Bài 32.4. Các phép duyệt cây và ứng dụng

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ đào sâu vào một chủ đề cực kỳ quan trọng khi làm việc với cây (trees): các phép duyệt cây (tree traversals).

Cây là một cấu trúc dữ liệu phân cấp mạnh mẽ, được sử dụng rộng rãi từ hệ thống tập tin, tổ chức dữ liệu trong cơ sở dữ liệu, đến biểu diễn cú pháp chương trình. Tuy nhiên, để thao tác hoặc truy xuất dữ liệu trong cây, chúng ta cần một cách có hệ thống để "ghé thăm" (visit) mọi nút (node) trong đó. Quá trình ghé thăm tất cả các nút theo một trình tự cụ thể được gọi là duyệt cây.

Tại sao lại cần nhiều cách duyệt khác nhau? Bởi vì mỗi cách duyệt sẽ cho chúng ta một trình tự truy cập các nút khác nhau, và trình tự này lại phù hợp với những bài toán hoặc ứng dụng cụ thể. Hãy cùng tìm hiểu chi tiết nhé!

Có hai phương pháp duyệt cây chính:

Depth-First Search (DFS): Duyệt theo chiều sâu.
Breadth-First Search (BFS): Duyệt theo chiều rộng.

Chúng ta sẽ đi vào chi tiết từng phương pháp và các biến thể của chúng.

Trước hết, để có thể minh hoạ bằng code, chúng ta cần một cấu trúc cơ bản cho một nút cây nhị phân (Binary Tree Node):

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

// Định nghĩa cấu trúc Node của cây nhị phân
struct Node {
    int data;
    Node *left;
    Node *right;

    // Constructor
    Node(int val) {
        data = val;
        left = right = nullptr; // Khởi tạo con trỏ con là null
    }
};

Cấu trúc Node này rất đơn giản, nó chứa giá trị của nút (data) và hai con trỏ tới nút con bên trái (left) và nút con bên phải (right).

I. Duyệt cây theo chiều sâu (Depth-First Search - DFS)

Duyệt theo chiều sâu nghĩa là chúng ta sẽ đi "sâu" nhất có thể xuống một nhánh của cây trước khi quay trở lại và khám phá các nhánh khác. Có ba biến thể chính của DFS, dựa trên thời điểm chúng ta "ghé thăm" (xử lý) nút gốc so với việc duyệt các cây con trái và phải:

Duyệt Tiền thứ (Pre-order Traversal): Duyệt theo thứ tự Gốc -> Trái -> Phải.
Duyệt Trung thứ (In-order Traversal): Duyệt theo thứ tự Trái -> Gốc -> Phải.
Duyệt Hậu thứ (Post-order Traversal): Duyệt theo thứ tự Trái -> Phải -> Gốc.

Cả ba phép duyệt này thường được cài đặt bằng đệ quy một cách tự nhiên, tận dụng cấu trúc đệ quy của cây.

Hãy xem xét một cây nhị phân ví dụ để dễ hình dung:

Các nút: 1 (gốc), 2 (con trái của 1), 3 (con phải của 1), 4 (con trái của 2), 5 (con phải của 2).

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

Nguyên tắc:

Ghé thăm nút gốc (Root).
Duyệt cây con bên trái (Left subtree).
Duyệt cây con bên phải (Right subtree).

Cách hoạt động (với cây ví dụ trên):

Bắt đầu từ gốc (1). Ghé thăm 1. In ra 1.
Chuyển sang cây con trái của 1 (gốc là 2).
- Tại nút 2: Ghé thăm 2. In ra 2.
- Chuyển sang cây con trái của 2 (gốc là 4).
  - Tại nút 4: Ghé thăm 4. In ra 4.
  - Cây con trái của 4 là rỗng.
  - Cây con phải của 4 là rỗng. Quay lại nút 2.
- Chuyển sang cây con phải của 2 (gốc là 5).
  - Tại nút 5: Ghé thăm 5. In ra 5.
  - Cây con trái của 5 là rỗng.
  - Cây con phải của 5 là rỗng. Quay lại nút 2.
- Đã duyệt xong cây con trái và phải của 2. Quay lại nút 1.
Chuyển sang cây con phải của 1 (gốc là 3).
- Tại nút 3: Ghé thăm 3. In ra 3.
- Cây con trái của 3 là rỗng.
- Cây con phải của 3 là rỗng. Quay lại nút 1.
Đã duyệt xong cây con trái và phải của 1. Kết thúc.

