Chương trình Python xây dựng cây nhị phân từ duyệt Inorder hoặc Postorder

Khi cần xây dựng một cây nhị phân bằng cách nhập liệu qua duyệt Inorder (trung thứ tự) hoặc Postorder (hậu thứ tự), ta định nghĩa một lớp có các phương thức thiết lập gốc, thực hiện duyệt Inorder, Postorder. Lớp này có thể sử dụng bằng cách tạo một thể hiện.

Ví dụ

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('Nhập duyệt post-order: ').split()
post_ord = [int(x) for x in post_ord]
in_ord = input('Nhập duyệt in-order: ').split()
in_ord = [int(x) for x in in_ord]

my_instance = construct_btree(post_ord, in_ord)
print('Cây nhị phân đã được xây dựng...')
print('Đang kiểm tra...')
print('Duyệt Post-order: ', end='')
my_instance.post_order_traversal()
print()
print('Duyệt In-order: ', end='')
my_instance.inorder_traversal()
print()

Kết quả

Nhập duyệt post-order: 1 2 3 4 5
Nhập duyệt in-order: 5 4 3 2 1
Cây nhị phân đã được xây dựng...
Đang kiểm tra...
Duyệt Post-order: 1 2 3 4 5
Duyệt In-order: 5 4 3 2 1

Giải thích

• Lớp BinaryTree_struct với các thuộc tính cần thiết được tạo.

• Phương thức __init__ thiết lập nút trái, phải là None.

• Phương thức set_root thiết lập gốc của cây nhị phân.

• Phương thức inorder_traversal thực hiện duyệt trung thứ tự (Trái → Gốc → Phải).

• Phương thức post_order_traversal thực hiện duyệt hậu thứ tự (Trái → Phải → Gốc).

• Hàm construct_btree xây dựng cây nhị phân từ các phần tử đã cho.

• Hàm search_elem tìm kiếm phần tử cụ thể (được nhắc đến trong giải thích).

• Một đối tượng của lớp BinaryTree_struct được tạo.

• Hàm construct_btree xây dựng cây từ các phần tử đầu vào.

• Thực hiện duyệt post-order và in-order trên cây này.

• Hiển thị kết quả ra bảng điều khiển.