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

Bài 14.3 - Tính chiều sâu của cây với Python

Trong lập trình cây, chiều sâu của cây (hay còn gọi là depth hoặc height) là một khái niệm rất cơ bản nhưng rất quan trọng. Nó giúp chúng ta hiểu được mức độ phân cấp và độ phức tạp của cây.

Trong bài này, bạn sẽ học cách viết chương trình Python để tính chiều sâu của cây một cách hiệu quả.

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

Trước hết, chúng ta cần xây dựng cây để thao tác:

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

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

Giải thích:

• Mỗi Node có một value và danh sách children (các node con).
• Hàm add_child dùng để gắn các node con vào node hiện tại.

2. Hàm tính chiều sâu của cây

def tree_depth(node):
    if not node.children:
        return 1
    return 1 + max(tree_depth(child) for child in node.children)

Giải thích:

• Nếu node không có con (tức là lá), chiều sâu = 1.
• Nếu có con, ta tính đệ quy chiều sâu của các con và lấy giá trị lớn nhất, cộng thêm 1 (cho node hiện tại).

3. Ví dụ 1: Cây cơ bả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)

print("Chiều sâu của cây là:", tree_depth(root))

✅ Kết quả:

Chiều sâu của cây là: 4

Giải thích:

Chuỗi đường đi dài nhất từ gốc A đến lá E là: A → B → D → E (4 cấp).

4. Ví dụ 2: Cây có nhiều nhánh phụ

root = Node("root")
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
f = Node("f")

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

print("Chiều sâu của cây là:", tree_depth(root))

✅ Kết quả:

Chiều sâu của cây là: 4

Giải thích:

Nhánh dài nhất là: root → a → d → f → (4 cấp).

5. Mở rộng: Tính chiều sâu từng node

Nếu bạn muốn biết chiều sâu của từng node (so với gốc), có thể dùng thêm tham số depth:

def print_depth(node, depth=1):
    print("".join(["-" * depth]), node.value, f"(Depth: {depth})")
    for child in node.children:
        print_depth(child, depth + 1)

print_depth(root)

Giải thích:

• Mỗi lần gọi đệ quy, ta tăng depth lên 1.
• In dấu - để mô phỏng mức độ phân cấp.

✅ Ví dụ kết quả:

- root (Depth: 1)
-- a (Depth: 2)
--- d (Depth: 3)
---- f (Depth: 4)
-- b (Depth: 2)
--- e (Depth: 3)
-- c (Depth: 2)

Kết luận

Tính chiều sâu cây là thao tác quan trọng khi làm việc với cấu trúc cây. Với Python, bạn có thể triển khai nó ngắn gọn mà vẫn hiệu quả. Đây là nền tảng để sau này xử lý các bài toán như: cân bằng cây, tối ưu truy vấn, hoặc phân tích độ sâu trong hệ thống phân cấp.

💡 Bạn có thể kết hợp thêm với chiều rộng cây hoặc tính độ cao trung bình nếu muốn phân tích sâu hơn.

#HappyCoding cùng FullhouseDev! 🚀