Khóa học CTDL và GT

Bài 32.1. Cây và các thuật toán cơ bản trên cây

Nếu bạn đã đi qua các cấu trúc dữ liệu tuyến tính như Mảng, Danh sách liên kết, Stack, Queue, thì đã đến lúc chúng ta bước vào một thế giới mới, thế giới của các cấu trúc dữ liệu phi tuyến tính! Và Cây (Tree) chính là điểm khởi đầu đầy thú vị của hành trình này.

Cây là một trong những cấu trúc dữ liệu mạnh mẽ và linh hoạt nhất, xuất hiện ở khắp mọi nơi trong khoa học máy tính, từ cách tổ chức file trong hệ điều hành, cấu trúc trang web, cho đến việc biểu diễn công thức toán học hay phân tích cú pháp ngôn ngữ lập trình. Trong bài viết này, chúng ta sẽ cùng nhau khám phá:

1. Cây là gì và các khái niệm cơ bản liên quan.
2. Tại sao Cây lại quan trọng.
3. Cách biểu diễn Cây trong lập trình.
4. Các thuật toán duyệt cây cơ bản: Duyệt theo chiều sâu (DFS) và Duyệt theo chiều rộng (BFS).

Hãy cùng bắt đầu hành trình khám phá cấu trúc dữ liệu "cây" này nhé!

Cây (Tree) Là Gì?

Trong khoa học máy tính, một cây là một cấu trúc dữ liệu phân cấp bao gồm các nút (nodes) được liên kết với nhau bởi các cạnh (edges). Nó mô phỏng các mối quan hệ phân cấp theo kiểu gia đình hoặc cấu trúc tổ chức.

Một cách định nghĩa đơn giản hơn, một cây có thể là:

• Một tập hợp rỗng các nút.
• Hoặc một tập hợp các nút bao gồm:
  • Một nút đặc biệt gọi là gốc (root).
  • Và zero hoặc nhiều cây con (subtrees) rời rạc, mỗi cây con cũng là một cây, có gốc được liên kết với gốc của cây lớn hơn bởi một cạnh.

Điều quan trọng cần nhớ về cây là nó không chứa chu trình (cycle). Luôn luôn có một và chỉ một đường đi duy nhất giữa hai nút bất kỳ trong cây.

Các Khái Niệm Cơ Bản Về Cây

Để làm việc với cây, chúng ta cần nắm vững một số thuật ngữ:

• Gốc (Root): Nút trên cùng của cây. Nó không có nút cha (parent). (Trong hình vẽ cây thường được biểu diễn ngược so với cây ngoài đời thực, gốc ở trên cùng).
• Nút con (Child): Một nút được liên kết trực tiếp với nút khác theo hướng đi xuống.
• Nút cha (Parent): Ngược lại với nút con, một nút là cha của các nút được liên kết trực tiếp với nó theo hướng đi xuống. Mỗi nút (trừ gốc) chỉ có duy nhất một nút cha.
• Anh em (Siblings): Các nút có cùng một nút cha.
• Lá (Leaf Node): Một nút không có bất kỳ nút con nào.
• Nút trung gian (Internal Node): Một nút không phải là nút lá (tức là có ít nhất một nút con).
• Đường đi (Path): Một dãy các nút từ nút này đến nút khác, được nối bằng các cạnh.
• Độ sâu (Depth): Độ sâu của một nút là số lượng cạnh từ gốc đến nút đó. Độ sâu của gốc thường được xem là 0.
• Chiều cao (Height): Chiều cao của một nút là số lượng cạnh trên đường đi dài nhất từ nút đó đến một nút lá trong cây con của nó. Chiều cao của cây là chiều cao của nút gốc. Chiều cao của nút lá là 0.
• Bậc (Degree): Bậc của một nút là số lượng cây con của nó (tức là số lượng nút con trực tiếp). Bậc của cây là bậc lớn nhất trong tất cả các nút của cây.
• Rừng (Forest): Một tập hợp các cây rời rạc.