Trình tự các nút được ghé thăm: 1 -> 2 -> 4 -> 5 -> 3

Code minh hoạ (Đệ quy):

// Hàm duyệt Tiền thứ (Pre-order)
void preOrder(Node* root) {
    // Điều kiện dừng đệ quy: nếu nút là rỗng, không làm gì cả
    if (root == nullptr) {
        return;
    }

    // 1. Ghé thăm nút gốc (In ra giá trị của nút hiện tại)
    std::cout << root->data << " ";

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

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

// Cách sử dụng: preOrder(root);

Giải thích code: Hàm preOrder nhận vào con trỏ root của cây (hoặc cây con) cần duyệt.

Dòng if (root == nullptr): Đây là điều kiện cơ bản để dừng đệ quy. Nếu nút hiện tại là rỗng (tức là chúng ta đã đi xuống dưới một lá hoặc cây ban đầu rỗng), hàm sẽ thoát.
Dòng std::cout << root->data << " ";: Đây là bước "ghé thăm" nút gốc. Chúng ta thực hiện hành động mong muốn (ở đây là in giá trị) trước khi duyệt các cây con.
Dòng preOrder(root->left);: Gọi đệ quy hàm preOrder cho cây con bên trái. Quá trình này sẽ lặp lại nguyên tắc Gốc-Trái-Phải cho toàn bộ cây con trái.
Dòng preOrder(root->right);: Sau khi cây con trái đã được duyệt xong hoàn toàn, chúng ta gọi đệ quy cho cây con bên phải.

Ứng dụng của Duyệt Tiền thứ:

Tạo bản sao của cây: Trình tự Tiền thứ cho phép bạn sao chép cây một cách dễ dàng. Bằng cách ghé thăm gốc trước, bạn có thể tạo nút gốc của cây mới, sau đó đệ quy xây dựng cây con trái và phải từ cây con trái và phải của cây gốc.
Biểu diễn biểu thức: Duyệt Tiền thứ trên cây biểu thức (expression tree) sẽ cho kết quả là biểu thức dạng tiền tố (Prefix Notation hay Polish Notation). Ví dụ, cây cho biểu thức (A + B) * C sẽ có dạng Tiền thứ là * + A B C.
Tuần tự hóa (Serialization) cây: Lưu cấu trúc cây vào một file hoặc truyền qua mạng. Trình tự Tiền thứ (thường kèm theo thông tin nút rỗng) rất phù hợp để xây dựng lại cây ban đầu.

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

Nguyên tắc:

Duyệt cây con bên trái (Left subtree).
Ghé thăm nút gốc (Root).
Duyệt cây con bên phải (Right subtree).

Cách hoạt động (với cây ví dụ trên):

Bắt đầu từ gốc (1). Chuyển sang cây con trái của 1 (gốc là 2).
- Tại nút 2: Chuyển sang cây con trái của 2 (gốc là 4).
  - Tại nút 4: Cây con trái của 4 là rỗng.
  - Ghé thăm 4. In ra 4.
  - Cây con phải của 4 là rỗng. Quay lại nút 2.
- Tại nút 2: Đã duyệt xong cây con trái (4). Ghé thăm 2. In ra 2.
- Chuyển sang cây con phải của 2 (gốc là 5).
  - Tại nút 5: Cây con trái của 5 là rỗng.
  - Ghé thăm 5. In ra 5.
  - Cây con phải của 5 là rỗng. Quay lại nút 2.
- Đã duyệt xong cây con trái (4) và phải (5) của 2. Quay lại nút 1.
Tại nút 1: Đã duyệt xong cây con trái (gốc 2). Ghé thăm 1. In ra 1.
Chuyển sang cây con phải của 1 (gốc là 3).
- Tại nút 3: Cây con trái của 3 là rỗng.
- Ghé thăm 3. In ra 3.
- Cây con phải của 3 là rỗng. Quay lại nút 1.
Đã duyệt xong cây con trái (gốc 2) và phải (gốc 3) của 1. Kết thúc.

Trình tự các nút được ghé thăm: 4 -> 2 -> 5 -> 1 -> 3

Code minh hoạ (Đệ quy):

// Hàm duyệt Trung thứ (In-order)
void inOrder(Node* root) {
    // Điều kiện dừng đệ quy
    if (root == nullptr) {
        return;
    }

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

    // 2. Ghé thăm nút gốc (In ra giá trị)
    std::cout << root->data << " ";

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

// Cách sử dụng: inOrder(root);

Giải thích code: Hàm inOrder cũng dùng đệ quy tương tự preOrder.

Dòng inOrder(root->left);: Gọi đệ quy duyệt toàn bộ cây con trái trước.
Dòng std::cout << root->data << " ";: Sau khi toàn bộ cây con trái đã được duyệt xong, chúng ta mới ghé thăm (in giá trị) nút gốc hiện tại.
Dòng inOrder(root->right);: Cuối cùng, gọi đệ quy duyệt toàn bộ cây con phải.

Ứng dụng của Duyệt Trung thứ:

Duyệt cây tìm kiếm nhị phân (Binary Search Tree - BST): Đây là ứng dụng nổi bật nhất! Khi duyệt Trung thứ trên một BST, các nút được ghé thăm sẽ có giá trị theo thứ tự tăng dần. Điều này cực kỳ hữu ích để lấy ra các phần tử của BST theo thứ tự đã được sắp xếp.
Biểu diễn biểu thức: Duyệt Trung thứ trên cây biểu thức (thường cần thêm dấu ngoặc) sẽ cho kết quả là biểu thức dạng trung tố (Infix Notation). Ví dụ, cây cho (A + B) * C sẽ có dạng Trung thứ là A + B * C (hoặc (A + B) * C nếu xử lý dấu ngoặc đúng cách).

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

Nguyên tắc:

Duyệt cây con bên trái (Left subtree).
Duyệt cây con bên phải (Right subtree).
Ghé thăm nút gốc (Root).

Cách hoạt động (với cây ví dụ trên):

Bắt đầu từ gốc (1). Chuyển sang cây con trái của 1 (gốc là 2).
- Tại nút 2: Chuyển sang cây con trái của 2 (gốc là 4).
  - Tại nút 4: Cây con trái là rỗng, cây con phải là rỗng.
  - Ghé thăm 4. In ra 4. Quay lại nút 2.
- Tại nút 2: Đã duyệt xong cây con trái (4). Chuyển sang cây con phải của 2 (gốc là 5).
  - Tại nút 5: Cây con trái là rỗng, cây con phải là rỗng.
  - Ghé thăm 5. In ra 5. Quay lại nút 2.
- Tại nút 2: Đã duyệt xong cây con trái (4) và phải (5). Ghé thăm 2. In ra 2. Quay lại nút 1.
Tại nút 1: Đã duyệt xong cây con trái (gốc 2). Chuyển sang cây con phải của 1 (gốc là 3).
- Tại nút 3: Cây con trái là rỗng, cây con phải là rỗng.
- Ghé thăm 3. In ra 3. Quay lại nút 1.
Tại nút 1: Đã duyệt xong cây con trái (gốc 2) và phải (gốc 3). Ghé thăm 1. In ra 1. Kết thúc.

Trình tự các nút được ghé thăm: 4 -> 5 -> 2 -> 3 -> 1

Code minh hoạ (Đệ quy):

// Hàm duyệt Hậu thứ (Post-order)
void postOrder(Node* root) {
    // Điều kiện dừng đệ quy
    if (root == nullptr) {
        return;
    }

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

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

    // 3. Ghé thăm nút gốc (In ra giá trị)
    std::cout << root->data << " ";
}

// Cách sử dụng: postOrder(root);

Giải thích code: Hàm postOrder cũng dùng đệ quy.

Dòng postOrder(root->left);: Gọi đệ quy duyệt toàn bộ cây con trái.
Dòng postOrder(root->right);: Sau khi cây con trái xong, gọi đệ quy duyệt toàn bộ cây con phải.
Dòng std::cout << root->data << " ";: Chỉ khi cả hai cây con trái và phải đã được duyệt xong, chúng ta mới ghé thăm (in giá trị) nút gốc hiện tại.

Ứng dụng của Duyệt Hậu thứ:

Xóa cây: Đây là ứng dụng kinh điển. Để xóa một cây một cách an toàn và giải phóng bộ nhớ, bạn cần xóa các nút con trước khi xóa nút cha. Duyệt Hậu thứ đảm bảo thứ tự này, vì nút cha chỉ được xử lý sau khi tất cả các con của nó đã được xử lý (xóa).
Tính toán giá trị của cây biểu thức: Duyệt Hậu thứ trên cây biểu thức sẽ cho kết quả là biểu thức dạng hậu tố (Postfix Notation hay Reverse Polish Notation). Việc tính toán giá trị từ biểu thức hậu tố là rất đơn giản dùng stack.
Giải phóng bộ nhớ các cấu trúc dữ liệu dạng cây: Tương tự như xóa cây, đảm bảo các tài nguyên liên quan đến nút con được giải phóng trước khi tài nguyên của nút cha.

Tóm tắt về DFS (Đệ quy)

Cả ba phép duyệt DFS đệ quy đều có cấu trúc rất giống nhau, chỉ khác thứ tự của ba dòng:

Gọi đệ quy cho cây con trái.
Xử lý nút gốc (ghé thăm).
Gọi đệ quy cho cây con phải.

Pre-order: 2, 1, 3
In-order: 1, 2, 3
Post-order: 1, 3, 2

Cài đặt phi đệ quy (Iterative) cho DFS: Mặc dù đệ quy là cách tự nhiên nhất, chúng ta cũng có thể cài đặt DFS bằng cách sử dụng một stack.

Pre-order (Iterative):
1. Đẩy gốc vào stack.
2. Trong khi stack không rỗng:
  - Lấy nút trên cùng ra khỏi stack (pop). Ghé thăm nút đó.
  - Đẩy con phải của nút đó vào stack (nếu có).
  - Đẩy con trái của nút đó vào stack (nếu có). (Đẩy con trái sau để nó được pop ra trước).
In-order (Iterative): Phức tạp hơn một chút, cần dùng stack để lưu các nút cha chưa được xử lý. Duyệt xuống tận cùng bên trái, đẩy các nút trên đường đi vào stack. Sau đó, pop nút từ stack, ghé thăm nó, và chuyển sang cây con phải của nó.
Post-order (Iterative): Phức tạp nhất trong ba loại, thường cần dùng hai stack hoặc một stack và giữ track về nút trước đó.

Do bài viết tập trung vào các phép duyệt và ứng dụng, chúng ta sẽ không đi sâu vào cài đặt phi đệ quy của DFS, nhưng hãy nhớ rằng chúng tồn tại và hữu ích trong trường hợp cây quá sâu gây tràn stack đệ quy.

II. Duyệt cây theo chiều rộng (Breadth-First Search - BFS)

Duyệt theo chiều rộng nghĩa là chúng ta sẽ ghé thăm tất cả các nút ở cùng một "mức" (level) trước khi chuyển sang mức tiếp theo. Phép duyệt theo chiều rộng duy nhất cho cây là Duyệt theo mức (Level-order Traversal).

4. Duyệt theo mức (Level-order Traversal)

Nguyên tắc: Ghé thăm tất cả các nút từ trái sang phải, từng mức một, bắt đầu từ mức 0 (mức của gốc).

Cách hoạt động (với cây ví dụ trên):

Mức 0: Duyệt nút gốc (1). Ghé thăm 1. In ra 1.
Mức 1: Duyệt các con của các nút ở mức 0, từ trái sang phải. Nút 1 có con trái là 2, con phải là 3. Ghé thăm 2, rồi 3. In ra 2 3.
Mức 2: Duyệt các con của các nút ở mức 1, từ trái sang phải. Nút 2 có con trái là 4, con phải là 5. Nút 3 không có con. Ghé thăm 4, rồi 5. In ra 4 5.
Mức 3: Duyệt các con của các nút ở mức 2. Nút 4 không có con. Nút 5 không có con. Không có nút nào ở mức 3. Kết thúc.

Trình tự các nút được ghé thăm: 1 -> 2 -> 3 -> 4 -> 5

Cài đặt (Phi đệ quy - sử dụng Queue): Duyệt theo mức thường được cài đặt bằng cách sử dụng một cấu trúc dữ liệu hàng đợi (queue). Hàng đợi tuân theo nguyên tắc FIFO (First-In, First-Out), rất phù hợp để xử lý các nút theo thứ tự mức.

#include <queue> // Cần include thư viện queue

// Hàm duyệt theo mức (Level-order)
void levelOrder(Node* root) {
    // Nếu cây rỗng, không làm gì cả
    if (root == nullptr) {
        return;
    }

    // Tạo một hàng đợi và thêm nút gốc vào
    std::queue<Node*> q;
    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 ra
        Node* currentNode = q.front();
        q.pop();

        // 2. Ghé thăm nút hiện tại (In ra giá trị)
        std::cout << currentNode->data << " ";

        // 3. Thêm nút con trái vào hàng đợi (nếu có)
        if (currentNode->left != nullptr) {
            q.push(currentNode->left);
        }

        // 4. Thêm nút con phải vào hàng đợi (nếu có)
        if (currentNode->right != nullptr) {
            q.push(currentNode->right);
        }
    }
}

// Cách sử dụng: levelOrder(root);

Giải thích code:

Dòng if (root == nullptr): Xử lý trường hợp cây rỗng.
Dòng std::queue<Node*> q;: Khai báo một hàng đợi để lưu trữ các con trỏ đến nút cần ghé thăm.
Dòng q.push(root);: Đưa nút gốc vào hàng đợi để bắt đầu quá trình.
Vòng while (!q.empty()): Vòng lặp chính chạy cho đến khi không còn nút nào trong hàng đợi để xử lý.
Dòng Node* currentNode = q.front(); q.pop();: Lấy nút ở đầu hàng đợi (nút đã được thêm vào sớm nhất) và loại bỏ nó khỏi hàng đợi.
Dòng std::cout << currentNode->data << " ";: Ghé thăm nút hiện tại.
Hai khối if sau đó: Nếu nút hiện tại có con trái hoặc con phải, chúng ta thêm chúng vào cuối hàng đợi. Điều này đảm bảo rằng chúng sẽ được xử lý sau tất cả các nút khác đã có sẵn trong hàng đợi ở mức hiện tại hoặc đã được thêm vào trước đó từ cùng mức.

Ứng dụng của Duyệt theo mức:

Tìm kiếm đường đi ngắn nhất trong cây (hoặc đồ thị không trọng số): BFS nói chung (và duyệt theo mức cho cây) tìm thấy đường đi ngắn nhất tính theo số cạnh từ nút bắt đầu đến bất kỳ nút nào khác.
Tìm chiều cao của cây: Duyệt theo mức có thể được sử dụng để tìm chiều cao của cây. Bạn có thể đánh dấu điểm kết thúc của mỗi mức (ví dụ, bằng cách thêm một con trỏ null hoặc đếm số nút ở mỗi mức) và tăng bộ đếm chiều cao sau khi xử lý xong một mức.
Phân tích cây theo cấu trúc mức: Hữu ích trong các bài toán cần xử lý hoặc phân tích dữ liệu theo từng lớp hoặc thế hệ trong cây.
Thu thập dữ liệu theo mức: Ví dụ, bạn muốn thu thập danh sách tất cả người quản lý cấp 1, sau đó cấp 2, v.v., trong một cây tổ chức.

III. Ví dụ tổng hợp và Chú thích

Hãy cùng tạo một cây và chạy tất cả các phép duyệt trên nó để xem kết quả.

#include <iostream>
#include <vector>
#include <queue> // Cần include cho levelOrder

// Định nghĩa cấu trúc Node của cây nhị phân (đã định nghĩa ở trên)
struct Node {
    int data;
    Node *left;
    Node *right;

    Node(int val) {
        data = val;
        left = right = nullptr;
    }
};

// Các hàm duyệt (đã định nghĩa ở trên)
void preOrder(Node* root) {
    if (root == nullptr) return;
    std::cout << root->data << " ";
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(Node* root) {
    if (root == nullptr) return;
    inOrder(root->left);
    std::cout << root->data << " ";
    inOrder(root->right);
}

void postOrder(Node* root) {
    if (root == nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    std::cout << root->data << " ";
}

void levelOrder(Node* root) {
    if (root == nullptr) return;
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* currentNode = q.front();
        q.pop();
        std::cout << currentNode->data << " ";
        if (currentNode->left != nullptr) q.push(currentNode->left);
        if (currentNode->right != nullptr) q.push(currentNode->right);
    }
}

int main() {
    // Xây dựng cây ví dụ:
    //         10
    //        /  \
    //       5    15
    //      / \     \
    //     2   7     18
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    root->left->left = new Node(2);
    root->left->right = new Node(7);
    root->right->right = new Node(18);

    std::cout << "Duyet Tien thu (Pre-order): ";
    preOrder(root); // Expected: 10 5 2 7 15 18
    std::cout << std::endl;

    std::cout << "Duyet Trung thu (In-order): ";
    inOrder(root); // Expected: 2 5 7 10 15 18 (Sorted for BST)
    std::cout << std::endl;

    std::cout << "Duyet Hau thu (Post-order): ";
    postOrder(root); // Expected: 2 7 5 18 15 10
    std::cout << std::endl;

    std::cout << "Duyet theo muc (Level-order): ";
    levelOrder(root); // Expected: 10 5 15 2 7 18
    std::cout << std::endl;

    // Lưu ý: Cần giải phóng bộ nhớ sau khi sử dụng (đặc biệt với cây lớn)
    // Việc giải phóng bộ nhớ cây thường dùng duyệt Post-order
    // (Đây chỉ là ví dụ đơn giản, không có hàm giải phóng chi tiết)

    return 0;
}

Output của chương trình trên:

Duyet Tien thu (Pre-order): 10 5 2 7 15 18
Duyet Trung thu (In-order): 2 5 7 10 15 18
Duyet Hau thu (Post-order): 2 7 5 18 15 10
Duyet theo muc (Level-order): 10 5 15 2 7 18

Bạn có thể thấy rõ sự khác biệt về trình tự duyệt giữa các phương pháp. Đặc biệt, phép duyệt Trung thứ trên cây này (đây là một ví dụ về Binary Search Tree) cho ra output đã được sắp xếp.

IV. Khi nào dùng phép duyệt nào?

Việc lựa chọn phép duyệt phụ thuộc vào yêu cầu của bài toán:

Duyệt Tiền thứ: Thường dùng khi bạn cần xử lý nút cha trước các nút con. Phù hợp cho việc sao chép cấu trúc cây hoặc khi thứ tự xử lý gốc là quan trọng nhất.
Duyệt Trung thứ: Chủ yếu dùng với Cây tìm kiếm nhị phân để lấy ra các phần tử theo thứ tự tăng dần. Cũng có thể dùng để biểu diễn biểu thức trung tố.
Duyệt Hậu thứ: Thường dùng khi bạn cần xử lý các nút lá và nút con trước nút cha. Phù hợp cho việc xóa cây, tính toán giá trị cây biểu thức hoặc các thao tác cần giải phóng tài nguyên theo thứ tự từ dưới lên.
Duyệt theo mức: Dùng khi bạn cần xử lý các nút theo từng mức, từ trên xuống dưới và từ trái sang phải. Phù hợp cho tìm kiếm đường đi ngắn nhất, phân tích theo cấu trúc tầng lớp, hoặc các bài toán cần xử lý đồng đều ở mỗi mức.

V. Độ phức tạp

Đối với tất cả các phép duyệt cơ bản (Pre-order, In-order, Post-order đệ quy/phi đệ quy, Level-order), chúng ta đều ghé thăm mỗi nút đúng một lần. Do đó:

Độ phức tạp thời gian: O(N), trong đó N là số lượng nút trong cây.
Độ phức tạp không gian:
- DFS (đệ quy): O(H) trong trường hợp tốt nhất/trung bình (cây cân bằng), trong đó H là chiều cao của cây. Tuy nhiên, trong trường hợp xấu nhất (cây suy biến thành danh sách liên kết), độ sâu đệ quy có thể lên tới N, dẫn đến độ phức tạp không gian O(N) cho stack gọi hàm.
- DFS (phi đệ quy với stack): O(H) hoặc O(N) tùy thuộc vào hình dạng cây, tương tự đệ quy nhưng chúng ta kiểm soát stack.
- BFS (Level-order với queue): O(W), trong đó W là chiều rộng lớn nhất của cây. Trong trường hợp xấu nhất (cây nhị phân đầy đủ ở mức cuối cùng), W có thể là N/2, dẫn đến độ phức tạp không gian O(N) cho queue.

Trong thực tế, nếu cây quá sâu, cài đặt DFS phi đệ quy với stack tường minh có thể tránh được lỗi tràn stack (stack overflow) so với đệ quy.

Comments

There are no comments at the moment.