Struktur Data : Tree

DEFINISI

 

Tree bisa didefinisikan sebagai suatu kumpulan elemen salah satu elemennya disebut dengan akar (root), dan sisa elemen lainnya (yang disebut simpul) terpecah menjadi sejumlah himpunan yang paling tidak berhubungan satu sama lain, yang disebut dengan subpohon (subtree), atau disebut juga cabang.
Jika kita melihat pada subpohon, maka subpohon inipun juga mempunyai akar dan sub-subpohonnya masing-masing. Dalam kehidupan sehari-hari, tree dapat dilihat dari pohon silsilah keluarga. Tingkat yang tertinggi disebut juga sebagai root.

 

Binary Tree
Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

 

CONTOH PROGRAM

#include<iostream.h>
#include<malloc.h>
struct nod {
struct nod *left;
char data;
struct nod *right;
};

typedef struct nod NOD;
typedef NOD POKOK;

NOD *NodBaru(char item)
{
NOD *n;
n=(NOD*) malloc (sizeof(NOD));
if(n!=NULL)
{
  n->data=item;
  n->left=NULL;
  n->right=NULL;
}
return n;
}
void BinaPokok(POKOK **T)
{
*T=NULL;
}
typedef enum {FALSE =0,TRUE=1}BOOL;
BOOL PokokKosong(POKOK *T)
{
return ((BOOL)(T==NULL));
}
void TambahNod(NOD **p,char item)
{
NOD *n;
n=NodBaru(item);
*p=n;
}
void preOrder (POKOK *T)
{
if(!PokokKosong(T))
{
  printf("%c",T->data);
  preOrder(T->left);
  preOrder(T->right);
}
}
void inOrder(POKOK *T)
{
if(!PokokKosong(T))
{
  inOrder(T->left);
  printf("%c",T->data);
  inOrder(T->right);
}
}
void postOrder(POKOK *T)
{
if(!PokokKosong(T))
{
  postOrder(T->left);
  postOrder(T->right);
  printf("%c",T->data);
}
}
int main()
{
POKOK *kelapa;
char buah;
BinaPokok(&kelapa);
TambahNod(&kelapa,buah='M');
TambahNod(&kelapa->left,buah='E');
TambahNod(&kelapa->left->right,buah='I');
TambahNod(&kelapa->right,buah='L');
TambahNod(&kelapa->right->right,buah='O');
TambahNod(&kelapa->right->right->left,buah='D');

printf("tampilkan secara preorder");
preOrder(kelapa);
printf("\ntampilkan secara inorder");
inOrder(kelapa);
printf("\ntampilkan secara postorder");
postOrder(kelapa);
printf("\n\n");
return 0;
}

 

TREE TRAVERSAL

 

Tree traversal merupakan proses mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Adatiga cara traverse : Pre Order, In Order, dan Post Order.

 

Jenis traversal tree ada 3 yaitu:

1. Pre Order

• Kunjungi simpul akar
• Sub kiri
• Sub kanan
• Contoh: Tree = (C * D) + E, maka Pre Order = +*CDE

2. In Order

• Sub kiri
• Kunjungi simpul akar
• Sub kanan
• Contoh, Tree = (C * D) + E, maka In Order = C*D+E

3. Post Order

• Sub kiri
• Sub kanan
• Kunjungi simpul akar
• COntoh, Tree = (C * D) + E, maka Post Order = CD*E+