Python - Tree Traversal อัลกอริทึม
Traversal เป็นกระบวนการในการเยี่ยมชมโหนดทั้งหมดของต้นไม้และอาจพิมพ์ค่าของมันด้วย เนื่องจากโหนดทั้งหมดเชื่อมต่อผ่านขอบ (ลิงค์) เรามักจะเริ่มต้นจากโหนดรูท (หัว) นั่นคือเราไม่สามารถสุ่มเข้าถึงโหนดในทรีได้ มีสามวิธีที่เราใช้ในการสำรวจต้นไม้ -
- In-order Traversal
- พรีออเดอร์ Traversal
- Post-order Traversal
In-order Traversal
ในวิธีการข้ามผ่านนี้ทรีย่อยด้านซ้ายจะถูกเยี่ยมชมก่อนจากนั้นจึงไปที่รูทและตามมาในแผนผังย่อยด้านขวา เราควรจำไว้เสมอว่าทุกโหนดอาจเป็นตัวแทนของทรีย่อยเอง
ในโปรแกรม python ด้านล่างเราใช้คลาส Node เพื่อสร้างตัวยึดตำแหน่งสำหรับโหนดรูทรวมทั้งโหนดซ้ายและขวา จากนั้นเราสร้างฟังก์ชันแทรกเพื่อเพิ่มข้อมูลให้กับต้นไม้ ในที่สุดตรรกะการข้ามผ่าน Inorder จะถูกนำไปใช้โดยการสร้างรายการว่างและเพิ่มโหนดทางซ้ายก่อนตามด้วยรูทหรือโหนดหลัก ในที่สุดโหนดด้านซ้ายจะถูกเพิ่มเพื่อให้การข้ามผ่าน Inorder เสร็จสมบูรณ์ โปรดทราบว่ากระบวนการนี้ซ้ำสำหรับแต่ละแผนผังย่อยจนกว่าโหนดทั้งหมดจะถูกข้ามผ่าน
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))
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
[10, 14, 19, 27, 31, 35, 42]
พรีออเดอร์ Traversal
ในวิธีการข้ามผ่านนี้โหนดรูทจะถูกเยี่ยมชมก่อนจากนั้นทรีย่อยด้านซ้ายและสุดท้ายคือทรีย่อยด้านขวา
ในโปรแกรม python ด้านล่างเราใช้คลาส Node เพื่อสร้างตัวยึดตำแหน่งสำหรับโหนดรูทรวมทั้งโหนดซ้ายและขวา จากนั้นเราสร้างฟังก์ชันแทรกเพื่อเพิ่มข้อมูลให้กับต้นไม้ ในที่สุดตรรกะการส่งผ่านคำสั่งซื้อล่วงหน้าก็ถูกนำมาใช้โดยการสร้างรายการว่างและเพิ่มโหนดรูทก่อนตามด้วยโหนดด้านซ้าย ในที่สุดโหนดด้านขวาจะถูกเพิ่มเพื่อให้การส่งผ่านคำสั่งซื้อล่วงหน้าเสร็จสมบูรณ์ โปรดทราบว่ากระบวนการนี้ซ้ำสำหรับแต่ละแผนผังย่อยจนกว่าโหนดทั้งหมดจะถูกข้ามผ่าน
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))
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
[27, 14, 10, 19, 35, 31, 42]
Post-order Traversal
ในวิธีการข้ามผ่านนี้โหนดรูทจะถูกเยี่ยมชมเป็นครั้งสุดท้ายดังนั้นชื่อ อันดับแรกเราสำรวจทรีย่อยด้านซ้ายจากนั้นทรีย่อยด้านขวาและสุดท้ายโหนดรูท
ในโปรแกรม python ด้านล่างเราใช้คลาส Node เพื่อสร้างตัวยึดตำแหน่งสำหรับโหนดรูทรวมทั้งโหนดซ้ายและขวา จากนั้นเราสร้างฟังก์ชันแทรกเพื่อเพิ่มข้อมูลให้กับต้นไม้ ในที่สุดลอจิกการข้ามผ่านหลังคำสั่งจะถูกนำมาใช้โดยการสร้างรายการว่างและเพิ่มโหนดด้านซ้ายก่อนตามด้วยโหนดด้านขวา ในที่สุดรูทหรือโหนดพาเรนต์จะถูกเพิ่มเพื่อให้การส่งผ่านหลังคำสั่งซื้อเสร็จสมบูรณ์ โปรดทราบว่ากระบวนการนี้ซ้ำสำหรับแต่ละแผนผังย่อยจนกว่าโหนดทั้งหมดจะถูกข้ามผ่าน
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))
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
[10, 19, 14, 31, 42, 35, 27]