Bab 13 tree tujuan



Download 200.11 Kb.
Page2/2
Date23.05.2020
Size200.11 Kb.
1   2

Pohon Biner Similer

Dua pohon yang memiliki struktur yang sama tetapi informasinya berbeda.



  1. Pohon Biner Ekuivalent

Dua pohon yang memiliki struktur dan informasi yang sama.



  1. Pohon Biner Miring (Skewed Tree)

Dua pohon yang semua simpulnya mempunyai satu anak / turunan kecuali daun.



    1. Sifat Utama Pohon Berakar

      1. Jika Pohon mempunyai Simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1).

      2. Mempunyai Simpul Khusus yang disebut Root, jika Simpul tersebut memiliki derajat keluar >= 0, dan derajat masuk = 0.

      3. Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika Simpul tersebut berderajat keluar = 0, dan berderajat masuk = 1.

      4. Setiap Simpul mempunyai Tingkatan / Level yang dimulai dari Root yang Levelnya = 1 sampai dengan Level ke - n pada daun paling bawah. Simpul yang mempunyai Level sama disebut Bersaudara atau Brother atau Stribling.

      5. Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan Level tertinggi.

      6. Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf) pada Pohon.

      7. Banyaknya Simpul Maksimum sampai Level N adalah :

        2 (N) - 1

      8. Banyaknya Simpul untuk setiap Level I adalah :

N

2 ( I – 1)



I = 1



    1. Kunjungan pada Pohon Biner

Kunjungan pohon biner terbagi menjadi 3 bentuk binary tree yaitu :

      1. Kunjungan secara preorder (Depth First Order), mempunyai urutan :

  1. Cetak isi simpul yang dikunjungi (simpul akar)

  2. Kunjungi cabang kiri

  3. Kunjungi cabang kanan





      1. Kunjungan secara inorder (symetric order), mempunyai urutan :

  1. Kunjungi cabang kiri

  2. Cetak isi simpul yang dikunjungi (simpul akar)

  3. Kunjungi cabang kanan





      1. Kunjungan secara postorder, mempunyai urutan :

  1. Kunjungi cabang kiri

  2. Kunjungi cabang kanan

  3. Cetak isi simpul yang dikunjungi (simpul akar)





    1. Aplikasi Pohon Biner

Pada bagian ini akan dibahas tentang bagaimana menyusun sebuah Pohon Biner yang apabila dikunjungi secara PreOrder akan menghasilkan Notasi Prefix, kunjungan secara InOrder menghasilkan Notasi Infix, dan kunjungan PostOrder menghasilkan Notasi Postfix.

  1. Prefix

Yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada didepan operand.

Contoh : A + B * C (Infix)

Maka notasi prefixnya adalah +A*BC

Pemecahannya :

A + B * C

Diketahui ada 3 operand yaitu : A, B, C, dan 2 operator yaitu + dan *. Proses dimulai dengan melihat dari hirarkhi operator. Contoh di atas operator yang tertinggi adalah * kemudian +.

Tanda * diapit oleh dua operand yaitu B dan C yaitu B * C, prefixnya dengan menggabungkan operand dan memindahkan operator ke depan dari operand, sehingga fungsi B * C, notasi prefixnya menjadi *BC. Sehingga hasil sementara dari notasi prefix adalah

A + *BC


Selanjutnya mencari prefix untuk operator yang berikutnya, yaitu +, cara yang dilakukan sama seperti di atas, operator +, diapit oleh 2 operand, yaitu A dan *BC, gabungkan operand, sehingga menjadi A*BC, lalu pindahkan operator ke depan operand, sehingga hasil akhir menjadi

+ A * B C

Contoh yang lain :

1. A + B – C * D

2 3 1  hirarkhi level

A + B – *CD  1

+ AB – *CD  2

– +AB *CD  3

2. A * B ^ C – D

2 1 3  hirarkhi

A * ^BC – D  1

*A^BC – D  2

-*A^BCD  3

3. A + ( B – C ) * D

3 1 2  hirarkhi

A + -BC * D  1 (karena diapit tanda paranthesis atau kurung buka/tutup, ( ) )

A + *-BCD  2

+ A *-BCD  3



  1. Infix

Yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada diantara operand. Notasi ini hanya dikenal oleh manusia dan selalu digunakan dalam perhitungan aritmatika.

Contoh : A + B * C

( A + B ) * C

A – ( B + C ) * D ^ E



  1. Postfix

Yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada dibelakang operand. Notasi ini hanya dikenal oleh processor dan dipahami dalam ALU.

Contoh : A + B * C (Infix). Maka notasi postfixnya adalah ABC*+



    1. Contoh Program Implementasi Tree

// C program for different tree traversals

#include

#include
/* A binary tree node has data, pointer to left child

and a pointer to right child */

struct node

{

int data;



struct node* left;

struct node* right;

};
/* Helper function that allocates a new node with the

given data and NULL left and right pointers. */

struct node* newNode(int data)

{

struct node* node = (struct node*)



malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;


return(node);

}
/* Given a binary tree, print its nodes according to the

"bottom-up" postorder traversal. */

void printPostorder(struct node* node)

{

if (node == NULL)



return;
// first recur on left subtree

printPostorder(node->left);


// then recur on right subtree

printPostorder(node->right);


// now deal with the node

printf("%d ", node->data);

}
/* Given a binary tree, print its nodes in inorder*/

void printInorder(struct node* node)

{

if (node == NULL)



return;
/* first recur on left child */

printInorder(node->left);


/* then print the data of node */

printf("%d ", node->data);


/* now recur on right child */

printInorder(node->right);

}
/* Given a binary tree, print its nodes in preorder*/

void printPreorder(struct node* node)

{

if (node == NULL)



return;
/* first print data of node */

printf("%d ", node->data);


/* then recur on left sutree */

printPreorder(node->left);


/* now recur on right subtree */

printPreorder(node->right);

}
/* Driver program to test above functions*/

int main()

{

struct node *root = newNode(1);



root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);


printf("\nPreorder traversal of binary tree is \n");

printPreorder(root);


printf("\nInorder traversal of binary tree is \n");

printInorder(root);


printf("\nPostorder traversal of binary tree is \n");

printPostorder(root);


getchar();

return 0;



}

    1. Latihan

???????????????

DAFTAR PUSTAKA

  1. Algorithm Data Structures and Problem Solving with C++. 1997. Addison Wesley.

  2. Moh. Sjukani, Algoritma dan Struktur Data. Mitra Wacana Media

  3. Inggriani Liem, Diktat Catatan Singkat Bahasa C Agustus 2003. ITB

  4. Inggriani Liem, Diktat Kuliah Dasar Pemrograman April 2007. ITB

  5. Rinaldi Munir, Algoritma dan Pemrograman. Informatika Bandung

  6. Schaum, Programming with C++ 2nd. 2000. McGraw-Hill

  7. Schaum. Teach yourself C++ in 21 days. 2007. McGraw-Hill

Download 200.11 Kb.

Share with your friends:
1   2




The database is protected by copyright ©sckool.org 2020
send message

    Main page