Ví dụ minh họa (trong tưởng tượng):

Hãy tưởng tượng một cây đơn giản:

• Nút A là gốc.
• Nút B và C là con của A.
• Nút D là con của B.
• Nút E và F là con của C.

Trong ví dụ này:

• A là gốc.
• B và C là anh em.
• D, E, F là các nút lá.
• A, B, C là các nút trung gian.
• Độ sâu của A là 0, B và C là 1, D, E, F là 2.
• Chiều cao của D, E, F là 0. Chiều cao của B là 1. Chiều cao của C là 1. Chiều cao của A là 2 (đường đi dài nhất A -> C -> E hoặc A -> C -> F).
• Bậc của A là 2, B là 1, C là 2, D, E, F là 0.

Tại Sao Cây Lại Quan Trọng?

Cây là một cấu trúc dữ liệu cực kỳ hữu ích vì khả năng mô hình hóa các mối quan hệ phân cấp và cung cấp các thuật toán hiệu quả cho nhiều tác vụ. Dưới đây là một vài ứng dụng điển hình:

• Hệ thống File: Cấu trúc thư mục và file trên máy tính của bạn chính là một cây (gốc là thư mục ổ đĩa, các nút là thư mục con và file).
• Cấu trúc tổ chức: Biểu đồ tổ chức của một công ty là một cây (gốc là CEO, các nút là các phòng ban/nhân viên).
• Phân tích cú pháp (Parsing): Các trình biên dịch (compiler) sử dụng cây cú pháp (parse tree hoặc abstract syntax tree) để biểu diễn cấu trúc của mã nguồn.
• Biểu thức toán học: Cây biểu thức có thể biểu diễn các công thức toán học một cách trực quan.
• Cơ sở dữ liệu: Nhiều cấu trúc dữ liệu được sử dụng trong cơ sở dữ liệu để indexing (như B-trees, B+ trees) dựa trên cây để truy vấn dữ liệu nhanh chóng.
• Trí tuệ nhân tạo: Cây quyết định (Decision Tree) được sử dụng trong machine learning.

Sự phân cấp giúp việc tìm kiếm, thêm, xóa dữ liệu trong cây (đặc biệt là các loại cây cân bằng) thường có độ phức tạp thời gian là O(log n), hiệu quả hơn nhiều so với các cấu trúc dữ tuyến tính cho các tập dữ liệu lớn.

Biểu Diễn Cây Trong Lập Trình

Có nhiều cách để biểu diễn một cây trong bộ nhớ máy tính. Cách phổ biến và trực quan nhất, đặc biệt với các loại cây không có cấu trúc cố định như Binary Tree hay General Tree, là sử dụng biểu diễn dựa trên nút (Node-based Representation).

Biểu Diễn Dựa Trên Nút

Trong cách này, mỗi nút trong cây là một đối tượng hoặc cấu trúc (struct hoặc class) chứa:

1. Dữ liệu của nút đó.
2. Các con trỏ (pointers) hoặc tham chiếu (references) đến các nút con của nó.

Đối với Cây nhị phân (Binary Tree), mỗi nút có tối đa hai nút con (con trái và con phải), nên cấu trúc nút sẽ đơn giản hơn:

#include <iostream>
#include <vector>
#include <queue> // Dùng cho BFS

// Định nghĩa cấu trúc một nút trong cây nhị phân
struct Node {
    int data; // Dữ liệu mà nút này lưu trữ
    Node* left; // Con trỏ tới nút con bên trái
    Node* right; // Con trỏ tới nút con bên phải

