Cấu trúc dữ liệu và Giải thuật Bài 40: Giới thiệu Cây Nhị Phân (Binary Tree) và các phép duyệt cây (Traversals).

Suốt 6 chương vừa qua, chúng ta đã mắc kẹt trong thế giới dữ liệu một chiều (1D). Dù là Mảng, Linked List, Stack hay Queue, dữ liệu luôn xếp thành một hàng dọc: một phần tử chỉ có đúng một người tiền nhiệm và một người kế nhiệm. Tuy nhiên, dữ liệu trong thế giới thực hiếm khi phẳng như vậy.

Hãy nhìn vào hệ thống thư mục trên máy tính, cấu trúc thẻ HTML của một trang web, hay sơ đồ tổ chức của một tập đoàn. Chúng đều phân nhánh từ trên xuống dưới. Để lưu trữ và thao tác với dữ liệu phân cấp (Hierarchical Data) này một cách tự nhiên nhất, chúng ta bước vào thế giới phi tuyến tính (2D) của Cây (Tree), mà cốt lõi là Cây Nhị Phân (Binary Tree).

1. Bản chất vật lý: Linked List phân nhánh

Về mặt bộ nhớ, Cây Nhị Phân thực chất là một phiên bản nâng cấp của Danh sách liên kết đôi (Doubly Linked List). Thay vì có hai con trỏ Next và Prev chạy trên một đường thẳng, mỗi Node của Cây Nhị Phân có hai con trỏ rẽ nhánh xuống phía dưới:

1. Left Pointer: Trỏ tới Node con bên trái.

2. Right Pointer: Trỏ tới Node con bên phải.

Từ vựng sinh học của Cây:

• Root (Gốc): Node duy nhất nằm trên cùng, không có cha. Mọi thao tác truy xuất đều phải bắt đầu từ đây (giống như Head của Linked List).

• Leaf (Lá): Những Node nằm ở tận cùng, không có bất kỳ con nào (cả Left và Right đều trỏ vào nil).

• Height (Chiều cao): Quãng đường dài nhất từ Root đi xuống một Leaf bất kỳ. Nếu Mảng có độ dài $N$, thì Cây có chiều cao $H$. Các thuật toán tối ưu trên cây luôn cố gắng ép thời gian chạy từ $O(n)$ xuống thành $O(h)$, trong đó $h \approx \log_2(n)$.

Triển khai Node bằng Golang:

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

2. Các phép duyệt theo chiều sâu (DFS - Depth First Search)

Vì dữ liệu rẽ nhánh, bạn không thể dùng một vòng lặp for i := 0; i < n để đi từ đầu đến cuối như mảng. Để đi qua mọi Node mà không bỏ sót ai, chúng ta sử dụng Đệ quy (Recursion) - bản chất là mượn Call Stack của hệ điều hành (như đã học ở Bài 33) để tự động ghi nhớ đường lùi.

Có 3 chiến thuật duyệt DFS, được đặt tên dựa trên vị trí của Gốc (Root/Node hiện tại) so với các con của nó:

A. Pre-order (Duyệt Tiền Thứ Tự: Gốc $\rightarrow$ Trái $\rightarrow$ Phải)

Bạn xử lý Node hiện tại ngay lần đầu tiên chạm vào nó, sau đó mới đi xuống khám phá các nhánh con.

• Ứng dụng: Dùng để "Copy" (Clone) một cây, hoặc Serialize (tuần tự hóa) cây thành một chuỗi JSON/String để lưu xuống database.

Go

func preOrder(node *TreeNode) {
    if node == nil {
        return
    }
    fmt.Println(node.Val) // Xử lý Gốc
    preOrder(node.Left)   // Đi hết nhánh Trái
    preOrder(node.Right)  // Đi hết nhánh Phải
}

B. In-order (Duyệt Trung Thứ Tự: Trái $\rightarrow$ Gốc $\rightarrow$ Phải)

Bạn đi sâu xuống tận cùng bên trái, sau đó mới xử lý Node, rồi mới sang phải.

• Ứng dụng: Đây là phép duyệt quan trọng nhất khi làm việc với Cây Nhị Phân Tìm Kiếm (BST). Nó đảm bảo dữ liệu được in ra theo thứ tự tăng dần hoàn hảo.

Go

