Struktur Data : Tree ( Pohon )

Posted on

A.    Tugas Pendahuluan :

1.        Jelaskan secara lengkap definisi Tree?
2.        Jelaskan Istilah-istilah umum dalam Tree :
a.       Prodecessor
b.      Successor
c.       Ancestor
d.      Descendant
e.       Parent
f.       Child
g.      Sibling
h.      Subtree
i.        Size
j.        Height
k.      Root
l.        Leaf
m.    Degree

3.        Sebutkan jenis-jenis Tree? Apa definisi dari Binary Tree, Full Binary Tree, Complete Binary Tree, Skewed Binary Tree?

Tugas Pendahuluan Praktikum Struktur Data
Modul 5
Tree
1.      Definisi tree : “Kumpulan elemen yang salah satu elemennya disebut dengan root (akar) dan sisa elemen yang lain disebut sebagai simpul (node/vertex) yang terpecah menjadi sejumlah himpunan yang tidak saling berhubungan satu sama lain, yang disebut subtree/cabang”.
2.       
a.       Predecessor adalah simpul yang berada di atas simpul yang ditinjau. Contoh : Predecessor D adalah B.
b.      Successor adalah simpul yang berada di bawah simpul yang ditinjau. Contoh : Successor D adalah I.
c.       Ancestor suatu simpul adalah semua simpul yang terletak dalam satu jalur dengan simpul tersebut, dari akar sampai simul yang ditinjaunya. Contoh Ancestor L adalah A,C dan G.
d.      Descendant adalah seluruh simpul yang terletak sesudah simpul tertentu dan terletak pada jalur yang sama. Contoh : Descendant E adalah J dan K.
e.       Parent adalah simpul yang berada satu level di atas simpul yang ditinjau. Contoh : Parent J adalah E
f.       Child,  suatu node adalah semua node yang dapat dicapai oleh node tersebutdengan sebuah path saja. Sebagai contoh, child dari N1 adalah N2, N3, dan N4;
child dari N4 adalah N5 dan N6; dan sebagainya.
g.       Sibling adalah simpul-simpul yang memiliki parent yang sama dengan simpul yang ditinjau. Contoh : Sibling J adalah K
h.      Subtree, sisa elemen yang lain (yang disebut node) terpecah menjadi sejumlah himpunan yang saling tidak berhubungan satu sama
lain (disjoint),
i.        Size : banyaknya node dalam suatu tree
j.        Height, Tinggi (height) atau kedalaman (depth) suatu tree adalah tingkat maksimum dari tingkat dalam tree tersebut dikurangi 1. Contoh dalam tree di atas, mempunyai depth 4.
k.      Root : satu-satunya node khusus dalam tree yang tak punya predecssor
l.        Leaf, simpul yang memiliki derajat 0 (nol) atau node-node dalam tree yang tak memiliki seccessor.
m.    Degree, menyatakan banyaknya anak/turunan di simpul tersebut. Contoh : Simpul A memiliki derajat 2 (B dan C), simpul yang memiliki derajat 0 (nol) disebut leaf (daun) seperti : I, J, K, L, N, dan O.
3.       Jenis-jenis tree
a.       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.
b.      Full Binary Tree, Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.
c.       Complete Binary Tree, Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
d.      Skewed Binary Tree yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

 

1.      Bila dipastikan simpul no. 50 ada, maka susun algoritma untuk menempatkan pointer Q sehingga menunjuk simpul no. 50 tersebut!
2.      Susun algoritma untuk menginsert simpul baru yang ditunjuk oleh pointer P, sehingga menjadi simpul no.50, bila dipastikan simpul no.25 ada dan simpul no. 50 belum ada!
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <conio.h>
struct node
{
int data;
struct node *right, *left;
}*root,*p,*q;
struct node *make(int y)
{
struct node *newnode;
newnode=(struct node *)malloc(sizeof(struct node));
newnode->data=y
newnode->right=newnode->left=NULL
return(newnode)
}//andhika na
void left(struct node *root,int y)
{
if(root->left!=NULL)
printf(“n Invalid !”);
else
root->left=make(y);
}
void right(struct node *root,int y)
{
if(root->right!=NULL)
printf(“n Invalid !”);
else
root->right=make(y);
}
void inorder(struct node *root)
{
if(root!=NULL)
{
inorder(root->left);
printf(“t %d”,root->data);
inorder(root->right);
}//andhika na
}
void preorder(struct node *root)
{
if(root!=NULL)
{
printf(“t %d”,root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(struct node *root)
{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf(“t %d”,root->data);
}
}
void cle()
{
gotoxy(17,4); printf(” “);
}
void main()
{//andhika na
int no;
int leftx=42;
int lefty=3;
int rightx=48;
int righty=3;
int choice;
clrscr();
printf(“nMasukkan root : “);
scanf(“%d”,& no);
gotoxy(0,1); printf(“Tekan -1 untuk berhenti..”);
gotoxy(45,1); printf(“(%d)”,no);
gotoxy(44,2); printf(“/”);
gotoxy(48,2); printf(“\”);
root=make(no);
p=root;
while(1)
{
int yy=3;
cle();
gotoxy(0,yy+1);printf(“Masukkan nomor : “);
gotoxy(17,yy+1);scanf(“%d”,&no);
if(no==-1)
break;
p=root;
q=root;
while(no!=p->data && q!=NULL)
{
p=q;
if(no<p->data)
{//andhika na
q=p->left;
}
else{
q=p->right;
}
}
if(no < p->data)
{
gotoxy(leftx–,lefty–); printf(“(%d)”,p->data,no);
gotoxy(leftx–,lefty–); printf(“/”);
left(p,no);
}
else
{
right(p,no);
gotoxy(rightx++,righty++); printf(“(%d)”,p->data,no);
gotoxy(rightx++,righty++); printf(“\”);
}
}
while(1)
{//andhika na
printf(“n 1.Inorder”);
printf(“n 2.Preorder”);
printf(“n 3.Postorder”);
printf(“n 4.Exit”);
printf(“nn>>Masukkan Pilihan:”);
scanf(“%d”,&choice);
switch(choice)
{
case 1 :
inorder(root);
break;
case 2 ://andhika na
preorder(root);
break;
case 3 :
postorder(root);
break;
case 4 :
exit(0);
default:
printf(“Error ! Invalid Choice “);
break;
}
getch();
}//andhika na
}
Tampilan :
hasil compile program
 

Gravatar Image
Suka jalan-jalan, naik sepeda, bermain code-code asal tidak suka mengkode cinta. Hubungi email : andhika.na@gmail.com jika anda butuh website untuk personal maupun bisnis.

Leave a Reply

Your email address will not be published. Required fields are marked *