Câu hỏi

Cho một cây nhị phân tìm kiếm (binary search tree), in ra phần tử nhỏ thứ n trong cây này.

Ví dụ: Với cây nhị phân như sau:

        7
   5         9
3     6         10

Phần tử nhỏ nhất (n=1) là 3, phần tử nhỏ thứ 2 là 5, phần tử nhỏ thứ 3 là 6.

Phân tích

Vì đây là cây nhị phân tìm kiếm nên ta luôn có điều kiện bất biến là các đỉnh bên trái luôn luôn nhỏ hơn hoặc bằng, và các đỉnh bên phải luôn luôn lớn hơn hoặc bằng giá trị của đỉnh đang xét.

Do đó, phần tử nhỏ nhất thứ n cũng là phần tử thứ n trong quá trình duyệt cây theo thứ tự trái, giữa, phải, tức là theo cách tìm kiếm ưu tiên chiều sâu (depth first search).

# encoding: utf-8
def solve(root, n):

    def traverse(node, nr_seen):
        '''Trả về (số đỉnh đã qua, và kết quả).'''
        if node is None:
            return nr_seen, None

        # Tìm trong nhánh trái
        nr_seen, answer = traverse(node.left, nr_seen)
        if answer is not None:
            # Tìm thấy kết quả bên nhánh trái.
            return nr_seen, answer

        nr_seen += 1
        if nr_seen == n:
            # Đỉnh hiện tại chính là đỉnh cần tìm.
            return nr_seen, node.value

        # Tìm trong nhánh phải
        nr_seen, answer = traverse(node.right, nr_seen)
        return nr_seen, answer

    nr_seen, answer = traverse(root, 0)
    return answer


class Node(object):

    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


root = Node(7, Node(5, Node(3), Node(6)), Node(9, None, Node(10)))
assert(solve(root, 1) == 3)
assert(solve(root, 2) == 5)
assert(solve(root, 3) == 6)
assert(solve(root, 4) == 7)
assert(solve(root, 5) == 9)
assert(solve(root, 6) == 10)