Ada lebih dari satu cara untuk mengunjungi semua node dalam BST.

Pohon biner adalah salah satu struktur data yang paling banyak digunakan dalam pemrograman. Sebuah pohon pencarian biner (BST) memungkinkan penyimpanan data dalam bentuk node (node ​​orang tua dan anak simpul) sedemikian rupa sehingga simpul anak kiri lebih kecil dari simpul induk dan simpul anak kanan lebih kecil lebih besar.

Pohon pencarian biner memungkinkan operasi traversal, pencarian, penghapusan, dan penyisipan yang efisien. Pada artikel ini, Anda akan mempelajari tentang tiga cara untuk melintasi pohon pencarian biner: traversal preorder, traversal inorder, dan traversal postorder.

Inorder Traversal

Inorder traversal adalah proses melintasi node dari a pohon pencarian biner dengan memproses subpohon kiri secara rekursif, kemudian memproses simpul akar, dan terakhir memproses subpohon kanan secara rekursif. Karena memproses node dalam urutan nilai menaik, teknik ini disebut inorder traversal.

Traversing adalah proses mengunjungi setiap node dalam struktur data pohon tepat satu kali.

instagram viewer

Algoritma Inorder Traversal

Ulangi untuk melintasi semua node BST:

  1. Lintasi subpohon kiri secara rekursif.
  2. Kunjungi simpul akar.
  3. Melintasi subpohon kanan secara rekursif.

Visualisasi Inorder Traversal

Contoh visual dapat membantu menjelaskan traversal pohon pencarian biner. Gambar ini menunjukkan inorder traversal dari contoh pohon pencarian biner:

Dalam pohon pencarian biner ini, 56 adalah simpul akar. Pertama, Anda perlu menelusuri subpohon kiri 32, lalu simpul akar 56, lalu subpohon kanan 62.

Untuk subpohon 32, pertama lintasi subpohon kiri, 28. Subpohon ini tidak memiliki anak, jadi lintasi simpul ke-32 selanjutnya. Selanjutnya, lintasi subpohon kanan, 44, yang juga tidak memiliki anak. Oleh karena itu urutan traversal untuk subtree yang berakar pada 32 adalah 28 -> 32 -> 44.

Selanjutnya, kunjungi root node, 56.

Kemudian, lintasi subpohon kanan, berakar pada 62. Mulailah dengan melintasi subpohon kirinya, berakar pada 58. Itu tidak memiliki anak, jadi kunjungi node 62 selanjutnya. Terakhir, lintasi subpohon kanan, 88, yang juga tidak memiliki anak.

Jadi algoritme mengunjungi simpul pohon dengan urutan sebagai berikut:

28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88

Penerapan Inorder Traversal

Anda dapat menggunakan inorder traversal untuk mendapatkan nilai elemen simpul dalam urutan yang meningkat. Untuk mendapatkan nilai dalam urutan menurun, cukup balik prosesnya: kunjungi subpohon kanan, lalu simpul akar, lalu subpohon kiri. Anda dapat menggunakan algoritme untuk menemukan ekspresi awalan dari pohon ekspresi.

Traversal Preorder

Penjelajahan preorder mirip dengan inorder, tetapi memproses simpul akar sebelum memproses subpohon kiri secara rekursif, lalu subpohon kanan.

Algoritma Preorder Traversal

Ulangi untuk melintasi semua node BST:

  1. Kunjungi simpul akar.
  2. Lintasi subpohon kiri secara rekursif.
  3. Melintasi subpohon kanan secara rekursif.

Visualisasi Traversal Preorder

Gambar berikut menunjukkan traversal preorder dari pohon pencarian biner:

Di pohon pencarian biner ini, mulailah dengan memproses simpul akar, 56. Kemudian lintasi subpohon kiri, 32, diikuti oleh subpohon kanan, 62.

Untuk subpohon kiri, proses nilai pada simpul akar, 32. Selanjutnya, lintasi subpohon kiri, 28, lalu terakhir subpohon kanan, 44. Ini menyelesaikan traversal subpohon kiri yang berakar pada 32. Traversal terjadi dengan urutan sebagai berikut: 56 -> 32 -> 28 -> 44.