    // Constructor để tạo nút mới
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Ví dụ tạo một cây nhị phân đơn giản:
//        1
//       / \
//      2   3
//     / \
//    4   5
int main() {
    // Tạo nút gốc
    Node* root = new Node(1);

    // Tạo các nút con và liên kết chúng
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    // Bây giờ chúng ta đã có một cây nhị phân.
    // ... sẽ thực hiện các thuật toán duyệt cây trên cây này

    // Dọn dẹp bộ nhớ (quan trọng trong C++ để tránh rò rỉ bộ nhớ)
    // Việc dọn dẹp cây đòi hỏi duyệt cây để xóa từng nút.
    // Tạm bỏ qua phần này trong ví dụ cơ bản, nhưng cần nhớ trong thực tế.
    // Một cách đơn giản là dùng post-order traversal để xóa.
    // delete root->left->left;
    // delete root->left->right;
    // delete root->left;
    // delete root->right;
    // delete root;

    return 0;
}

Giải thích Code:

• Chúng ta định nghĩa một struct Node để biểu diễn một nút trong cây nhị phân.
• Mỗi Node có một trường data (ở đây là kiểu int), và hai con trỏ left và right kiểu Node*. Các con trỏ này sẽ trỏ đến nút con trái và con phải tương ứng. Nếu một con trỏ là nullptr, nghĩa là nút đó không có con tương ứng.
• Constructor Node(int val) giúp khởi tạo một nút mới với dữ liệu là val và hai con trỏ con ban đầu là nullptr.
• Trong main, chúng ta tạo các nút mới bằng new Node(...) và gán chúng vào các con trỏ left hoặc right của nút cha để xây dựng cấu trúc cây.

Đối với Cây tổng quát (General Tree), nơi một nút có thể có bất kỳ số lượng nút con nào, chúng ta sẽ cần một cấu trúc linh hoạt hơn, thường sử dụng một vector hoặc danh sách liên kết để lưu trữ các con trỏ đến các nút con:

#include <iostream>
#include <vector>
#include <queue> // Dùng cho BFS

// Định nghĩa cấu trúc một nút trong cây tổng quát
struct GeneralTreeNode {
    int data; // Dữ liệu của nút
    std::vector<GeneralTreeNode*> children; // Vector lưu trữ các con trỏ tới nút con

