โปรแกรม Python สร้าง Binary Tree จาก Inorder และ Postorder Traversal

เมื่อได้รับ Inorder traversal และ Postorder traversal สามารถสร้าง Binary Tree กลับมาได้ (เพราะ 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: โหนดของ binary tree มี key, left, right

• เมธอด inorder_traversal: Left → Node → Right

• เมธอด post_order_traversal: Left → Right → Node

• ฟังก์ชัน construct_btree: สร้างต้นไม้แบบ recursive

  • Root = ตัวสุดท้ายของ postorder
  • หา root ใน inorder → ดัชนี index

  • Left subtree: postorder[:index], inorder[:index]
  • Right subtree: postorder[index:-1], inorder[index+1:]

• โปรแกรมรับ input จากผู้ใช้ แล้วสร้างต้นไม้และตรวจสอบด้วยการ traverse กลับ

เงื่อนไข: ค่าของโหนดต้องไม่ซ้ำกัน (unique values) มิฉะนั้น in_ord.index(key) จะหาไม่ถูกต้อง