Vấn đề sau khi nhập các node vào cây đó là việc duyệt cây. Khác với cấu trúc dữ liệu khác, ở trong cấu trúc dữ liệu cây ta sẽ có nhiều cách khác nhau để duyệt một cây. Trong bài này tôi sẽ đưa ra 3 phương pháp duyệt cây đó là:

• Duyệt cây theo tiền thứ tự
• Duyệt cây theo trung thứ tự
• Duyệt cây theo hậu thứ tự

Chú ý: Mọi thao tác duyệt cây đều có sử dụng phương pháp đệ quy!

1.Duyệt cây theo tiền thứ tự – NLR

Duyệt cây theo tiền thứ tự hay duyệt theo Node – Left – Right (NLR) là việc ban đầu thực hiện ghé thăm node gốc, tiếp sau đó ghé thăm đến cây con trái và cuối cùng là ghé thăm cây con phải.

void NLR(Tree root){
    if (root!=NULL){
        //xu ly node goc
        printf("%d \t",root->data);
        //su dung de quy de duyet tiep cay con trai
        NLR(root->left);
        //su dung de quy de duyet tiep cay con phai
        NLR(root->right);
    }
}

2.Duyệt cây theo trung thứ tự – LNR

Duyệt cây theo trung thứ tự hay duyệt theo Left – Node – Right là việc ban đầu sẽ ghé thăm cây con trái, tiếp theo ghé thăm đến node gốc và cuối cùng là ghé thăm cây con phải.

void LNR(Tree root){
    if (root!=NULL){
        //su dung de quy de duyet tiep cay con trai
        LNR(root->left);
        //xu ly node goc
        printf("%d \t",root->data);
        //su dung de quy de duyet tiep cay con phai
        LNR(root->right);
    }
}

3. Duyệt cây theo hậu thứ tự – LRN

Việc duyệt cây theo hậu thứ tự hay duyệt theo Left – Right -Node là việc ban đầu sẽ ghé thăm cây con trái, tiếp theo ghé thăm đến cây con phải và cuối cùng mới thực hiện ghé thăm node gốc.

void LRN(Tree root){
    if (root!=NULL){
        //su dung de quy de duyet tiep cay con trai
        LRN(root->left);
        //su dung de quy de duyet tiep cay con phai
        LRN(root->right);
        //xu ly node goc
        printf("%d \t",root->data);
    }
}

4.Chương trình hoàn chỉnh duyệt cây theo NLR – LNR – LRN

Trước khi đến với chương trình duyệt cây, đầu tiên bạn hay đảm bảo đã có thể thêm các node vào cây trước! Sau đó ta có thể hoàn toàn sử dụng 1 trong 3 phương pháp ở trên (tùy vào yêu cầu) để duyệt cây nhị phân!

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    //khai bao du lieu cua node co kieu du lieu int
    int data;
    //khai bao con tro den cay con trai
    Node* left;
    //khai bao con tro den cay con phai
    Node* right;

};
typedef struct Node* Tree;
Tree root;

void Init (Tree &root){   
    //gan node goc ve NULL
    root = NULL;
}

Node* CreateNode (int x){
    //tao node moi
    Node* p = new Node;
    //neu cay nhi phan khong rong
    if (p != NULL){
        //gan cay con trai va cay con phai mac dinh bang NULL
        p->left = NULL;
        p->right = NULL;
        //gan data bang x
        p->data = x;
    }
    //tra ve node p
    return p;
}
int InsertNode(Tree &root, Node*p){
    //neu node root khac rong thi thuc hien them vao cay
    if (root != NULL){
        //neu 2 data cua 2 node bang nhau thi ket thuc
        if (root->data==p->data){
            return 0;
        }
        //neu khoa cua root lon hon khoa cua p thi goi de quy trai 
        if (root->data > p->data){
            return InsertNode(root->left, p);
        }
        else{//neu khoa cua root nho hon khoa cua p thi goi de quy phai 
            return InsertNode(root->right,p);
        }
    }else { //truong hop neu node root la rong thi them node p vao node root
        root = p;
    }
}

void Input(Tree &root){
    int n;
    printf ("NHAP SO LUONG NODE CAN THEM: "); 
    scanf("%d",&n);
    for(int i=1; i<=n;i++){
        int x;
        printf ("NHAP DATA CUA NODE %d: ",i); 
        scanf("%d",&x);
        //tao node p co data = x
        Node* p = CreateNode(x);
        //them node p co data x vao trong cay
        InsertNode(root, p);
    }
}

void NLR(Tree root){
    if (root!=NULL){
        //xu ly node goc
        printf("%d \t",root->data);
        //su dung de quy de duyet tiep cay con trai
        NLR(root->left);
        //su dung de quy de duyet tiep cay con phai
        NLR(root->right);
    }
}

void LNR(Tree root){
    if (root!=NULL){
        //su dung de quy de duyet tiep cay con trai
        LNR(root->left);
        //xy ly node goc
        printf("%d \t",root->data);
        //su dung de quy de duyet tiep cay con phai
        LNR(root->right);
    }
}

void LRN(Tree root){
    if (root!=NULL){
        //su dung de quy de duyet tiep cay con trai
        LRN(root->left);
        //su dung de quy de duyet tiep cay con phai
        LRN(root->right);
        //xu ly node goc
        printf("%d \t",root->data);
    }
}

int main(){
    //tao cay voi node goc la root
    Tree root;
    //khoi tao cay
    Init(root);
    //nhap n phan tu vao cay
    Input(root);
    //duyet cay theo NLR
    printf("Duyet cay theo NLR\n");
    NLR(root);
    //duyet cay theo LNR
    printf("\nDuyet cay theo LNR\n");
    LNR(root);
    //duyet cay theo LRN
    printf("\nDuyet cay theo LRN\n");
    LRN(root);
}