    // Constructor
    GeneralTreeNode(int val) : data(val) {}
};

// Ví dụ tạo một cây tổng quát đơn giản:
//        10
//       / | \
//      20 30 40
//     / \    |
//    50 60   70
int main_general_tree() {
    GeneralTreeNode* root = new GeneralTreeNode(10);

    // Thêm các nút con cho gốc
    root->children.push_back(new GeneralTreeNode(20));
    root->children.push_back(new GeneralTreeNode(30));
    root->children.push_back(new GeneralTreeNode(40));

    // Thêm các nút con cho nút 20 (là con đầu tiên của gốc)
    root->children[0]->children.push_back(new GeneralTreeNode(50));
    root->children[0]->children.push_back(new GeneralTreeNode(60));

    // Thêm nút con cho nút 40 (là con thứ ba của gốc)
    root->children[2]->children.push_back(new GeneralTreeNode(70));

    // Bây giờ chúng ta đã có một cây tổng quát.
    // ... sẽ thực hiện các thuật toán duyệt cây trên cây này

    // Dọn dẹp bộ nhớ (tương tự như Binary Tree, cần duyệt và xóa)
    // Việc này phức tạp hơn một chút với cây tổng quát,
    // thường dùng đệ quy hoặc BFS để xóa từ lá trở lên.

    return 0;
}

Giải thích Code:

• GeneralTreeNode sử dụng một std::vector<GeneralTreeNode*> để lưu trữ các con trỏ đến tất cả các nút con của nó. Số lượng con có thể thay đổi linh hoạt.
• Khi tạo cây, chúng ta tạo các nút mới và sử dụng phương thức push_back() của vector để thêm chúng vào danh sách con của nút cha.

Lưu ý: Trong phạm vi các thuật toán cơ bản thường được giới thiệu đầu tiên, chúng ta sẽ tập trung vào cây nhị phân vì nó đơn giản hơn và là nền tảng cho nhiều loại cây phức tạp khác. Các thuật toán duyệt cây cho cây tổng quát cũng tương tự, chỉ khác ở chỗ lặp qua danh sách các nút con thay vì chỉ hai con trái/phải.

Các Thuật Toán Duyệt Cây Cơ Bản (Tree Traversal)

Duyệt cây (Tree Traversal) là quá trình thăm (visit) mọi nút trong cây một cách có hệ thống. "Thăm" một nút có thể có nghĩa là in dữ liệu của nút đó, xử lý dữ liệu đó, hoặc thực hiện một thao tác nào đó.

Có hai chiến lược chính để duyệt cây:

1. Duyệt theo chiều sâu (Depth-First Search - DFS): Đi sâu nhất có thể vào một nhánh trước khi quay lại và khám phá nhánh khác.
2. Duyệt theo chiều rộng (Breadth-First Search - BFS): Thăm tất cả các nút ở cùng một mức độ sâu trước khi chuyển sang mức độ sâu tiếp theo.

Chúng ta sẽ xem xét các phương pháp này cho Cây nhị phân, đây là trường hợp phổ biến nhất khi học duyệt cây.

1. Duyệt Theo Chiều Sâu (DFS)

Duyệt DFS trên cây nhị phân có ba cách phổ biến, dựa trên thứ tự thăm nút gốc (Root) so với các cây con trái (Left) và phải (Right):

• Duyệt Tiền thứ tự (Pre-order Traversal): Thăm nút gốc, sau đó duyệt cây con trái, cuối cùng duyệt cây con phải. Thứ tự: Root -> Left -> Right.
• Duyệt Trung thứ tự (In-order Traversal): Duyệt cây con trái, sau đó thăm nút gốc, cuối cùng duyệt cây con phải. Thứ tự: Left -> Root -> Right.
• Duyệt Hậu thứ tự (Post-order Traversal): Duyệt cây con trái, sau đó duyệt cây con phải, cuối cùng thăm nút gốc. Thứ tự: Left -> Right -> Root.

Các thuật toán DFS trên cây thường được triển khai một cách tự nhiên và thanh lịch bằng đệ quy.

Duyệt Tiền thứ tự (Pre-order Traversal)

Thứ tự: Root -> Left -> Right

Ứng dụng: Tạo bản sao của cây, biểu diễn cấu trúc tiền tố (prefix expression) của cây biểu thức.

#include <iostream>
#include <vector>
#include <queue>

// Định nghĩa cấu trúc một nút trong cây nhị phân
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Hàm duyệt cây theo thứ tự Tiền thứ tự (Pre-order)
void preOrder(Node* node) {
    // Trường hợp cơ bản: Nếu nút rỗng, dừng đệ quy
    if (node == nullptr) {
        return;
    }

    // 1. Thăm nút gốc (in dữ liệu)
    std::cout << node->data << " ";

    // 2. Duyệt cây con trái
    preOrder(node->left);

    // 3. Duyệt cây con phải
    preOrder(node->right);
}

// --- Hàm main và ví dụ cây như trên ---
//        1
//       / \
//      2   3
//     / \
//    4   5

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    std::cout << "Duyet Pre-order: ";
    preOrder(root); // Kết quả: 1 2 4 5 3
    std::cout << std::endl;

    // Dọn dẹp bộ nhớ (ví dụ đơn giản, trong thực tế cần hàm xóa cây đầy đủ)
    // Dùng post-order để xóa là cách an toàn.
    // postOrderDelete(root); // Cần triển khai hàm này

    return 0;
}

Giải thích Code:

• Hàm preOrder(Node* node) nhận vào con trỏ tới nút hiện tại.
• if (node == nullptr): Đây là điều kiện dừng của đệ quy. Nếu con trỏ là nullptr, tức là đã đi qua một nhánh rỗng, chúng ta dừng lại.
• std::cout << node->data << " ";: Đây là thao tác "thăm" nút hiện tại. Trong pre-order, thao tác này được thực hiện trước khi gọi đệ quy cho các con.
• preOrder(node->left);: Gọi đệ quy để duyệt toàn bộ cây con bên trái của nút hiện tại.
• preOrder(node->right);: Sau khi duyệt xong cây con trái, gọi đệ quy để duyệt toàn bộ cây con bên phải.

