Page: Tree in Python
Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :
- Prodecessor : node yang berada diatas node tertentu.
- Successor : node yang berada di bawah node tertentu.
- Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
- Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
- Parent : predecssor satu level di atas suatu node.
- Child : successor satu level di bawah suatu node.
- Sibling : node-node yang memiliki parent yang sama dengan suatu node.
- Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
- Size : banyaknya node dalam suatu tree.
- Height : banyaknya tingkatan/level dalam suatu tree.
- Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
- Leaf : node-node dalam tree yang tak memiliki seccessor.
- Degree : banyaknya child yang dimiliki suatu node.
Membuat Root
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def PrintTree(self):
print(self.data)
root = Node(10)
root.PrintTree()
Insert ke Tree
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def insert(self, data):
# Compare the new value with the parent node
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()
Melintasi/Traversal Elemen Tree
Traversal adalah proses untuk mengunjungi semua simpul pohon dan dapat mencetak nilainya juga. Karena, semua node terhubung melalui edge (tautan) kita selalu mulai dari root (head) node. Yaitu, kita tidak dapat secara acak mengakses sebuah simpul di pohon. Ada tiga cara yang digunakan untuk melintasi pohon
- In-order Traversal
- Pre-order Traversal
- Post-Order Traversal
Dalam metode traversal ini, subtree kiri dikunjungi terlebih dahulu, kemudian root dan kemudian sub-tree kanan. Kita harus selalu ingat bahwa setiap node dapat mewakili subtree itu sendiri. Dalam program python di bawah ini, kita menggunakan kelas Node untuk membuat tempat dudukan untuk simpul root serta simpul kiri dan kanan. Lalu kita membuat fungsi menyisipkan untuk menambahkan data ke pohon.Akhirnya logika traversal In-order diimplementasikan dengan membuat daftar kosong dan menambahkan node kiri pertama diikuti oleh root atau node induk. Akhirnya node kiri ditambahkan untuk menyelesaikan Inorder traversal. Harap dicatat bahwa proses ini diulang untuk setiap sub-pohon sampai semua node dilintasi.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Inorder traversal
# Left -> Root -> Right
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))
Ketika kode di atas dieksekusi, ia menghasilkan hasil sebagai berikut[10, 14, 19, 27, 31, 35, 42]
Dalam metode traversal ini, simpul akar dikunjungi terlebih dahulu, kemudian subtree kiri dan akhirnya subtree kanan.
Dalam program python di bawah ini, kami menggunakan kelas Node untuk membuat tempat dudukan untuk simpul root serta simpul kiri dan kanan. Lalu kami membuat fungsi menyisipkan untuk menambahkan data ke pohon.Akhirnya logika traversal Pre-order diimplementasikan dengan membuat daftar kosong dan menambahkan simpul akar pertama diikuti oleh simpul kiri.Akhirnya simpul kanan ditambahkan untuk menyelesaikan traversal Pre-order.Harap dicatat bahwa proses ini diulang untuk setiap sub-pohon sampai semua node dilintasi.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Preorder traversal
# Root -> Left ->Right
def PreorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.PreorderTraversal(root.left)
res = res + self.PreorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))
Ketika kode di atas dieksekusi, ia menghasilkan hasil sebagai berikut -
[27, 14, 10, 19, 35, 31, 42]
Traversal Post-Order
Dalam metode traversal ini, simpul akar dikunjungi terakhir, karenanya namanya. Pertama kita melintasi subtree kiri, kemudian subtree kanan dan akhirnya node root.
Dalam program python di bawah ini, kami menggunakan kelas Node untuk membuat tempat dudukan untuk simpul root serta simpul kiri dan kanan. Lalu kami membuat fungsi menyisipkan untuk menambahkan data ke pohon.Akhirnya logika traversal Post-order diimplementasikan dengan membuat daftar kosong dan menambahkan node kiri pertama diikuti oleh node kanan.Akhirnya root atau parent node ditambahkan untuk menyelesaikan traversal Post-order. Harap dicatat bahwa proses ini diulang untuk setiap sub-pohon sampai semua node dilintasi.
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))
Ketika kode di atas dieksekusi, ia menghasilkan hasil sebagai berikut -
[10, 19, 14, 31, 42, 35, 27]
Tidak ada komentar:
Posting Komentar