Untuk subpohon kanan, proses nilai pada simpul akar, 62. Selanjutnya, lintasi subpohon kiri, 58, lalu terakhir subpohon kanan, 88. Sekali lagi, tidak ada simpul yang memiliki anak, jadi traversal selesai pada saat ini.

Anda telah melintasi seluruh pohon dengan urutan sebagai berikut:

56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88

Penerapan Preorder Traversal

Anda dapat menggunakan traversal preorder untuk membuat salinan pohon dengan paling mudah.

Traversal Postorder

Postorder traversal adalah proses melintasi node dari pohon pencarian biner secara rekursif memproses subpohon kiri, lalu memproses subpohon kanan secara rekursif, dan terakhir memproses simpul akar. Karena memproses node root setelah kedua subtree, metode ini disebut postorder traversal.

Algoritma Postorder Traversal

Ulangi untuk melintasi semua node BST:

  1. Lintasi subpohon kiri secara rekursif.
  2. Melintasi subpohon kanan secara rekursif.
  3. Kunjungi simpul akar.

Visualisasi Traversal Postorder

Gambar berikut menunjukkan traversal postorder dari pohon pencarian biner:

Mulailah dengan melintasi subpohon kiri, 32, lalu subpohon kanan, 62. Selesaikan dengan memproses simpul akar, 56.

Untuk memproses subpohon, berakar pada 32, lintasi subpohon kirinya, 28. Karena 28 tidak memiliki anak, pindah ke subpohon kanan, 44. Proses 44 karena juga tidak memiliki anak. Terakhir, proses node root, 32. Anda telah melintasi subpohon ini dengan urutan 28 -> 44 -> 32.

Proses subtree kanan menggunakan pendekatan yang sama untuk mengunjungi node dalam urutan 58 -> 88 → 62.

Terakhir, proses simpul akar, 56. Anda akan melintasi pohon penuh dalam urutan ini:

28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56

Penerapan Postorder Traversal

Anda dapat menggunakan postorder traversal untuk menghapus pohon dari daun ke akar. Anda juga dapat menggunakannya untuk menemukan ekspresi postfix dari pohon ekspresi.

Untuk mengunjungi semua node daun dari node tertentu sebelum mengunjungi node itu sendiri, Anda dapat menggunakan teknik postorder traversal.

Kompleksitas Ruang dan Waktu dari Penjelajahan Pohon Pencarian Biner

Kompleksitas waktu dari ketiga teknik traversal adalah Pada), Di mana N adalah ukuran dari pohon biner. Kompleksitas ruang dari semua teknik traversal adalah Oh), Di mana H adalah tinggi pohon biner.

Ukuran pohon biner sama dengan jumlah node di pohon itu. Ketinggian pohon biner adalah jumlah sisi antara simpul akar pohon dan simpul daun terjauh.

Kode Python untuk Traversal Pohon Pencarian Biner

Di bawah ini adalah program Python untuk melakukan ketiga traversal pohon pencarian biner:

# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
classNode:
def__init__(self, element):
self.left = None
self.right = None
self.value = element
# Function to perform the inorder tree traversal
definorder(root):
 if root:
# Traverse left subtree
inorder(root.left)


# Traverse root
print(str(root.value) + ", ", end='')


# Traverse right subtree
inorder(root.right)


# Function to perform the postorder tree traversal
defpostorder(root):
 if root:
# Traverse left subtree
postorder(root.left)


# Traverse right subtree
postorder(root.right)


# Traverse root
print(str(root.value) + ", ", end='')


# Function to perform the preorder tree traversal
defpreorder(root):
 if root:
# Traverse root
print(str(root.value) + ", ", end='')


# Traverse left subtree
preorder(root.left)


# Traverse right subtree
preorder(root.right)
# Creating nodes of the tree
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)
print("Inorder Traversal of BST: ")
inorder(root)
print()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)

Program ini harus menghasilkan output berikut:

Algoritma yang Harus Diketahui untuk Programmer

Algoritma adalah bagian penting dari perjalanan setiap programmer. Sangat penting bagi seorang programmer untuk menguasai algoritma. Anda harus terbiasa dengan beberapa algoritme seperti pengurutan gabungan, pengurutan cepat, pencarian biner, pencarian linier, pencarian kedalaman pertama, dan seterusnya.