Dựa trên tính chất của cây tìm kiếm nhị phân, hãy viết hàm minimum(T) và maximum(T) tính giá trị khoá nhỏ nhất và lớn nhất của cây tìm kiếm nhị phân T.

Dựa trên tính chất của cây tìm kiếm nhị phân (BST), giá trị nhỏ nhất của cây sẽ nằm ở nút lá bên trái cùng (nếu có) và giá trị lớn nhất sẽ nằm ở nút lá bên phải cùng (nếu có).

Dưới đây là cài đặt Python cho hai hàm minimum(T) và maximum(T) để tính giá trị khoá nhỏ nhất và lớn nhất của cây tìm kiếm nhị phân T.

class TreeNode:

    def __init__(self, key):

        self.left = None

        self.right = None

        self.val = key

def minimum(T):

    # Duyệt qua các nút con bên trái cho đến khi không còn nút con nào nữa

    while T.left is not None:

        T = T.left

    return T.val

def maximum(T):

    # Duyệt qua các nút con bên phải cho đến khi không còn nút con nào nữa

    while T.right is not None:

        T = T.right

    return T.val

Giải thích:

• Hàm minimum(T) sẽ duyệt qua cây từ nút gốc theo hướng sang trái cho đến khi không còn nút con nào bên trái nữa. Khi đó, nút hiện tại sẽ là nút có giá trị khoá nhỏ nhất của cây.
• Tương tự, hàm maximum(T) sẽ duyệt qua cây từ nút gốc theo hướng sang phải cho đến khi không còn nút con nào bên phải nữa. Khi đó, nút hiện tại sẽ là nút có giá trị khoá lớn nhất của cây.