โปรแกรม Python สร้าง Binary Tree ด้วย Linked List

ภาพรวม

เมื่อต้องการสร้างโครงสร้างข้อมูล Binary Tree โดยใช้ Linked List จะนิยามเมธอดตั้งค่าโหนดราก การท่องไปในลำดับ in-order การแทรกองค์ประกอบทางซ้ายของราก การแทรกทางขวา และการค้นหาค่า

ตัวอย่างโค้ด

class BinaryTree_structure:
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None

    def set_root(self, key):
        self.key = key

    def in_order_traversal(self):
        if self.left is not None:
            self.left.in_order_traversal()
        print(self.key, end=' ')
        if self.right is not None:
            self.right.in_order_traversal()

    def insert_left(self, new_node):
        self.left = new_node

    def insert_right(self, new_node):
        self.right = new_node

    def search_val(self, key):
        if self.key == key:
            return self
        if self.left is not None:
            temp = self.left.search_val(key)
            if temp is not None:
                return temp
        if self.right is not None:
            temp = self.right.search_val(key)
            return temp
        return None

btree = None
print('Menu (this assumes no duplicate keys)')
print('insert  at root')
print('insert  left of ')
print('insert  right of ')
print('quit')
while True:
    print('The inorder traversal of binary tree ', end='')
    if btree is not None:
        btree.in_order_traversal()
    print()
    do = input('What would you like to do? ').split()
    operation = do[0].strip().lower()
    if operation == 'insert':
        data = int(do[1])
        new_node = BinaryTree_structure(data)
        sub_op = do[2].strip().lower()
        if sub_op == 'at':
            btree = new_node
        else:
            position = do[4].strip().lower()
            key = int(position)
            ref_node = None
            if btree is not None:
                ref_node = btree.search_val(key)
            if ref_node is None:
                print('No such key exists')
                continue
            if sub_op == 'left':
                ref_node.insert_left(new_node)
            elif sub_op == 'right':
                ref_node.insert_right(new_node)
    elif operation == 'quit':
        break

ผลลัพธ์ตัวอย่าง

Menu (this assumes no duplicate keys)
insert  at root
insert  left of 
insert  right of 
quit
The inorder traversal of binary tree
What would you like to do? insert 45 at root
The inorder traversal of binary tree 45
What would you like to do? insert 78 left of 45
The inorder traversal of binary tree 78 45
What would you like to do? insert 90 right of 45
The inorder traversal of binary tree 78 45 90
What would you like to do? quit

คำอธิบาย

• สร้างคลาส BinaryTree_structure
• มีฟังก์ชัน set_root ตั้งค่ารากของ Tree
• เมธอด in_order_traversal ท่องต้นไม้แบบ In-order (ซ้าย-โหนด-ขวา)
• เมธอด insert_left เพิ่มองค์ประกอบทางซ้ายของค่าราก
• เมธอด insert_right เพิ่มองค์ประกอบทางขวาของค่าราก
• เมธอด search_val ค้นหาค่าในต้นไม้
• ให้ตัวเลือก 4 อย่าง: insert at root, insert left of, insert right of, quit
• ตาม input/choice ของผู้ใช้ จะทำการดำเนินการตามลำดับ
• แสดงผลลัพธ์บนคอนโซล