Chương trình Python tìm nút thứ N trong duyệt Inorder của cây

Khi cần tìm nút thứ 'n' bằng duyệt Inorder (trung thứ tự) của một cây nhị phân, ta tạo một lớp cây nhị phân với các phương thức thiết lập gốc, thêm phần tử bên trái/phải, thực hiện duyệt Inorder, v.v. Một thể hiện của lớp được tạo và dùng để truy cập các phương thức.

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_nth(self, n):
        return self.inorder_nth_helper_fun(n, [])

    def inorder_nth_helper_fun(self, n, in_ord):
        if self.left is not None:
            temp = self.left.inorder_nth_helper_fun(n, in_ord)
            if temp is not None:
                return temp
        in_ord.append(self)
        if n == len(in_ord):
            return self
        if self.right is not None:
            temp = self.right.inorder_nth_helper_fun(n, in_ord)
            if temp is not None:
                return temp

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

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

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

btree_instance = None
print('Menu (giả sử không có khóa trùng)')
print('insert  at root')
print('insert  left of ')
print('insert  right of ')
print('inorder')
print('quit')

while True:
    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_struct(data)
        suboperation = do[2].strip().lower()
        if suboperation == 'at':
            btree_instance = new_node
        else:
            position = do[4].strip().lower()
            key = int(position)
            ref_node = None
            if btree_instance is not None:
                ref_node = btree_instance.search_elem(key)
            if ref_node is None:
                print('Không tìm thấy khóa.')
                continue
            if suboperation == 'left':
                ref_node.insert_to_left(new_node)
            elif suboperation == 'right':
                ref_node.insert_to_right(new_node)
    elif operation == 'inorder':
        if btree_instance is not None:
            index = int(do[1].strip().lower())
            node = btree_instance.inorder_nth(index)
            if node is not None:
                print('Phần tử thứ n của duyệt inorder: {}'.format(node.key))
            else:
                print('Chỉ số vượt quá chỉ số tối đa có thể.')
        else:
            print('Cây rỗng...')
    elif operation == 'quit':
        break

Kết quả

Menu (giả sử không có khóa trùng)
insert  at root
insert  left of 
insert  right of 
inorder
quit
Bạn muốn làm gì? insert 5 at root
Bạn muốn làm gì? insert 6 left of 5
Bạn muốn làm gì? insert 8 right of 5
Bạn muốn làm gì? inorder 5
Chỉ số vượt quá chỉ số tối đa có thể.
Bạn muốn làm gì? 6 6

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_nth thực hiện duyệt Inorder bằng đệ quy.

• Do đó có hàm hỗ trợ inorder_nth_helper_fun được định nghĩa cùng lúc.

• Phương thức insert_to_right thêm phần tử bên phải gốc.

• Phương thức insert_to_left thêm phần tử bên trái gốc.

• Phương thức search_elem tìm kiếm phần tử cụ thể.

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

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

• Thực hiện thao tác tương ứng.

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