Chương trình Python triển khai cây nhị phân sử dụng danh sách liên kết

Khi cần triển khai cấu trúc dữ liệu cây nhị phân sử dụng danh sách liên kết, các phương thức đặt nút gốc, thực hiện duyệt in-order, chèn phần tử bên trái nút gốc, chèn phần tử bên phải nút gốc và tìm kiếm giá trị được định nghĩa.

Ví dụ

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 (giả sử không có khóa trùng lặp)')
print('insert  at root')
print('insert  left of ')
print('insert  right of ')
print('quit')
while True:
    print('Duyệt inorder của cây nhị phân: ', end='')
    if btree is not None:
        btree.in_order_traversal()
    print()
    do = input('Bạn muốn làm gì? ').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('Không tồn tại khóa như vậy')
                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

Kết quả

Menu (giả sử không có khóa trùng lặp)
insert  at root
insert  left of 
insert  right of 
quit
Duyệt inorder của cây nhị phân
Bạn muốn làm gì? insert 45 at root
Duyệt inorder của cây nhị phân 45
Bạn muốn làm gì? insert 78 left of 45
Duyệt inorder của cây nhị phân 78 45
Bạn muốn làm gì? insert 90 right of 45
Duyệt inorder của cây nhị phân 78 45 90
Bạn muốn làm gì? quit

Giải thích

• Lớp BinaryTree_structure được tạo.
• Có hàm set_root giúp đặt giá trị gốc cho cây.
• Phương thức in_order_traversal giúp duyệt qua cây theo thứ tự Trái -> Nút -> Phải.
• Phương thức insert_left giúp thêm phần tử bên trái giá trị gốc.
• Phương thức insert_right giúp thêm phần tử bên phải giá trị gốc.
• Phương thức search_val giúp tìm kiếm giá trị trong cây.
• Bốn tùy chọn được đưa ra: insert at root, insert to left of, insert to right of và quit.
• Dựa trên lựa chọn/đầu vào của người dùng, các thao tác tương ứng được thực hiện.
• Kết quả được hiển thị trên console.