Chương trình Python xây dựng cây nhị phân & thực hiện chèn, xóa, hiển thị

Khi cần xây dựng một cây nhị phân (binary tree) và thực hiện các thao tác như chèn phần tử, xóa phần tử và hiển thị các phần tử của cây, ta định nghĩa một lớp (class) chứa các phương thức cần thiết. Một thể hiện (instance) của lớp được tạo và dùng để truy cập các phần tử cũng như thực hiện các thao tác.

Ví dụ

class Tree_struct:
    def __init__(self, data=None, parent=None):
        self.key = data
        self.children = []
        self.parent = parent

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

    def add_node(self, node):
        self.children.append(node)

    def search_node(self, key):
        if self.key == key:
            return self
        for child in self.children:
            temp = child.search_node(key)
            if temp is not None:
                return temp
        return None

    def remove_node(self):
        parent = self.parent
        index = parent.children.index(self)
        parent.children.remove(self)
        for child in reversed(self.children):
            parent.children.insert(index, child)
            child.parent = parent

    def bfs(self):
        queue = [self]
        while queue != []:
            popped = queue.pop(0)
            for child in popped.children:
                queue.append(child)
            print(popped.key, end=' ')

my_instance = None
print('Menu (giả sử không có khóa trùng lặp)')
print('add  at root')
print('add  below ')
print('remove ')
print('display')
print('quit')

while True:
    do = input('Bạn muốn làm gì? ').split()
    operation = do[0].strip().lower()
    if operation == 'add':
        data = int(do[1])
        new_node = Tree_struct(data)
        suboperation = do[2].strip().lower()
        if suboperation == 'at':
            my_instance = new_node
        elif suboperation == 'below':
            position = do[3].strip().lower()
            key = int(position)
            ref_node = None
            if my_instance is not None:
                ref_node = my_instance.search_node(key)
            if ref_node is None:
                print('Không tìm thấy khóa.')
                continue
            new_node.parent = ref_node
            ref_node.add_node(new_node)
    elif operation == 'remove':
        data = int(do[1])
        to_remove = my_instance.search_node(data)
        if my_instance == to_remove:
            if my_instance.children == []:
                my_instance = None
            else:
                leaf = my_instance.children[0]
                while leaf.children != []:
                    leaf = leaf.children[0]
                leaf.parent.children.remove_node(leaf)
                leaf.parent = None
                leaf.children = my_instance.children
                my_instance = leaf
        else:
            to_remove.remove_node()
    elif operation == 'display':
        if my_instance is not None:
            print('Duyệt theo chiều rộng (BFS): ', end='')
            my_instance.bfs()
            print()
        else:
            print('Cây rỗng')
    elif operation == 'quit':
        break

Kết quả

Menu (giả sử không có khóa trùng lặp)
add  at root
add  below 
remove 
display
quit
Bạn muốn làm gì? add 5 at root
Bạn muốn làm gì? add 6 below 5
Bạn muốn làm gì? add 8 below 6
Bạn muốn làm gì? remove 8
Bạn muốn làm gì? display
Duyệt theo chiều rộng (BFS): 5 6
Bạn muốn làm gì? quit

Giải thích

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

• Phương thức __init__ khởi tạo danh sách rỗng.

• Phương thức set_root xác định gốc của cây.

• Phương thức add_node giúp thêm nút vào cây.

• Phương thức search_node giúp tìm kiếm một phần tử cụ thể.

• Phương thức remove_node xóa phần tử khỏi cây.

• Phương thức bfs thực hiện duyệt theo chiều rộng (Breadth First Search).

• Một thể hiện được tạo và gán None.

• Nhập lựa chọn thao tác từ người dùng.

• Thực hiện thao tác tương ứng theo lựa chọn.

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