Rabu, 27 April 2011

POHON ( TREE ) Pengertian Pohon Pohon atau tree adalah salah satu bentuk konsep struktur data yang terdiri dari akar dan simpul-simpul yang berada dibawah akar. tingkat I tingkat 2 tingkat 3 tingkat 4 Gambar Tingkat Pohon Tree Selain istilah tingkat juga ada yang disebut dengan derajat ( degree ). Derajat merupakan banyak tingkat simpul turunan dari satu simpul tertentu, misalkan simpul tertentu, misalkan simpul “ Ketua Umum” memiliki derajat 3, simpul “ wakil Ketua I “ memiliki derajat 2 dan seterusnya. Simpul yang memiliki derajat 0 disebut dengan daun ( leaf), pada struktur data pohon dikenal istilah yang disebut kedalaman ( depth ). Sedangkan sebuah simpul yang ada diatas sebuah simpul lain disebut sebagai ancestor. Kumpulan pohon disebut dengan hutan ( forest ). Ada beberapa cara untuk menggambarkan sebuah pohon yaitu : Keterangan Representasi Pohon Menggunakan graph Menggunakan diagram venn Menggunakan notasi kurung ( A, ( B ( E, F ), c ( G), D( H, I ) ) Pohon biner lengkap ( complete binary tree ) yaitu pohon bier yang setiap simpulnya mempunyai dua buah simpul turunan. Pohon biner condong kiri ( leaft skewed binary tree ) Pohon biner condong kanan ( right skewed binary tree ) Pohon biner sembarang Operasi Pada Pohon Biner Operasi pada pohon biner : - Operasi yang dapat dilakukan pada pohon biner antara lain kunjungan terhadap simpul simpulnya. Jenis-jenis kunjunfan pada pohon biner antara lain : - Preorder - Inorder - Postorder - Level order Pre Order Kunjungan preorder merupakan kunjungan pada pohon biner yang dimulai dari akar kemudian ke subpohon kiri, setelah subpohon kiri dikunjungi baru subpohon kanan dikunjungi. Maka dengan kunjungan preorder akan menghasilkan urutan simpul yang dikunjungi A – B – D – E – C – F – G – H In Order Kunjungan inorder merupakan kunjungan pada pohon biner yang dimulai dari simpul-simpul turunan subpohon kiri, akar, baru kemudian simpul-simpul turunan pada subpohon kanan. Maka kunjungan inoeder akan menghasilkan urutan simpul : D – B – E – A – F – C – H – G Post Order Kunjungan post order merupakan kunjungan pada pohon biner yang dimulai dari simpul-simpul turunan subpohon kiri, baru kemudian simpul-simpul turunan pada subpohon kanan, Kemudian akar, misalkan terdapat sebuah pohon biner seperti pada gambar Post Order akan menghasilkan urutan simpul yang dikunjungi : D – E – B – F – H – G – C – A Level Order Kunjungan level order merupakan kunjungan pada pohon biner yang dimulai dari simpul pada tingkat 1 kemudian simpul-simpul pada tingkat 2 dan seterusnya., dimulai dari simpul paling kiri ke kanan. Kunjungan level order akan menghasilkan urutan simpul A- B- C – D – E – F – G – H Implementasi Pohon Biner Pointer sub pohon kanan pointer subpohon kiri sehingga jika di implementasikan sebagai pohon , simpul-simpul itu akan menjadi seperti : Null Null Null Null Null Null Null ( Representasi Pohon Biner ) Pohon Tree Struktur data berbentuk Tree dapat diartikan bahwa relasi antar elemen adalah hierarkis. Selalu terdapat satu elemen sebagai akar ( roots ) dan diikuti oleh elemen-elemen sebagai cabang-cabang. Record mahasiswa dengan atribut : Nomorpokok, Nama, Alamat, Jurusan, Hierarki mahasiswa dapat ditulis dalam bentuk Record terstruktur : 01 Mahasiswa 02 Nomorpokok 02 Nama 03 Depan 03 Famili 03 Alias 02 Jurusan 02 Alamat 03 Jalan 03 Area 04 Kota 04 Negara 04 Kodepos Contoh : Hierarki dipergunakan juga untuk menggambarkan formulasi aljabar : f(x) = ( 2x + y ) ( a – 7b )3 seperti : level 0 v0 e2 e0 e1 Level 1 V1 v2 v3 Level 2 Level 3 Tree atau Pohon Termasuk struktur data non linear. Tree , M-Ary tree dan Binary Tree Contoh sebuah Tree : Level 0 V0 e2 e0 e1 Level 1 v3 v1 v2 level 2 Level 3 Ada banyak nama, istilah dan pengertian yang digunakan untuk mengilustrasikan atau menyatakan ataupun yang dikaitkan dengan pohon , antara lain : a. Tree ( pohon ) dan Graph ( Grafik ) b. Simpul ( Vertex, Node ), dan Busur ( Edge, Arch ) c. Superordinat dan Subordinat, father dan son, parent dan children d. Root ( akar ) dan Leap ( Daun ) e. Level ( Tingkat ) dan Depth ( kedalaman ) f. Degree ( derajat simpul dan Degree pohon g. M- ary tree dan Binary tree. h. Link dan Null- Link. Istilah-istilah diatas dapat diuraikan sebagai : a. Tree dan graph Tree merupakan bagian dari Graph T =  G b. Simpul dan Busur Pohon merupakan kumpulan dari simpul dan busur, dimana salah satu simpul merupakan akar ( Root ) dan simpul – simpul lain membentuk suatu subpohon atau subtree yang dapat disimbolkan sebagai berikut : T = ( V, E ) Dimana : V = Vertex, atau Node atau titik atau simpul. E = Edge, atau Arc atau Busur. Simpul Disini digunakan istilah vertex, yang disimbolkan dengan huruf besar. Tree terdiri dari 14 buah simpul ( n = 14 ) yaitu simpul A sampai dengan simpul N, atau V0 sampai dengan v13, yang disimbolkan sebagai berikut : V = { v0 , v1 , v2 , ………., v13 } Yang maksudnya v terdiri dari atau merupakan kumpulan dari v0 , v1, ….. Busur Disini digunakan istilah Edge yang disimbolkan dengan huruf E besar, Tree terdiri dari 13 buah busur ( m = 12 ) yaitu e 0 sampai dengan e13 yang disimbolkan sebagai berikut : E = { e0 , e1, e2, ………, e12 } Yang maksudnya E teridiri dari atau merupakan kumpulan dari e0 , e1, e2, ………, e12. Bila jumlah simpul dinyatakan dengan : n Dan jumlah busur dinyatakan dengan : m Maka selalu berlaku hubungan : m = n -1 c. Superordinat Untuk contoh pohon diatas : - Simpul B merupakan superordinat simpul E dan F. - Simpul E dan F mempunyai superordinat simpul B Superordinat diistilahkan dengan Father ( Bapak ) dan Subordinat diistilahkan dengan Son ( Anak ). Ada yang mengistilahkan dengan Parent dan Children. d. Root ( Akar ) dan Leaf ( Daun ) Root ( Akar ) adalah simpul yang tak mempunyai superordinat. Untuk pohon yang dicontohkan diatas maka akar adalah simpul A. Leaf ( Daun ) adalah simpul yang tak mempunyai subordinat. Untuk pohon yang dicontohkan diatas, maka daun adalah : simpul C, E, G, I, J, K, L, M, N e. Level ( Tingkat ) dan Depth ( Kedalaman ) Akar dinyatakan berada pada level 0, atau disebut level 1. Setiap turun satu subordinat, level bertambah 1. Depth ( Kedalaman ) disebut ketinggian ( height ) Suatu pohon yang mempunyai level teratas atau level tertinggi = k , maka disebut kedalamannya = k. Untuk pohon yang dicontohkan diatas, karena level tertinggi adalah 3, maka depth = 3 f. Degree ( derajat ) sebuah simpul Degree sebuah simpul menyatakan jumlah simpul subordinat dari simpul tersebut: Untuk pohon yang dicontohkan pada gambar dibawah ini : Simpul A : degree = 3 Simpul B : degree = 2 Simpul C : degree = 0 Degree sebuah pohon Degree sebuah pohon adalah degree tertinggi ( yang mungkin ada ) dari degree simpul yang ada. Untuk pohon yang dicontohkan : Contoh sebuah pohon TREE Derajat = 3 Link, Null- Link dan Bukan Null – Link Link, adalah pointer yang digunakan untuk menunjuk simpul subordinat. Untuk pohon biner yang dicontohkan pada Gambar dibawah ini, maka setiap simpul mempunyai 2 link, sehingga jumlah link = 9 * 2 = 18 pada gambar 3a. Null- Link Null- Link adalah Link yang bernilai Null, yaitu link yang tidak menunjuk simpul subordinat. Untuk pohon biner yang dicontohkan pada gambar 3b, maka jumlah Null- Link ada sebanyak 10 buah. Bukan Null – Link atau Busur Bukan Null-link adalah Link yang menunjuk simpul subordinat atau link yang menghubungkan dua buah simpul yang biasanya disebut busur. Untuk pohon biner yang dicontohkan pada Gambar 3° tersebut, jumlah link yang bukan Null-Link yang disebut busur, ada 8 buah. Gambar 3a Gambar 3b Gambar 3c Contoh : Soal-1. Sebuah pohon M-ary dengan 10 buah simpul. Bila M = 3, maka Ditanya berapa jumlah Null-Link: Beberapa contoh Gambar Pohon 3- ary dengan 10 simpul : Gambar 4a Gambar 4b Pohon 3- ary Skewed Right ( Skewed to the right ) Jawab : Pohon dengan M = 3 Jumlah simpul 10, jadi : n = 10 Jumlah Null - Link = n * ( M – 1 ) + 1 = 10 * ( 3 – 1 ) + 1 = 10 * 2 + 1 = 21 Contoh Soal : Beberapa contoh gambar pohon biner dengan 10 simpul. Gambar 5a Gambar 5b Pohon Biner Skewed Right (Skewed to the right ) Jawab : Pohon Biner, berarti M = 2 Jumlah simpul 10, Jadi : n = 10 Jumlah Null – Link = n * ( M – 1 ) + 1 = 10 * ( 2 – 1) + 1 = 10 * 1 + 1 = 11 Jumlah Null – Link = n * ( M – 1 ) + 1 Jumlah Ditambah 1 Simpul karena simpul terakhir ada tambah 1 Terlihat jelas pada gambar Bahwa setiap simpul ada 1 null link, kecuali simpul terakhir ada 2 link jadi 10 * 1 + 1 = 11 Contoh Soal : Pada sebuah pohon biner, salah satu simpulnya bernomor = 75. Ditanya nomor simpul superordinat simpul tersebut. Jawab : Dari gambar terlihat bahwa nomor simpul superordinat ( parent ) nya = 37 n ? 37 Dengan matematika : 2n +1 = 75 2n = 74 n = 37 2n 2n + 1 75 74 75 Gambar 6a Gambar 6b Gambar 6c Contoh Soal : Diketahui sebuah Phon Biner kedalaman d = 3 Ditanya : a. Maksimum jumlah simpul pada level 3. .............................. Jawab : 8 b. Minimum jumlah simpul pada level 3. ............................. Jawab : 1 c. Maksimum jumlah seluruh simpul sampai dengan level 3. ... Jawab : 15 d. Minimum jumlah seluruh simpul sampai dengan level 3. .... Jawab : 4 Keterangan : Ada banyak sekali bentuk pohon biner yang mempunyai kedalaman = 3 Beberapa diantaranya diperlihatkan pada gambar : Gambar 6a Gambar 6b Gambar 6c Gambar 6d Gambar 6e Gambar 6f Gambar 6g Gambar gh Gambar 6i Dari gambar diatas, dapat dilihat jawaban untuk masing-masing pertanyaan sebagai berikut : a. Maksimum jumlah simpul pada level 3 adalah = 8 ( lihat gambar 6a) b. Minimum jumlah simpul pada level 3 adalah = 1 ( lihat gambar 6d, e, f, g, h, i ) c. Maksimum jumlah seluruh simpul sampai dengan level 3 adalah = 15 ( gambar 6a ) d. Minimum jumlah seluruh simpul sampai dengan level 3 adalah = ( lihat gambar 6g, h, i ). Level Maksimum jumlah simpul pada level Maksimum jumlah seluruh simpul sampai dengan level 0 1 1 1 2 3 2 4 7 3 8 15 4 16 31 5 32 63 6 64 127 7 128 255 8 256 511 9 512 1023 10 1024 2047 11 2048 4095 12 4096 8191 13 8196 16383 14 16394 32767 . . . . . . . . . k 2^k 2^(k+1)-1 Dari tabel diatas dapat dijawab : a. Maksimum jumlah simpul pada level 9 = 512 b. Maksimum jumlah seluruh simpul sampai dengan level 9 = 1023 Sedangkan : c. Minimum jumlah simpul pada level 9 = 1 d. Minimum jumlah seluruh simpul sampai dengan level 9 = 10 Sampai level 14 jumlah simpul maksimum = 32767. Ingat batas maksimal bilangan signed integer 16 bit.


POHON ( TREE )

Pengertian  Pohon

Pohon  atau tree adalah salah satu bentuk konsep struktur data yang terdiri dari akar dan simpul-simpul yang berada dibawah akar.


*                  Selain istilah tingkat juga ada yang disebut dengan derajat ( degree ).
*                  Derajat merupakan banyak tingkat simpul turunan dari satu simpul tertentu, misalkan  simpul tertentu, misalkan simpul “ Ketua Umum” memiliki derajat 3, simpul “ wakil Ketua I “ memiliki derajat 2 dan seterusnya.
*                  Simpul yang memiliki derajat 0 disebut dengan daun ( leaf), pada struktur data pohon dikenal istilah yang disebut  kedalaman  ( depth ).
*                  Sedangkan sebuah simpul yang ada diatas sebuah simpul lain disebut sebagai ancestor.
*                  Kumpulan pohon disebut dengan hutan ( forest ).


Ada beberapa cara untuk menggambarkan sebuah pohon yaitu :


Keterangan

Representasi Pohon

Menggunakan graph







Flowchart: Connector: A











Menggunakan diagram venn









Flowchart: Connector: A












Menggunakan notasi kurung


( A, ( B ( E, F ), c ( G), D( H, I ) )
Pohon biner lengkap
( complete binary tree ) yaitu pohon bier yang setiap simpulnya mempunyai dua buah simpul turunan.





Pohon biner condong kiri
( leaft skewed binary tree )





Flowchart: Connector: A 

Pohon biner condong kanan
( right skewed binary tree )
 





Flowchart: Connector: A






Flowchart: Connector: C
Pohon biner sembarang








Flowchart: Connector: FFlowchart: Connector: EFlowchart: Connector: DFlowchart: Connector: CFlowchart: Connector: BFlowchart: Connector: A


Operasi  Pada  Pohon  Biner


Operasi pada pohon biner :
-          Operasi yang dapat dilakukan pada pohon biner antara lain kunjungan terhadap simpul simpulnya.

Jenis-jenis kunjunfan pada pohon biner antara lain :
-          Preorder
-          Inorder
-          Postorder
-          Level order


Pre Order
            Kunjungan preorder merupakan kunjungan pada pohon biner yang dimulai dari akar kemudian ke subpohon kiri, setelah subpohon  kiri  dikunjungi  baru  subpohon  kanan dikunjungi.






Maka dengan kunjungan preorder  akan  menghasilkan  urutan  simpul  yang dikunjungi
A – B – D – E – C – F – G – H
In Order
          Kunjungan inorder merupakan kunjungan pada pohon biner yang dimulai dari simpul-simpul turunan subpohon kiri, akar, baru kemudian simpul-simpul turunan pada subpohon kanan.


 

         






Maka  kunjungan  inoeder  akan  menghasilkan urutan simpul :
   D – B – E – A – F – C – H – G


Post Order
            Kunjungan post order merupakan kunjungan pada pohon biner yang dimulai dari simpul-simpul turunan subpohon kiri, baru kemudian simpul-simpul turunan pada subpohon kanan, Kemudian akar, misalkan terdapat sebuah pohon biner seperti pada gambar
 








Post Order akan menghasilkan urutan simpul yang dikunjungi :
          D – E – B – F – H – G – C – A


Level  Order
          Kunjungan level order merupakan kunjungan pada pohon biner yang dimulai dari simpul pada tingkat  1  kemudian  simpul-simpul pada tingkat 2  dan seterusnya., dimulai dari simpul  paling kiri ke kanan.

Kunjungan level order akan menghasilkan urutan simpul
A-    B- C – D – E – F – G – H



Implementasi Pohon  Biner
Flowchart: Predefined Process: Struktur data                                                                     simpul                                                                   Pointer sub pohon
 kanan
   pointer
 subpohon kiri


sehingga jika di implementasikan sebagai pohon , simpul-simpul itu akan menjadi
seperti :



Flowchart: Predefined Process: A
 

                                                                                   
Flowchart: Predefined Process: BFlowchart: Predefined Process: EFlowchart: Predefined Process: DFlowchart: Predefined Process: B                                                                                                                      
                                                                                                                   

Flowchart: Predefined Process: B                                                                Null                              






Null                          Null   Null                        Null            Null                           Null

( Representasi Pohon Biner )


Pohon Tree
          Struktur data berbentuk Tree dapat diartikan bahwa relasi antar elemen adalah hierarkis.  Selalu  terdapat satu elemen sebagai akar ( roots ) dan diikuti oleh elemen-elemen sebagai cabang-cabang.

Record mahasiswa dengan atribut :
           
            Nomorpokok,
            Nama,
            Alamat,
            Jurusan,











 
















Hierarki mahasiswa dapat ditulis dalam bentuk Record terstruktur :

01      Mahasiswa
02    Nomorpokok
02  Nama
            03  Depan
            03  Famili
            03  Alias
02  Jurusan
02  Alamat
           03  Jalan
           03  Area
                      04  Kota
                      04  Negara
                      04  Kodepos














Contoh :
            Hierarki  dipergunakan juga untuk menggambarkan formulasi aljabar :
                        f(x)  =  ( 2x + y )  ( a – 7b )3
            seperti :                                                                                     level 0
                                            v0


 

                                         e2
                    e0                              e1                     
C
 
                                                                                         Level 1
                    V1                    v2                                  v3

                                                                                            Level 2



                                                                                                     Level 3



Tree atau Pohon

          Termasuk struktur data non linear.


Tree ,  M-Ary tree  dan  Binary Tree

Contoh sebuah Tree :
                                                                                         Level 0
                                           V0                           e2                                
                                                
                                e0                    e1                                                                            Level 1
                                                                                                                    v3
                                   v1                    v2                                                                              level 2




                                                                                                                             Level 3



Ada banyak nama, istilah dan pengertian yang digunakan untuk mengilustrasikan atau menyatakan  ataupun yang dikaitkan dengan pohon , antara lain :
a.       Tree ( pohon  )  dan Graph ( Grafik )
b.      Simpul ( Vertex, Node ), dan  Busur ( Edge, Arch )
c.       Superordinat dan Subordinat, father dan son, parent dan children
d.      Root ( akar ) dan Leap ( Daun )
e.       Level ( Tingkat ) dan Depth ( kedalaman )
f.       Degree ( derajat simpul dan Degree pohon
g.      M- ary tree dan Binary tree.
h.      Link  dan  Null- Link.


Istilah-istilah  diatas dapat diuraikan sebagai :
a.      Tree  dan  graph
Tree  merupakan  bagian  dari Graph


 

      T = ÃŽ G


b.      Simpul dan  Busur
Pohon merupakan kumpulan dari simpul dan busur, dimana salah satu simpul merupakan akar  ( Root )  dan simpul – simpul  lain  membentuk  suatu subpohon  atau  subtree yang dapat disimbolkan sebagai berikut :
     
      T =  ( V, E )


Dimana :
              V = Vertex,  atau  Node  atau titik  atau  simpul.
              E =  Edge,  atau  Arc  atau Busur.


Simpul
Disini  digunakan istilah vertex, yang disimbolkan dengan huruf  besar.   Tree terdiri  dari 14  buah  simpul  ( n = 14 ) yaitu simpul A sampai dengan simpul N, atau V0  sampai dengan  v13, yang disimbolkan sebagai berikut :
        V  =  { v0 , v1 , v2 , ……….,  v13 }
Yang maksudnya  v  terdiri dari atau merupakan kumpulan  dari  v0 , v1, …..

Busur
Disini digunakan istilah Edge yang disimbolkan dengan huruf  E  besar, Tree terdiri dari 13 buah busur ( m = 12 )  yaitu  e 0  sampai dengan  e13  yang disimbolkan sebagai berikut :
                  E =  {  e0 , e1,  e2,  ………, e12 }
Yang maksudnya  E  teridiri  dari  atau  merupakan  kumpulan                                  dari e0 , e1,  e2,  ………, e12.
Bila jumlah simpul dinyatakan dengan  :  n
Dan  jumlah  busur  dinyatakan  dengan : m
Maka selalu berlaku hubungan               : m = n -1

c.   Superordinat
      Untuk contoh pohon diatas :
-          Simpul  B  merupakan  superordinat  simpul  E  dan  F.
-          Simpul  E dan  F  mempunyai  superordinat  simpul  B

Superordinat  diistilahkan  dengan Father ( Bapak )  dan Subordinat diistilahkan  dengan  Son ( Anak ).  Ada yang mengistilahkan dengan  Parent  dan Children.


d.      Root ( Akar )  dan  Leaf  ( Daun )
Root ( Akar ) adalah simpul yang tak mempunyai superordinat.  Untuk pohon yang dicontohkan diatas maka akar adalah  simpul  A.

Leaf ( Daun )  adalah simpul yang tak mempunyai subordinat.  Untuk  pohon yang dicontohkan diatas, maka daun adalah :
      simpul  C, E, G, I, J, K, L, M, N

e.       Level  ( Tingkat )  dan  Depth ( Kedalaman )

Akar dinyatakan  berada pada level 0, atau  disebut level 1.  Setiap turun  satu  subordinat,  level bertambah  1.

Depth ( Kedalaman )  disebut ketinggian  ( height )
Suatu pohon yang mempunyai level teratas atau level tertinggi = k ,  maka disebut kedalamannya =  k.     Untuk  pohon 
yang dicontohkan diatas, karena level tertinggi adalah 3,  maka  depth = 3

f.       Degree ( derajat ) sebuah simpul
Degree sebuah simpul menyatakan jumlah simpul subordinat dari simpul tersebut:
Untuk  pohon yang dicontohkan pada gambar dibawah ini :
             Simpul  A  :  degree  = 3
             Simpul  B  :  degree  = 2
             Simpul  C :   degree  = 0

Degree sebuah pohon
             Degree sebuah pohon adalah degree tertinggi ( yang mungkin ada ) dari degree simpul yang ada.  Untuk pohon yang dicontohkan :

Contoh sebuah pohon  TREE
Derajat  = 3





Flowchart: Connector: +Flowchart: Connector: +Flowchart: Connector: +Flowchart: Connector: +Flowchart: Connector: BFlowchart: Connector: JFlowchart: Connector: IFlowchart: Connector: FFlowchart: Connector: KFlowchart: Connector: HFlowchart: Connector: GFlowchart: Connector: D  Flowchart: Connector: EFlowchart: Connector: CFlowchart: Connector: A                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       

Link,  Null- Link  dan  Bukan  Null – Link

Link, adalah pointer yang digunakan untuk menunjuk simpul subordinat. Untuk pohon biner yang dicontohkan pada Gambar dibawah ini, maka setiap simpul  mempunyai 2  link, sehingga jumlah link = 9 * 2 = 18  pada gambar 3a.


Null- Link
       Null- Link adalah Link yang bernilai Null, yaitu link yang tidak menunjuk simpul subordinat.  Untuk pohon biner yang dicontohkan pada gambar 3b,  maka jumlah  Null- Link ada sebanyak  10 buah.
















Bukan  Null – Link atau  Busur
          Bukan Null-link adalah  Link yang menunjuk simpul subordinat atau link yang menghubungkan dua buah simpul yang biasanya disebut busur.  Untuk pohon biner yang dicontohkan pada Gambar 3° tersebut, jumlah link yang bukan  Null-Link  yang disebut busur, ada 8 buah.











 
















             Gambar 3a                               Gambar 3b                                           Gambar 3c
























Contoh :
Soal-1.      Sebuah pohon  M-ary dengan 10 buah simpul.
                 Bila  M = 3,  maka  Ditanya berapa jumlah  Null-Link:

                 Beberapa contoh Gambar Pohon 3- ary dengan 10 simpul :






 



Flowchart: Connector: CFlowchart: Connector: FFlowchart: Connector: B                                                                                      
Flowchart: Connector: DFlowchart: Connector: CFlowchart: Connector: JFlowchart: Connector: HFlowchart: Connector: GFlowchart: Connector: IFlowchart: Connector: E                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Gambar 4a 













                                                                                                                        Gambar 4b
                                                                                                 Pohon 3- ary Skewed Right
                                                                                                 ( Skewed to the right )
Jawab :
Pohon dengan  M = 3
Jumlah simpul 10,  jadi :  n = 10
Jumlah  Null -  Link =  n *  ( M – 1 ) + 1
                                 =  10  *  ( 3 – 1 ) + 1
                                 =  10 *  2  +  1
                                 =  21



Contoh Soal :

Beberapa contoh gambar pohon biner dengan 10 simpul.







Flowchart: Connector: H

 


Flowchart: Connector: AFlowchart: Connector: DFlowchart: Connector: JFlowchart: Connector: IFlowchart: Connector: HFlowchart: Connector: FFlowchart: Connector: CFlowchart: Connector: GFlowchart: Connector: EFlowchart: Connector: B                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Gambar 5a                                                                                                                                                                                                                                                                                                                                                   Gambar 5b
                                                                    Pohon  Biner Skewed Right
                                                                    (Skewed  to the right )


Flowchart: Connector: B
 


Flowchart: Connector: C                                                   Jawab :
                                                   Pohon  Biner, berarti M = 2
                                                   Jumlah simpul 10, Jadi :  n = 10
Flowchart: Connector: D                                                   Jumlah  Null – Link  = n *  ( M – 1 ) + 1
                                                                                     = 10 * ( 2 – 1) + 1
Flowchart: Connector: JFlowchart: Connector: IFlowchart: Connector: HFlowchart: Connector: GFlowchart: Connector: FFlowchart: Connector: E                                                                                     = 10 * 1 + 1