Duyệt Trung thứ tự (In-order Traversal)

Thứ tự: Left -> Root -> Right

Ứng dụng: Duyệt các phần tử của một Cây tìm kiếm nhị phân (Binary Search Tree - BST) sẽ cho kết quả các phần tử được sắp xếp theo thứ tự tăng dần.

#include <iostream>
#include <vector>
#include <queue>

// ... (Cấu trúc Node tương tự như trên) ...
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Hàm duyệt cây theo thứ tự Trung thứ tự (In-order)
void inOrder(Node* node) {
    // Trường hợp cơ bản: Nếu nút rỗng, dừng đệ quy
    if (node == nullptr) {
        return;
    }

    // 1. Duyệt cây con trái
    inOrder(node->left);

    // 2. Thăm nút gốc (in dữ liệu) - Thao tác thăm xảy ra giữa hai lời gọi đệ quy
    std::cout << node->data << " ";

    // 3. Duyệt cây con phải
    inOrder(node->right);
}

// --- Hàm main và ví dụ cây như trên ---
//        1
//       / \
//      2   3
//     / \
//    4   5

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    std::cout << "Duyet In-order: ";
    inOrder(root); // Kết quả: 4 2 5 1 3
    std::cout << std::endl;

    // Dọn dẹp bộ nhớ

    return 0;
}

Giải thích Code:

• Cấu trúc hàm tương tự preOrder.
• Điểm khác biệt duy nhất là vị trí của thao tác "thăm" (std::cout << node->data << " ";). Trong in-order, nó được đặt giữa lời gọi đệ quy cho cây con trái và lời gọi đệ quy cho cây con phải.

Duyệt Hậu thứ tự (Post-order Traversal)

Thứ tự: Left -> Right -> Root

Ứng dụng: Xóa toàn bộ cây (xóa các nút lá trước, sau đó đến cha của chúng, v.v., đảm bảo không truy cập vào bộ nhớ đã được giải phóng), biểu diễn cấu trúc hậu tố (postfix expression) của cây biểu thức.

#include <iostream>
#include <vector>
#include <queue>

// ... (Cấu trúc Node tương tự như trên) ...
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Hàm duyệt cây theo thứ tự Hậu thứ tự (Post-order)
void postOrder(Node* node) {
    // Trường hợp cơ bản: Nếu nút rỗng, dừng đệ quy
    if (node == nullptr) {
        return;
    }

    // 1. Duyệt cây con trái
    postOrder(node->left);

    // 2. Duyệt cây con phải
    postOrder(node->right);

    // 3. Thăm nút gốc (in dữ liệu) - Thao tác thăm xảy ra sau hai lời gọi đệ quy
    std::cout << node->data << " ";
}

// --- Hàm main và ví dụ cây như trên ---
//        1
//       / \
//      2   3
//     / \
//    4   5

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    std::cout << "Duyet Post-order: ";
    postOrder(root); // Kết quả: 4 5 2 3 1
    std::cout << std::endl;

    // Dọn dẹp bộ nhớ
    // Ví dụ hàm xóa cây bằng Post-order:
    /*
    void postOrderDelete(Node* node) {
        if (node == nullptr) return;
        postOrderDelete(node->left);
        postOrderDelete(node->right);
        delete node; // Xóa nút sau khi đã xóa các con
    }
    */
    // postOrderDelete(root); // Gọi hàm xóa

    return 0;
}

Giải thích Code:

• Tương tự hai hàm trên, nhưng thao tác "thăm" (std::cout << node->data << " ";) được đặt sau cùng, sau khi cả cây con trái và cây con phải đã được duyệt xong hoàn toàn.

2. Duyệt Theo Chiều Rộng (BFS) - Duyệt theo Mức (Level-Order Traversal)

