Modul 6
Binary Search Tree
Tujuan Praktikum:
1. Memahami Binary search tree dan operasi – operasi terhadap tree
2. Memahami beberapa cara tree treversal
3. Memanfaatkan tree pada persoalan pemrograman tertentu
4. Memahami pembuatan tree dengan array dan linked list
Teori:
Binary tree adalah abstraksi tree dengan aturan setiap node paling banyak memiliki 2 anak node. Binary tree disebut full binary tree jika setiap dahan pada aras yang sama dan setiap node memiliki 2 anak. Jika sebuah full binary memiliki tinggi h maka akan memiliki 2 pangkat h dahan. Sebuah binary tree complit (lengkap adalah sebuah pohon biner penuh atau lainnya yang dapat dibuat penuh hanya pada aras terbawah.
Pohon biner dapat dikunjungi anak – anaknya dengan beberapa cara:
1. Preorder
a. Kunjungi Root
b. Jika tree disebelah kiri tidak kosong, maka lakukan kunjungan preorder padanya.
c. Jika tree disebelah kanan tidak kosong, maka lakukan kunjungan preorder padanya
2. PostOrder
a. Jika tree disebelah kiri tidak kosong, maka lakukan kunjungan postorder padanya
b. Jika tree disebelah kanan tidak kosong, maka lakukan kunjungan postorder padanya
c. Kunjungi Root
3. Inorder
a. Jika Tree disebelah kiri tidak kosong, maka lakukan kunjungan inorder padanya,
b. Kunjungi root
c. Jika tree disebelah kanan tidak kosong, maka lakukan kunjungan inorder padanya.
Praktikum:
Alat dan Bahan:
- IDE C++ (Integrated Development Environtment) seperti Borland C++
- System Operasi Windows
Langkah – langkah Praktikum :
1. Buat Project baru, beri nama Lab06_01 (seperti langkah 1 s/d 5 pada Lab01_01)
2. Buatlah source code berikut:
/************************/
/* Lab06_01.cpp */
/************************/
#include
#include
#include
struct simpul
{
char info;
struct simpul *right;
struct simpul *left;
};
struct tree
{
struct simpul *root;
};
void makeTree(char c, tree *T)
{
simpul *node;
node = (simpul *) malloc(sizeof (simpul));
node->info = c;
node->right = NULL;
(*T).root = node;
}
void addRight(char c, simpul **root)
{
if((*root)->right == NULL)
{
/*jika sub pohon kanan kosong*/
simpul *node;
node = (simpul *) malloc(sizeof (simpul));
node->info = c;
node->right = NULL;
node->left = NULL;
(*root)->right = node;
}
else
{
printf("sub pohon kanan telah terisi \n");
}
}
void addLeft(char c, simpul **root)
{
if((*root)->left == NULL)
{
//Jika sub pohon kiri kosong
simpul *node;
node = (simpul *) malloc(sizeof (simpul));
node->info = c;
node->right = NULL;
node->left = NULL;
(*root)->left = node;
}
else
{
printf("sub pohon kiri telah terisi \n");
}
}
void delRight(simpul **root)
{
simpul *node = (*root)->right;
(*root)->right = NULL;
free(node);
}
void delLeft(simpul **root)
{
simpul *node = (*root)->left;
(*root)->left = NULL;
free(node);
}
void printTreePreOrder(simpul *root)
{
if(root != NULL)
{
printf(" %c ", root->info);
printTreePreOrder(root->left);
printTreePreOrder(root->right);
}
}
void printTreeInOrder(simpul *root)
{
if(root != NULL)
{
printTreeInOrder(root->left);
printf(" %c ", root->info);
printTreeInOrder(root->right);
}
}
void printTreePostOrder(simpul *root)
{
if(root != NULL)
{
printTreePostOrder(root->left);
printTreePostOrder(root->right);
printf(" %c ", root->info);
}
}
void printTreeLevelOrderNext(simpul *root)
{
if(root != NULL)
{
if(root->left != NULL)
{
printf(" %c ", root->left->info);
}
if(root->right != NULL)
{
printf(" %c ", root->right->info);
}
if(root->left != NULL)
{
printTreeLevelOrderNext(root->left);
}
if(root->right != NULL)
{
printTreeLevelOrderNext(root->right);
}
}
}
void printTreeLevelOrder(simpul *root)
{
if(root != NULL)
{
printf(" %c ", root->info);
printTreeLevelOrderNext(root);
}
}
void copyTree(simpul *root1, simpul **root2)
{
if(root1 != NULL)
{
(*root2) = (simpul *)malloc(sizeof (simpul));
(*root2)->info = root1->info;
if(root1->left != NULL )
{
copyTree(root1->left, &(*root2)->left);
}
if(root1->right != NULL)
{
copyTree(root1->right, &(*root2)->right);
}
}
}
bool isEqual(simpul *root1, simpul *root2)
{
bool hasil = true;
if((root1 != NULL) && (root2 != NULL))
{
if(root1->info != root2->info)
{
hasil = false;
}
else
{
isEqual(root1->left, root2->left);
isEqual(root1->right, root2->right);
}
}
else
{
if((root1 != NULL)||(root2!= NULL))
{
hasil = false;
}
}
return hasil;
}
int main()
{
struct tree T;
makeTree('A', &T);
addLeft('B', &T.root);
addRight('C', &T.root);
addLeft('D', &T.root->left);
addRight('E', &T.root->left);
addRight('F', &T.root->right);
printf("===================\n");
printf("preOrder\n");
printTreePreOrder(T.root);
printf("\n=================\n");
printf("inOrder\n");
printTreeInOrder(T.root);
printf("===================\n");
printf("postorder\n");
printTreePostOrder(T.root);
printf("===================\n");
printf("levelOrder\n");
printTreeLevelOrder(T.root);
printf("===================\n");
tree T2;
copyTree(T.root, &T2.root);
if(isEqual(T.root, T2.root) == true)
{
printf("pohon sama\n");
}
else
{
printf("pohon tidak sama\n");
}
delRight(&T.root->left);
delLeft(&T.root->left);
printf("====================\n");
printf("preOrder setelah dihapus\n");
printTreePreOrder(T.root);
printf("====================\n");
getch();
return 0;
}
Pertanyaan Praktikum:
1. Jelaskan dan berikan analisis pada keluaran Lab06_01.cpp!
2. Jelaskan algoritma:
a. makeTree()
b. addLeft() dan addRight()
c. printTreePreOrder()
d. printTreeInOrder()
e. printTreePostOrder()
f. copyTree()
g. delLeft() dan delRight()
