Chương trình Python tìm giá trị lớn nhất trong cây nhị phân bằng inorder

Duyệt inorder (trái, gốc, phải) để tìm giá trị lớn nhất trong cây nhị phân (không nhất thiết BST).

Ví dụ

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

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

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

    def search(self, key):
        if self.key == key:
            return self
        if self.left:
            res = self.left.search(key)
            if res: return res
        if self.right:
            return self.right.search(key)
        return None

    def inorder_largest(self):
        largest = []
        self._inorder_helper(largest)
        return largest[0]

    def _inorder_helper(self, largest):
        if self.left:
            self.left._inorder_helper(largest)
        if not largest or largest[0] < self.key:
            largest[:] = [self.key]
        if self.right:
            self.right._inorder_helper(largest)

# Demo
root = None
while True:
    cmd = input("Cmd (insert/largest/quit): ").split()
    if not cmd: continue
    if cmd[0] == 'insert':
        val = int(cmd[1])
        node = BinaryTree(val)
        if cmd[2] == 'at':
            root = node
        else:
            parent = root.search(int(cmd[4]))
            if parent:
                if cmd[2] == 'left':
                    parent.insert_left(node)
                else:
                    parent.insert_right(node)
    elif cmd[0] == 'largest':
        if root:
            print("Max:", root.inorder_largest())
        else:
            print("Cây rỗng")
    elif cmd[0] == 'quit':
        break

Kết quả

Cmd (insert/largest/quit): insert 8 at root
Cmd (insert/largest/quit): insert 9 left of 8
Cmd (insert/largest/quit): insert 4 right of 8
Cmd (insert/largest/quit): largest
Max: 9
Cmd (insert/largest/quit): quit

Giải thích

• Inorder traversal duyệt tất cả nút, cập nhật max qua list tham chiếu largest.
• Hàm helper _inorder_helper truyền list để mutable.
• Nếu cây là BST, max là nút ngoài cùng bên phải (O(h)), nhưng cách này áp dụng cho cây thường.
• Menu tương tác.