Duyệt BFS trên cây còn được gọi là duyệt theo mức (Level-order Traversal). Chúng ta thăm tất cả các nút ở mức 0 (chỉ gốc), sau đó tất cả các nút ở mức 1, rồi tất cả các nút ở mức 2, và cứ thế tiếp tục cho đến khi thăm hết tất cả các nút.

Thuật toán này không dễ dàng triển khai bằng đệ quy như DFS. Thay vào đó, nó thường sử dụng một hàng đợi (queue) để quản lý các nút cần thăm theo đúng thứ tự mức.

Cách hoạt động:

1. Bắt đầu bằng cách thêm nút gốc vào hàng đợi.
2. Trong khi hàng đợi chưa rỗng:
   • Lấy (dequeue) một nút từ phía trước hàng đợi.
   • Thăm nút đó (ví dụ: in dữ liệu).
   • Thêm (enqueue) tất cả các nút con của nó vào phía sau hàng đợi (theo thứ tự từ trái sang phải đối với cây nhị phân).

#include <iostream>
#include <vector>
#include <queue> // Thư viện chứa std::queue

// ... (Cấu trúc Node tương tự như trên) ...
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Hàm duyệt cây theo thứ tự Mức (Level-order)
void levelOrder(Node* root) {
    // Trường hợp cơ bản: Cây rỗng
    if (root == nullptr) {
        return;
    }

    // Tạo một hàng đợi để lưu trữ các con trỏ nút
    std::queue<Node*> q;

    // Thêm nút gốc vào hàng đợi ban đầu
    q.push(root);

    // Lặp cho đến khi hàng đợi rỗng
    while (!q.empty()) {
        // 1. Lấy nút ở đầu hàng đợi
        Node* current_node = q.front();
        q.pop(); // Xóa nút đó khỏi hàng đợi

        // 2. Thăm nút hiện tại (in dữ liệu)
        std::cout << current_node->data << " ";

        // 3. Thêm các nút con của nút hiện tại vào cuối hàng đợi (nếu có)
        if (current_node->left != nullptr) {
            q.push(current_node->left);
        }
        if (current_node->right != nullptr) {
            q.push(current_node->right);
        }
    }
}

// --- Hàm main và ví dụ cây như trên ---
//        1
//       / \
//      2   3
//     / \
//    4   5

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    std::cout << "Duyet Level-order (BFS): ";
    levelOrder(root); // Kết quả: 1 2 3 4 5
    std::cout << std::endl;

    // Dọn dẹp bộ nhớ
    // Việc dọn dẹp bộ nhớ cho cây này có thể thực hiện bằng post-order deletion
    // hoặc bằng chính BFS bằng cách lưu trữ các nút cần xóa.

    return 0;
}

Giải thích Code:

• Chúng ta sử dụng std::queue<Node*> q; để lưu trữ các nút sẽ được thăm tiếp theo. Queue tuân theo nguyên tắc FIFO (First-In, First-Out).
• Bắt đầu bằng cách đẩy nút gốc vào hàng đợi.
• Vòng lặp while (!q.empty()) tiếp tục cho đến khi không còn nút nào trong hàng đợi (tức là đã duyệt hết cây).
• Bên trong vòng lặp:
  • q.front(): Lấy nút ở đầu hàng đợi mà không xóa nó.
  • q.pop(): Xóa nút vừa lấy ra khỏi hàng đợi.
  • std::cout << current_node->data << " ";: Thăm nút hiện tại.
  • Hai câu lệnh if kiểm tra xem nút hiện tại có con trái (left) hoặc con phải (right) không. Nếu có, các nút con này sẽ được đẩy vào cuối hàng đợi. Nhờ tính chất FIFO của queue, chúng sẽ được lấy ra và thăm sau tất cả các nút cùng mức đã được thêm vào trước đó.

Các Thuật Toán Cơ Bản Khác

