POHON (LANJUTAN)

POHON (Lanjutan)

A.Pohon Berakar (rooted tree)

Pohon berakar yang urutan anak-anaknya penting disebut pohon  terurut (ordered tree).

1.Anak (child atau children) dan Orangtua (parent)

b, c, dan d adalah anak-anak simpul a,  a adalah orangtua dari anak-anak itu a.

2. Lintasan (path)

Lintasan dari a ke j adalah a, b, e, j.  Panjang lintasan dari a ke j adalah 3.

3. Saudara kandung (sibling)

f adalah saudara kandung e, tetapi g bukan

saudara kandung e, karena orangtua mereka  berbeda.

4. Upapohon (subtree)

5. Derajat (degree)

Derajat sebuah simpul   adalah   jumlah  upapohon           (atau     jumlah  anak) pada simpul tersebut.

Derajat a adalah 3, derajat b adalah 2,  Derajat d adalah satu dan derajat c adalah 0.

Jadi, derajat yang dimaksudkan di sini adalah derajat-keluar.

Derajat maksimum dari semua simpul merupakan derajat pohon itu  sendiri. Pohon di atas berderajat 3

6. Daun (leaf)

Simpul yang berderajat nol (atau tidak mempunyai anak) disebut

daun. Simpul h, i, j, f, c, l, dan m adalah daun.

7. Simpul Dalam (internal nodes)

Simpul yang mempunyai anak disebut simpul dalam. Simpul b, d,e, g, dan k adalah simpul dalam.

8. Aras (level) atau Tingkat

9. Tinggi (height) atau Kedalaman (depth)

Aras maksimum dari suatu pohon disebut tinggi atau kedalaman

pohon tersebut. Pohon di atas mempunyai tinggi 4.

B.Pohon Terurut (ordered tree)

Pohon berakar yang urutan anak-anaknya penting disebut pohon  terurut (ordered tree).

C.Pohon n-ary

• Pohon   berakar yang      setiap    simpul  cabangnya           mempunyai  paling banyak n buah anak disebut pohon n-ary.
  

< sentence>

• Pohon n-ary dikatakan teratur atau penuh (full) jika setiap  simpul cabangnya mempunyai tepat n anak.

D.Pohon Biner (binary tree)

~        Adalah pohon n-ary dengan n = 2.

~        Pohon yang paling penting karena banyak aplikasinya.

~        Setiap simpul di adlam pohon biner mempunyai paling  banyak 2 buah anak.

~        Dibedakan antara anak kiri (left child) dan anak kanan  (right child)

~        Karena ada perbedaan urutan anak, maka pohon biner  adalah pohon terurut.

 

E.Pohon Biner Seimbang

Pada beberapa aplikasi, diinginkan tinggi upapohon kiri dan tinggi  upapohon kanan yang seimbang, yaitu berbeda maksimal 1.

F.Terapan Pohon Biner

1. Pohon Ekspresi

2. Pohon Keputusan

3. Kode Awalan

4. Kode Huffman