Binary Tree

Renardi Dewanto C (26410004)Eko Bayu Kusumo (26410006)Steven Nico Tjandra (26410050)Lanny Sutanto (26409008)Roys Setiawan (26406112)

Parts of a binary tree• Sebuah pohon biner yang terdiri dari nol atau lebih node• Setiap node berisi:

-Sebuah nilai (beberapa jenis item data)-Sebuah referensi atau pointer ke anak kiri-Sebuah referensi atau pointer ke anak kanan

• Sebuah pohon biner mungkin kosong (tidak mengandung node)

• Jika tidak kosong, sebuah pohon biner memiliki node root-Setiap node dalam pohon biner dapat dicapai dari node root dengan jalan yang unik

• Sebuah node yang tidak memiliki anak kiri maupun anak kanan disebut leaf

Picture of a binary treea

b c

d e

g h i

l

f

j k

Size and depth• Ukuran pohon biner adalah

jumlah node di dalamnya- Pohon biner ini memiliki ukuran 12

• Kedalaman dari sebuah node jarak dari akar- a pada kedalaman nol- e pada kedalaman 2

• Kedalaman dari sebuah pohon biner adalah kedalaman simpul yang paling dalam- Pohon biner ini memiliki 4 kedalaman

a

b c

d e f

g h i j k

l

Tree traversals

• Sebuah pohon biner didefinisikan secara rekursif: terdiri dari akar, subtree kiri, dan subtree kanan

• Untuk traversal pohon biner adalah dengan mengunjungi setiap node dalam pohon biner Traversals pohon secara alami rekursif

• Ada dua jenis traversals secara umum- Breadth First Search- Depth First Search

Breadth First Search• Penelusuran tree dengan mencari node secara

mendatar atau horizontal

Depth First Search• Mencari tree dengan cara yang terdalam• Terdiri dari 3 :-In order traverse : Left, root, right-Pre order traverse : root, left, right-Post order traverse : left, right, root

Tree traversals using “flags”• Urutan di mana node dikunjungi selama traversal pohon

dapat dengan mudah ditentukan dengan membayangkan ada "bendera" yang melekat pada setiap node, sebagai berikut:

• To traverse the tree, collect the flags:

preorder inorder postorder

A

B C

D E F G

A B D E C F G

A

B C

D E F G

A

B C

D E F G

D B E A F C G D E B F G C A

Preorder traversal• Dalam preorder, akar dikunjungi pertama• Berikut adalah preorder traversal untuk mencetak

semua elemen dalam pohon biner:• void pre()

{cout<<data<<" ";if(left) left->pre();if(right) right->pre();

}

Inorder traversal• Dalam inorder, akar dikunjungi di tengah• Berikut adalah traversal inorder untuk mencetak

semua elemen dalam pohon biner:• void in()

{if(left) left->in();cout<<data<<" ";if(right) right->in();

}

Postorder traversal• Dalam postorder, akar adalah yang terakhir

dikunjungi• Berikut ini adalah traversal postorder untuk

mencetak semua elemen dalam pohon biner:• void post()

{if(left) left->post();if(right) right->post();cout<<data<<" ";

}

Other traversals• Traversals lainnya adalah kebalikan dari tiga

standar- Artinya, subtree kanan dilalui sebelum subtree kiri dilalui

• Kebalikannya preorder: akar, kanan subtree, subtree kiri

• Kebalikannya inorder: subtree kanan, akar, kiri subtree

• Kebalikannya postorder: subtree kanan, kiri subtree, akar

Di head.h#include <iostream.h>class node { private:

int data;node *left;node *right;

public:node (){

left=NULL;right=NULL;

}

int get (){return data; }

void set (int x){data=x; }

node * lget(){return (left); }

 void lset (node * nextnode){left=nextnode; }

node *rget(){return (right); }

 void rset(node * nextnode){right=nextnode;}

void in(){

if(left) left->in();cout<<data<<" ";if(right) right->in();

} 

void pre(){

cout<<data<<" ";if(left) left->pre();if(right) right->pre();

} 

void post(){

if(left) left->post();if(right) right->post();cout<<data<<" ";

}

void add(node *baru) {if(baru->get() < data){if(left==NULL){left=baru;}

 else{left->add(baru);}}

 else if(baru-> get() > data){if(right==NULL){right = baru;}

else{right->add(baru);}}}

};

class tree{

node * root;int count;

public: 

tree(){root=NULL;}

 void add(int x){node * baru;baru=new node;baru->set(x);

 if(!root){root=baru;}

 else{node * temp;temp = root;temp->add(baru);}count++;}

void inorder(){root->in();}

void preorder(){root->pre();}

 void postorder(){root->post();}

 void view(){

node * temp;count=0;temp=root;for(int i=0;i<count;i++){

cout<<temp->get()<<" ";}

}

};

Di main.cpp#include "head.h"void main(){

tree t;t.add(2);t.add(5);t.add(1);t.add(8);t.add(4);t.add(5);t.inorder();cout<<" ";t.postorder();cout<<" ";t.preorder();

}

The End

• http://www.cplusplus.com/forum/general/1551/• www.cis.upenn.edu/