เมื่อจำเป็นต้องสร้างไบนารีทรีโดยรับอินพุตโดยใช้การข้ามผ่านแบบ inorder หรือ postorder คลาสถูกกำหนด ซึ่งมีวิธีการตั้งค่าองค์ประกอบรูท ดำเนินการข้ามผ่านคำสั่ง ดำเนินการผ่านคำสั่งภายหลัง สามารถใช้ได้โดยการสร้างอินสแตนซ์ของคลาส
ด้านล่างนี้เป็นการสาธิตสิ่งเดียวกัน -
ตัวอย่าง
class BinaryTree_struct:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None
def set_root(self, key):
self.key = key
def inorder_traversal(self):
if self.left is not None:
self.left.inorder_traversal()
print(self.key, end=' ')
if self.right is not None:
self.right.inorder_traversal()
def post_order_traversal(self):
if self.left is not None:
self.left.post_order_traversal()
if self.right is not None:
self.right.post_order_traversal()
print(self.key, end=' ')
def construct_btree(post_ord, in_ord):
if post_ord == [] or in_ord == []:
return None
key = post_ord[-1]
node = BinaryTree_struct(key)
index = in_ord.index(key)
node.left = construct_btree(post_ord[:index], in_ord[:index])
node.right = construct_btree(post_ord[index:-1], in_ord[index + 1:])
return node
post_ord = input('The input for post-order traversal is : ').split()
post_ord = [int(x) for x in post_ord]
in_ord = input('The input for in-order traversal is : ').split()
in_ord = [int(x) for x in in_ord]
my_instance = construct_btree(post_ord, in_ord)
print('Binary tree has been constructed...')
print('Verification in process..')
print('Post-order traversal is... ', end='')
my_instance.post_order_traversal()
print()
print('In-order traversal is... ', end='')
my_instance.inorder_traversal()
print() ผลลัพธ์
The input for post-order traversal is : 1 2 3 4 5 The input for in-order traversal is : 5 4 3 2 1 Binary tree has been constructed... Verification in process.. Post-order traversal is... 1 2 3 4 5 In-order traversal is... 5 4 3 2 1
คำอธิบาย
-
คลาส 'BinaryTree_struct' พร้อมแอตทริบิวต์ที่จำเป็นจะถูกสร้างขึ้น
-
มีฟังก์ชัน 'init' ที่ใช้ตั้งค่าโหนดซ้ายและขวาเป็น 'ไม่มี'
-
มันมีเมธอด 'set_root' ที่ช่วยตั้งค่ารูทของไบนารีทรี
-
อีกวิธีหนึ่งที่ชื่อว่า 'inorder_traversal' ซึ่งดำเนินการข้ามผ่านตามลำดับ เช่น ซ้าย→โหนด→ขวา
-
มีการกำหนดวิธีการอื่นที่ชื่อว่า 'post_order_traversal' ซึ่งช่วยในการสำรวจต้นไม้ตามลำดับหลัง เช่น ซ้าย→ขวา→โหนด
-
มีการกำหนดวิธีการชื่อ 'construct_btree' ซึ่งช่วยสร้างไบนารีทรีโดยใช้องค์ประกอบที่ได้ระบุไว้ก่อนหน้านี้
-
มีการกำหนดเมธอดที่ชื่อว่า "search_elem" ซึ่งช่วยในการค้นหาองค์ประกอบเฉพาะ
-
วัตถุของคลาส 'BinaryTree_struct' ถูกสร้างขึ้น
-
วิธี 'construct_btree' ใช้เพื่อสร้างไบนารีทรีโดยใช้องค์ประกอบที่ระบุไว้ก่อนหน้านี้
-
การดำเนินการผ่านรายการผ่านรายการและการข้ามผ่านคำสั่งจะดำเนินการบนทรีนี้
-
เอาต์พุตที่เกี่ยวข้องจะแสดงบนคอนโซล
