Khóa học Python từ Cơ bản đến Nâng cao

Bài 14.2 - Truy vấn tổ tiên sử dụng Python

Khi làm việc với cấu trúc cây, một trong những thao tác quan trọng là truy vấn tổ tiên của một nút nào đó. Điều này thường gặp trong các hệ thống phân cấp như hệ thống thư mục, cây phân loại, hoặc các cây phả hệ.

Trong bài này, bạn sẽ học cách xây dựng cây và triển khai các hàm để truy vấn tổ tiên của một nút bất kỳ trong Python.

Xây dựng cấu trúc cây

Chúng ta sẽ dùng class Node như sau để tạo cây:

class Node:
    def __init__(self, value):
        self.value = value
        self.parent = None
        self.children = []

    def add_child(self, child):
        child.parent = self
        self.children.append(child)

Giải thích:

• Mỗi Node chứa value (giá trị), children (danh sách con) và parent (nút cha).
• Khi thêm con, ta đồng thời gán parent để phục vụ việc truy vấn tổ tiên.

Truy vấn tất cả tổ tiên của một nút

def get_ancestors(node):
    ancestors = []
    current = node.parent
    while current:
        ancestors.append(current.value)
        current = current.parent
    return ancestors

Giải thích:

• Bắt đầu từ node.parent, lặp ngược lên cho tới khi không còn parent.
• Mỗi lần đi lên, thêm giá trị của tổ tiên vào danh sách.

Ví dụ 1: Cây đơn giản

# Tạo cây
root = Node("A")
b = Node("B")
c = Node("C")
d = Node("D")
e = Node("E")

root.add_child(b)
root.add_child(c)
b.add_child(d)
d.add_child(e)

# Truy vấn tổ tiên của E
print("Tổ tiên của E:", get_ancestors(e))

✅ Kết quả:

Tổ tiên của E: ['D', 'B', 'A']

Truy vấn tổ tiên có điều kiện

Ví dụ: Tìm tổ tiên đầu tiên thoả mãn điều kiện nào đó (ví dụ: giá trị bắt đầu bằng chữ "B")

def find_ancestor_condition(node, condition_fn):
    current = node.parent
    while current:
        if condition_fn(current.value):
            return current.value
        current = current.parent
    return None

# Ví dụ điều kiện
print("Tổ tiên bắt đầu bằng 'B':", find_ancestor_condition(e, lambda val: val.startswith("B")))

✅ Kết quả:

Tổ tiên bắt đầu bằng 'B': B

Ví dụ 2: Cây phức tạp hơn

# Cây khác
root = Node("root")
a = Node("admin")
b = Node("user")
c = Node("guest")
a1 = Node("superadmin")
a2 = Node("moderator")

root.add_child(a)
root.add_child(b)
a.add_child(a1)
a.add_child(a2)
a2.add_child(c)

print("Tổ tiên của 'guest':", get_ancestors(c))

✅ Kết quả:

Tổ tiên của 'guest': ['moderator', 'admin', 'root']

Kết luận

Việc truy vấn tổ tiên trên cây là một kỹ thuật thiết yếu khi làm việc với các cấu trúc dữ liệu phân cấp. Python cung cấp cho chúng ta cách cài đặt đơn giản, dễ hiểu và linh hoạt.

💡 Bạn có thể mở rộng bằng cách lưu các tổ tiên vào set để kiểm tra tổ tiên chung, hoặc kết hợp với DFS để xử lý nâng cao hơn.

#HappyCoding cùng FullhouseDev! 🚀