1

Pohon (Tree)

1. Definisi Rekurens Dari Pohon Sebuah pohon adalah himpunan terbatas tidak

kosong, dengan elemen yang dibedakan sebagai berikut :

1. Sebuah elemen yang dibedakan dari yang lain yang disebut sebagai AKAR (root) dari pohon

2. Elemen yang lain (jika masih ada) dibagi-bagi menjadi beberapa sub himpunan yang disjoint dan masing-masing sub himpunan tersebut adalah pohon yang disebut sebagai sub pohon dari pohon tersebut.

2

Beberapa Istilah

1. Hutan

Hutan adalah sequence (list) dari pohon

2. Simpul (Node)

Simpul adalah elemen dari pohon yang memungkinkan akses pada sub pohon dimana simpul tersebut berfungsi sebagai Akar

3. Cabang

Cabang adalah hubungan antara Akar dengan sub pohon

3

4. Ayah

Akar dari sebuah pohon adalah Ayah dari sub pohon

5. Anak

Anak dari sebuah pohon adalah Sub pohon

6. Saudara

Saudara adalah simpul-simpul yang mempunyai Ayah yang sama

7. Daun

Daun adalah simpul terminal dari pohon. Semua simpul selain Daun adalah simpul bukan terminal

4

8. Jalan (Path)

Jalan adalah suatu urutan tertentu dari

Cabang

9. Derajat

Derajat sebuah pohon adalah banyaknya

anak dari dari pohon tersebut.

Jika sebuah simpul berderajat N disebut

pohon N-aire

1 disebut pohon 1-aire/uner

2 disebut pohon 2-aire/biner

5

10. Tingkat (Level)

Level pohon adalah panjangnya jalan dari

Akar sampai dengan simpul yang

bersangkutan. Panjang dari jalan adalah

banyaknya simpul yang dikandung pada

jalan tersebut. Akar mempunyai tingkat sama

dengan 1.

Dua buah simpul disebut sebagai Sepupu jika

mempunyai tingkat yang sama dalam sebuah

pohon.

6

11. Kedalaman (Tinggi)

Kedalaman (Tinggi) dari pohon adalah nilai maksimum dari tingkat simpul yang ada pada pohon tersebut. Kedalaman adalah panjang maksimum jalan dari Akar menuju ke sebuah daun

12. Lebar

Lebar sebuah Pohon adalah maksimum banyaknya simpul yang ada pada suatu Tingkat (Level)

7

2. Struktur Pohon Biner Definisi

Sebuah pohon biner (Binary Tree) adalah himpunan terbatas yang :

Mungkin kosong atau

Terdiri dari sebuah simpul yang disebut sebagai Akar dan dua buah himpunan lain yang disjoint yang merupakan pohon biner yang disebut sebagai Sub Pohon Kiri (Left) dan Sub Pohon Kanan (Right) dari pohon biner tersebut.

8

Pohon biner merupakan tipe yang sangat penting

dari struktur data dan banyak dijumpai

dalam berbagai terapan. Karakteristik yang

dimiliki oleh pohon biner adalah bahwa

setiap simpul paling banyak hanya

memiliki dua buah anak, dan mungkin

tidak punya anak.

Istilah-istilah yang digunakan sama dengan

istilah pada pohon secara umum.

9

Notasi Prefiks, Infiks dan Postfiks

1. Notasi Prefiks

Notasi Prefiks ditulis dengan cara mengikuti

alur sebagai berikut :

10

2. Notasi Infiks

Notasi ini ditulis dengan cara mengikuti alur

sebagai berikut :

11

3. Notasi Posfiks

Notasi ini ditulis dengan cara mengikuti alur

sebagai berikut :

12

Rekonstruksi Algoritma

{Deklarasi Type}

Type Infotype = … {terdefinisi}

Type node = record <Info : infotype,

Left : address,

Right: address >

Type BinTree : address

{Primitif}

13

function Akar (P : BinTree) infotype