Ngoài duyệt cây, còn có nhiều thuật toán cơ bản khác trên cây mà bạn có thể cần:

• Tính chiều cao của cây: Dùng đệ quy, chiều cao của một nút bằng 1 cộng với chiều cao lớn nhất của các cây con của nó.
• Đếm số nút: Dùng đệ quy, số nút bằng 1 (nút hiện tại) cộng với tổng số nút trong tất cả các cây con của nó.
• Tìm kiếm một nút: Có thể dùng bất kỳ phương pháp duyệt nào (DFS hoặc BFS) để tìm kiếm một giá trị cụ thể.
• Chèn/Xóa nút: Phụ thuộc nhiều vào loại cây (Binary Search Tree, AVL tree, Red-Black tree,...), các thao tác này phức tạp hơn duyệt.

Ví dụ: Tính Chiều Cao Cây Nhị phân

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> // Để dùng std::max

// ... (Cấu trúc Node tương tự như trên) ...
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Hàm tính chiều cao của cây nhị phân
// Chiều cao của cây rỗng là -1
// Chiều cao của cây chỉ có 1 nút là 0
int height(Node* node) {
    // Trường hợp cơ bản: Cây rỗng
    if (node == nullptr) {
        return -1;
    }

    // Tính chiều cao của cây con trái
    int left_height = height(node->left);
    // Tính chiều cao của cây con phải
    int right_height = height(node->right);

    // Chiều cao của nút hiện tại bằng 1 cộng với chiều cao lớn nhất của hai cây con
    return std::max(left_height, right_height) + 1;
}

// --- Hàm main và ví dụ cây như trên ---
//        1
//       / \
//      2   3
//     / \
//    4   5

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    // Cây có chiều cao là 2 (đường đi dài nhất từ 1 đến 4 hoặc 5 là 1->2->4 hoặc 1->2->5, có 2 cạnh)

    std::cout << "Chieu cao cua cay: " << height(root) << std::endl; // Kết quả: 2

    // Dọn dẹp bộ nhớ

    return 0;
}

Giải thích Code:

• Hàm height(Node* node) sử dụng đệ quy để tính chiều cao.
• Trường hợp cơ bản if (node == nullptr) trả về -1. Điều này là một quy ước phổ biến để khi tính chiều cao của một nút lá (có hai con trỏ nullptr), std::max(-1, -1) + 1 sẽ cho kết quả 0, đúng với định nghĩa chiều cao của nút lá là 0.
• Đối với nút không rỗng, chúng ta gọi đệ quy để tính chiều cao của cây con trái và cây con phải.
• Kết quả trả về là giá trị lớn nhất giữa chiều cao của hai cây con, cộng thêm 1 (để tính cạnh nối từ nút hiện tại xuống nút con cao nhất).

Ví dụ: Đếm Số Nút trong Cây Nhị phân

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

// ... (Cấu trúc Node tương tự như trên) ...
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Hàm đếm số nút trong cây nhị phân
int countNodes(Node* node) {
    // Trường hợp cơ bản: Cây rỗng
    if (node == nullptr) {
        return 0;
    }

    // Số nút bằng 1 (chính nó) cộng với số nút trong cây con trái và cây con phải
    return 1 + countNodes(node->left) + countNodes(node->right);
}

// --- Hàm main và ví dụ cây như trên ---
//        1
//       / \
//      2   3
//     / \
//    4   5

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    // Cây có 5 nút

    std::cout << "So nut trong cay: " << countNodes(root) << std::endl; // Kết quả: 5

    // Dọn dẹp bộ nhớ

    return 0;
}

Giải thích Code:

• Hàm countNodes(Node* node) cũng dùng đệ quy.
• Trường hợp cơ bản if (node == nullptr) trả về 0, vì cây rỗng không có nút nào.
• Đối với nút không rỗng, nó đếm chính nó (1) và cộng thêm tổng số nút trong cây con trái (countNodes(node->left)) và cây con phải (countNodes(node->right)).