func inOrder(node *TreeNode) {
    if node == nil {
        return
    }
    inOrder(node.Left)    // Khám phá tận cùng Trái
    fmt.Println(node.Val) // Xử lý Gốc
    inOrder(node.Right)   // Khám phá nhánh Phải
}

C. Post-order (Duyệt Hậu Thứ Tự: Trái $\rightarrow$ Phải $\rightarrow$ Gốc)

Bạn bỏ qua Node hiện tại, đi xử lý triệt để tất cả các con cháu của nó trước, rồi mới quay lên xử lý chính nó cuối cùng (Từ dưới lên trên).

• Ứng dụng: Dùng để giải phóng bộ nhớ (Xóa cây), hoặc tính toán các thông số mang tính "tổng hợp" (Ví dụ: Tính tổng dung lượng của một thư mục bằng cách cộng dung lượng của tất cả các file con bên trong nó lại).

Go

func postOrder(node *TreeNode) {
    if node == nil {
        return
    }
    postOrder(node.Left)
    postOrder(node.Right)
    fmt.Println(node.Val) // Xử lý Gốc cuối cùng
}

3. Phép duyệt theo chiều rộng (BFS - Level Order Traversal)

Nếu DFS lao thẳng xuống đáy sâu nhất rồi mới mò ngược lên, thì BFS chọn cách "quét radar" theo từng tầng (level). Nó sẽ thăm Root ở Tầng 0, sau đó thăm tất cả các Node ở Tầng 1 (từ trái sang phải), rồi mới xuống Tầng 2.

Để làm được điều này, Đệ quy (Stack) trở nên vô dụng. Chúng ta phải sử dụng Hàng đợi (Queue) để giữ gìn thứ tự khám phá "vào trước ra trước".

Go

func levelOrder(root *TreeNode) {
    if root == nil {
        return
    }
    
    // Khởi tạo Queue và đưa Root vào
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        // Lấy Node ở đầu hàng đợi ra (Dequeue)
        current := queue[0]
        queue = queue[1:]
        
        fmt.Println(current.Val) // Xử lý Node hiện tại
        
        // Kéo các con của nó vào xếp hàng đợi (Enqueue)
        if current.Left != nil {
            queue = append(queue, current.Left)
        }
        if current.Right != nil {
            queue = append(queue, current.Right)
        }
    }
}

• Ứng dụng: Tìm đường đi ngắn nhất (Shortest Path) trong đồ thị, hoặc thiết kế các module phân tích quan hệ mạng lưới (Ví dụ: Hiển thị danh sách "Bạn chung" trên Facebook - quét vòng bạn bè bậc 1 trước khi quét bậc 2).

4. Ứng dụng của Cấu trúc Cây trong Backend

Khi lập trình backend, bạn hiếm khi phải tự struct TreeNode. Tuy nhiên, mã nguồn của các công cụ bạn đang dùng hằng ngày đều được vận hành bởi chúng:

• Bộ định tuyến (Router) trong Web Frameworks: Khi bạn khai báo Route trong các framework (như Gin, Echo của Golang, hoặc Laravel của PHP), Engine bên dưới không dùng Mảng để so khớp URL. Chúng dùng một loại cây đặc biệt (Radix Tree/Trie). Khi một request /api/v1/users đi tới, nó duyệt dọc theo cây để tìm đến hàm Handler xử lý với thời gian tiệm cận $O(1)$, thay vì dùng Regex quét toàn bộ danh sách routes.

• Trình biên dịch (Compiler) & AST: Khi bạn gõ mã nguồn Golang, bước đầu tiên để Go biên dịch mã của bạn thành mã máy là chạy Lexer/Parser để biến toàn bộ file .go thành một cây Cú pháp trừu tượng (Abstract Syntax Tree - AST).

• Cơ sở dữ liệu dạng tài liệu (Document DBs): Cấu trúc JSON bạn lưu trong MongoDB hay Elasticsearch bản chất là một cái Cây, nơi các Key là Node cha và Value lồng ghép bên trong là các nhánh con.

Cây Nhị Phân cơ bản chỉ là nền tảng để chứa dữ liệu phân cấp. Nhưng nếu chúng ta áp đặt một luật lệ phân bổ dữ liệu nghiêm ngặt lên cấu trúc Cây (ví dụ: con bên trái luôn nhỏ hơn cha, con bên phải luôn lớn hơn cha), chúng ta sẽ tạo ra một trong những cỗ máy tìm kiếm dữ liệu vĩ đại nhất của ngành Khoa học Máy tính.