{Mengirimkan nilai Akar pohon biner P}

function Left (P : BinTree) infotype

{Mengirimkan anak kiri pohon biner P}

function Right (P : BinTree) infotype

{Mengirimkan anak kanan pohon biner P}

14

function IsEmpty(P : BinTree)boolean

{ Test apakah sebuah pohon kosong, mengirimkan True jika kosong dan False jika tidak}

procedure MakeTree(input Akar : infotype, L : BinTree, R : BinTree, output P : BinTree)

{ K. Awal : sembarang

K. Akhir : Terbentuk sebuah pohon biner

Proses : Menghasilkan sebuah pohon biner dari Akar, L dan R}

15

{Traversal}

Procedur PreOrder(input P : BinTree)

{K. AWAL : P terdefinisi

K. AKHIR : Semua simpul P sudah

diproses secara preorder}

Procedure InOrder(input P : BinTree)

{K. AWAL : P terdefinisi

K. AKHIR : Semua simpul P sudah

diproses secara inorder}

16

Procedure PostOrder(input P : BinTree)

{K. AWAL : P terdefinisi

K. AKHIR : Semua simpul P sudah

diproses secara postorder}

Procedure PrintTree(input P : BinTree, h : integer)

{K. AWAL : P terdefinisi, h adalah jarak indentasi

K. AKHIR : Semua simpul P sudah ditulis dengan

indentasi}

17

{Search}

function Search(P : BinTree, X : infotype)boolean

{Mengirimkan True jika ada node P bernilai X, false

jika tidak}

{fungsi lain}

function NbElmt(P : BinTree)integer

{Mengirimkan banyaknya elemen (node) pohon

biner P}

18

function NbDaun(P : BinTree) integer

{ Mengirimkan banyaknya daun pohon biner P}

function IsUnerLeft(P : BinTree) boolean

{ Mengirimkan True jika pohon biner tidak

kosong P adalah pohon unerleft yaitu hanya

mempunyai sub pohon kiri}

function IsUnerRight(P : BinTree) boolean

{ Mengirimkan True jika pohon biner tidak

kosong P adalah pohon unerright yaitu hanya

mempunyai sub pohon kanan}

19

function IsBin(P : BinTree)boolean

{ Mengirimkan True jika pohon biner tidak kosong P adalah pohon biner yaitu mempunyai sub pohon kanan dan sub pohon kiri}

function IsSkewLeft(P : BinTree)boolean

{ Mengirimkan True jika pohon biner P adalah pohon condong kiri}

function IsSkewRight(P : BinTree)boolean

{ Mengirimkan True jika pohon biner P adalah pohon condong kanan}

20

function Tinggi(P : BinTree)integer

{ Mengirimkan tinggi dari pohon biner P}

function Level(P : BinTree, X : infotype)integer

{ Mengirimkan level dari node X yang merupakan

salah satu simpul dari pohon biner P}

{Operasi Lain}

21

Procedure AddDaunTerkiri(input/output P:BinTree, input X: infotype)

{K. AWAL : P boleh kosong

K. AKHIR : P bertambah simpulnya, dengan X adalah simpul daun terkiri}

Procedure AddDaun(input/output P:BinTree, input X, Y : infotype, input Kiri : boolean)

{K. AWAL : P tidak boleh kosong, X adalah salah satu daun pohon Biner P

K. AKHIR : P bertambah simpulnya, dengan Y adalah anak kiri X (jika kiri) atau sebagai anak kanan X (jika not kiri)}

22

Procedure DelDaunTerkiri(input/output P:BinTree, output X: infotype)

{K. AWAL : P tidak kosong

K. AKHIR: P dihapus daun terkirinya dan didealokasi, dengan X adalah info yang semula disimpan pada daun terkiri yang dihapus}

Procedure DelDaun(input/output P:BinTree, output X: infotype)

{K. AWAL : P tidak kosong, X adalah salah satu daun

K. AKHIR : X dihapus dari P}