Pohon Biner

* Struktur pohon:

-          Pohon statik: berisi node tetap

-          Pohon dinamik: berisi node yang berubah-ubah

* Node root adalah node yang paling atas dan memiliki anak. Sedangkan node dibawah root merupakan subtree.

* Istilah-istilah dalam pohon biner:

-          Predecessor : Node yang ada diatas node tertentu.

-          Successor : Node yang ada dibawah node tertentu.

-          Ancestor : Seluruh node yang terletak sebelum node tertentu pada jalur yang sama.

-          Descendant : Seluruh node yang terletak setelah node tertentu pada jalur yang sama.

-          Parent : Predecessor satu level diatas suatu node.

-          Child : Successor satu level diatas suatu node.

-          Sibling : Node-node yang memiliki parent yang sama.

-          Subtree : Suatu node beserta descendant.

-          Size : Banyak node dalam tree.

-          High : Banyak tingkatan dalam tree.

-          Root : Node khusus yang tidak memiliki predecessor.

-          Leaf  : Node dalam tree yang tidak memiliki successor.

-          Degree : Banyaknya child didalam suatu node.

Contoh:

Dari gambar diatas dapat diketahui bahwa:

Ancestor dari F adalah C dan A

Descendant dari C adalah F dan G

Parent dari D adalah B

Child dari A adalah B dan C

Height/tinggi pohon adalah 3

Root pohon adalah A

Leaf pohon adalah D, E, F, G

Degree C adalah 2

* Langkah-langkah membentuk pohon biner dari notasi infix:

1.      Tentukan valensi,

2.      Ambil semua karakter dari string yang berisi notasi Infix dan tes karakter tersebut,

3.      Jika ada kurung buka, maka push karakter ini kedalam tumpukan operator.

4.      Jika ada operand, push karakter ini kedalam tunpukan operand.

5.      Jika kurung tutup, pop 2 buah elemen dari tumpukan operand (elemen pertama menempati cabang kanan dan elemen kedua menempati cabang kiri) dan pop sebuah elemen dari tumpukan operator (dipasang sebagai akar). Gabung elemen-elemen ini sehingga membentuk sebuah pohon biner dan push kembali operator tersebut kedalam tumpukan operand. Langkah ini diulang sampai elemen teratas tumpukan operator berisi ‘(‘. Pop juga elemen ini, tetapi tidak perlu diapa-apakan.

6.      Jika operator, maka perlu dibandingkan valensi operator tersebut dengan valensi elemen teratas dari tumpukan operator.

7.      Jika tumpukan operator tersebut lebih kecil atau sama dengan valensi teratas dari tumpukan operator dan tumpukan operator tidak kosong, maka lakukan langkah-langkah seperti nomor 5.

8.      Jika valensi operator itu lebih besar atau tumpukan kosong, push operator tersebut kedalam tumpukan operator.