Pengertian Tree dalam Teori Bahasa dan Automata

Tree merupakan salah satu bentuk struktur data non-linear yang menggambarkan hubungan yang bersifat hirarkis antara elemen-elemen. Tree dapat juga didefinisi-kan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut rootdan nodelainnya  yang  terbagi  lagi  menjadi  himpunan-himpunan  yang  disebut subtree. Terdapat beberapa istilah dalam tree, diantaranya adalah sebagai berikut:

1. Predecessor, merupakan nodeyang berada di atas nodetertentub.
2. Successor, merupakan node yang berada di bawah node tertentu.
3. Ancestor:seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
4. Descendant:seluruh node  yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
5. Father:predecessor satu level di atas suatu node.
6. Son:successor satu level di bawah suatu node.
7. Sibling:node-node  yang  memiliki  father  yang  sama  dengan  suatu node.
8. Subtree:bagian  dari  tree  yang  berupa  suatu  node  beserta  descendant-nya dan memiliki semua karakteristik dari tree tersebut.
9. Size: Banyaknya node dalam suatu tree.
10. Height:Banyaknya tingkatan/level dalam suatu tree.
11. Root:Satu-satunya   node   khusus   dalam   tree   yang   tak   punya predecessor.
12. Leaf:Node-node dalam tree yang tak memiliki successor.
13. Degree :Banyaknya son yang dimiliki suatu node.

Contoh:

Keterangan :

• Ancestor (H)= F,C,A
• Descendant (F)= H,I
• Father (D)=B
• Son (A)= B,C
• Sibling (D)= E
• Size= 9
• Height= 4
• Root= A
• Leaf= D,G,H,I
• Degree (E)= 1