Tiền đề cho bài học

Để nắm rõ kiến thức của bài học này bạn cần nắm được khái niệm chung về cây nhị phân,thuật toán đệ quy và ngăn xếp. bạn có thể đọc các kiến thức này ở các đường dẫn sau:

Cây nhị phân
Thuật toán đệ quy (Recursion)
Ngăn xếp (Stack)

Chú ý:

Trong bài học này tôi sử dụng các từ stack và ngăn xếp xen kẽ nhau.

Push: Chứa một phần tử vào đỉnh ngăn xếp.

Pop: Lấy một phần tử từ đỉnh ngăn xếp

Phương thức duyệt cây theo chiều sâu

Hình 1: Cây nhị phân

Như đã đề cập ở bài trước, chúng ta có hai cách thức duyệt cây chính là duyệt theo chiều rộng và duyệt theo chiều sâu. Ở bài này sẽ giới thiệu chi tiết hơn về cách thức duyệt cây theo chiều sâu.

Có 3 cách duyệt mà chúng ta sẽ đi vào tìm hiểu chi tiết trong bài này đó là: Preorder, Inorder, Postorder.

Các cách duyệt cây này khác nhau ở thứ tự mà chúng ta duyệt qua các cây con bên trái, bên phải và node gốc.

Để cho dễ ghi nhớ về cách thức, thứ tự duyệt của từng loại, ta xét bảng sau:


Cách duyệt	Thứ tự
Preorder	<gốc>	<cây con trái>	<cây con phải>
Inorder	<cây con trái>	<gốc>	<cây con phải>
Postorder	<cây con trái>	<cây con phải>	<gốc>

Bảng 1: Các cách duyệt cây theo chiều sâu

Bạn có thể thấy ở trong bảng trên, các node gốc tạo thành một đường chéo và cây con trái luôn luôn được duyệt trước cây con phải trong mọi trường hợp.

Preorder

Các bước để duyệt cây với Preorder như sau:

Bước 1: Thăm node gốc.

Bước 2: Thăm cây con bên trái (thăm tất cả các node của cây con bên trái)

Bước 3: Thăm cây con bên phải (thăm tất cả các node của cây con bên phải).

Hình 2: Mô tả duyệt cây Preorder

Các số 1, 2, 3 trong hình 2 tương ứng với các bước duyệt cây theo thứ tự của preoder.

Với thứ tự duyệt như vậy ta thu được thứ tự các node được thăm trong hình 2 như sau: A, B, D, H, I, E, J, C, F, G

Thực hiện chương trình duyệt cây Preorder với C/C++

Ta đặt hàm thực hiện duyệt cây preoder là void Preorder(struct Node *root). Hàm này nhận địa chỉ của node gốc như là đối số. Loại dữ liệu của đối số là con trỏ tới Node. Node được định nghĩa như một cấu trúc với ba trường gồm data và hai trường chứa địa chỉ của con trái và con phải.

struct Node{
    int data;
    struct Node *left;
    struct Node *right;
};

Nội dung hàm như sau:

void Preorder(struct Node *root)
{
    /* Ta không thể gọi đệ quy hàm mãi mãi, nên ta cần điều kiện dừng */
    /* Việc gọi đệ quy sẽ kết thúc khi cây hoặc cây con rỗng */
    /* Hay nói cách khác, việc gọi đệ quy sẽ kết thúc khi node gốc là NULL */
    if(root == NULL) return;
    /* Đầu tiên hàm sẽ thăm và in ra dữ liệu ở node gốc */
    cout << root->data << " ";
    /* Giờ ta sẽ gọi đệ quy để thăm các node của cây con bên trái */
    /* Đối số được truyền vào là địa chỉ con trái của node gốc hiện tại */
    /* Bởi vì con trái của node gốc hiện tại sẽ là node gốc của cây con trái */
    Preorder(root->left); 
    /* Tiếp theo ta gọi đệ quy để thăm các node của cây con bên phải */
    /* Đối số được truyền vào là địa chỉ con phải của node gốc hiện tại */
    /* Bởi vì con phải của node gốc hiện tại sẽ là node gốc của cây con phải*/
    Preorder(root->right);
}

Thực hiện chương trình duyệt cây Inorder với C/C++

Các bước để duyệt cây với Inorder như sau:

Bước 1:Thăm con bên trái.

Bước 2: Thăm node gốc.

Bước 3: Thăm con bên phải.

Xét hàm void Inorder(struct Node *root)


void Inorder(struct Node *root)
{
    if(root == NULL) return;
    /* Đầu tiên ta gọi đệ quy để thăm các con bên trái */
    /* Đối số được truyền vào là địa chỉ con trái của node gốc hiện tại */
    Inorder(root->left); 
    /* Sau đó thăm và in ra dữ liệu ở node gốc */
    cout << root->data << " ";
    /* Tiếp theo ta gọi đệ quy để thăm các con bên phải */
    /* Đối số được truyền vào là địa chỉ con phải của node gốc hiện tại */
    Inorder(root->right); 
}

Thực hiện chương trình duyệt cây Postorder với C/C++

Các bước để duyệt cây với Postorder như sau:

Bước 1:Thăm con bên trái.

Bước 2: Thăm con bên phải.

Bước 3: Thăm node gốc.

Xét hàm void PostOrder (struct Node *root)

void PostOrder(struct Node *root)
{
    if(root == NULL) return;
    /* Đầu tiên ta gọi đệ quy để thăm các con bên trái */
    /* Đối số được truyền vào là địa chỉ con trái của node gốc hiện tại */
    PostOrder(root->left); 

    /* Tiếp theo ta gọi đệ quy để thăm các con bên phải */
    /* Đối số được truyền vào là địa chỉ con phải của node gốc hiện tại */
    PostOrder(root->right);
    /* Sau đó thăm và in ra dữ liệu ở node gốc */
    cout << root->data << " ";
}

Các bạn có thể lấy toàn bộ mã nguồn của chương trình chạy được để kiểm thử trong đường dẫn này (https://gitlab.com/thevngeek/basic-data-structure/blob/master/duyetcaytheochieusau.cpp).

Tài liệu tham khảo

https://gist.github.com/mycodeschool/10016271
https://en.wikipedia.org/wiki/Tree_traversal#Pre-order

Có điều gì thắc mắc hay muốn góp ý để cải thiện cho bài viết bạn vui lòng để lại bình luận ở phía bên dưới. Chúng tôi sẽ trả lời nhanh nhất có thể để giải đáp các thắc mắc của các bạn.

Uncategorized

Duyệt cây theo chiều sâu