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
Merupakan
salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang
bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa
didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang
disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak
berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di bawah akan
diuraikan istilah-istilah umum dalam tree :
a) Prodecessor : node
yang berada diatas node tertentu.
b) Successor : node yang berada di bawah node tertentu.
c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
e) Parent : predecssor satu level di atas suatu node.
f) Child : successor satu level di bawah suatu node.
g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.
h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
i) Size : banyaknya node dalam suatu tree.
j) Height : banyaknya tingkatan/level dalam suatu tree.
k) Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
l) Leaf : node-node dalam tree yang tak memiliki seccessor.
m) Degree : banyaknya child yang dimiliki suatu node.
Contoh Program Tree :
b) Successor : node yang berada di bawah node tertentu.
c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
e) Parent : predecssor satu level di atas suatu node.
f) Child : successor satu level di bawah suatu node.
g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.
h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
i) Size : banyaknya node dalam suatu tree.
j) Height : banyaknya tingkatan/level dalam suatu tree.
k) Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
l) Leaf : node-node dalam tree yang tak memiliki seccessor.
m) Degree : banyaknya child yang dimiliki suatu node.
Contoh Program Tree :
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<string.h>
//Defination of nodes of the tree
class node
{
public:
char value [11];
node *lchild;
node *rchild;
};
node *root = NULL; //root note is set to empty
//INSERT A NEW NODE IN THE TREE
void insert (node *z)
{
node
*x;
node
*y;
y =
NULL;
x =
root;
while ( x!=NULL)
{
y = x;
//compare value of new node with value of x
if(strcmp(z->value,x->value) < 0)
{
x= x-> lchild; //if new value less seek left child
}
else
{
x= x-> rchild; //if new value greater seek right child
}
}
//if
value of y is null write new node at root
if(
y==NULL )
{
root=z;
}
else if(strcmp(
z->value,y->value) < 0)
{
y -> lchild = z;
}
else
{
y-> rchild = z;
}
}
//PREORDER TRAVERSAL OF TREE BY RECURSION
void preorder( node *r )
{
cout<< r -> value << " ";
if
(r->lchild != NULL)
preorder (r->lchild);
if
(r->rchild != NULL)
preorder (r->rchild);
}
//INORDER TRAVERSAL OF TREE BY RECURSION
void inorder( node *r )
{
if
(r->lchild != NULL)
inorder (r->lchild);
cout<< r -> value << " ";
if
(r->rchild != NULL)
inorder (r->rchild);
}
//POSTORDER TRAVERSAL OF TREE BY RECURSION
void postorder( node *r )
{
if
(r->lchild != NULL)
postorder (r->lchild);
if
(r->rchild != NULL)
postorder (r->rchild);
cout<< r -> value << " ";
}
void main()
{
int
choice;
while (choice!=3)
{
clrscr();
cout<<"\n\n\t 1. Insert a element
to the tree.";
cout<<"\n\n\t 2. Traverse the tree.";
cout<<"\n\n\t 3. Exit.";
cout<<"\n\n\t Enter your choice : ";
cin>>choice;
switch (choice)
{
case 1: clrscr();
node *z=new node; //create a new node
cout<<"\n\n\tEnter a text string: ";
cin >> z->value;
z->rchild=NULL; //set left child as NULL
z->lchild=NULL; //set right child as NULL
insert (z); //insert node in tree
break;
case 2: clrscr();
cout << "\n\n\t Preorder Traversal : ";
preorder(root);
cout << "\n\n\t Inorder Traversal : ";
inorder(root);
cout << "\n\n\t Postorder Traversal : ";
postorder(root);
getch();
break;
case 3: break;
}
}
}
// end of program
Tidak ada komentar:
Posting Komentar