Các bước thực hiện yêu cầu của bài tập xóa một nút trong cây nhị phân tìm kiếm bằng ngôn ngữ lập trình C như sau:

Bước 1: Khai báo 1 cấu trúc Node gồm có dữ liệu của Node int data, con trỏ đến cây con trái Node *left và con trỏ dến cây con phải Node *right. Định nghĩa cây nhị phân Node *Tree có gốc là Tree root.

Bước 2: Tạo hàm void Init (Tree &root). Trong hàm gán gốc về NULL root=NULL.

Bước 3: Tạo hàm tạo nút Node* CreateNode (int x). Trong hàm ta tạo một nút mới Node* p = new Node. Nếu p!=NULL ta gán cây con trái và phải của p bằng NULL(p->left=NULL, p->right=NULL) còn data của p=x (p->data=NUL). Trả về Node p.

Bước 4:Tạo hàm InsertNode(Tree &root, Node*p) để thêm nút vào cây. Trong hàm ta dùng if với điều kiện nếu gốc khác NULL (root!=NULL) thì dùng if với điều kiện nếu root=p->data thì trả về 0(gốc và nút p bằng nhau thì kết thúc), dùng tiếp if với điều kiện nếu root->data > p->data thì trả về InsertNode(root->left, p) (gốc lớn hơn nút p thì chuyển p sang cây con bên trái), ngược lại nếu nút p lớn hơn gốc thì p nằm bên phải gốc (return InsertNode(root->right,p)). Nếu gốc đang rỗng thì ta gán luôn root=p.

Bước 5: Tạo hàm Input(Tree &root) dùng để nhập dữ liệu cho cây. Trong hàm ta khai báo int n (số node của cây) và nhập dữ liệu cho n. Tiếp theo ta tạo vòng lặp for bắt đầu từ int i=1 kết thúc khi i<=n và mỗi lần lặp i tăng lên 1, trong vòng lặp ta khai báo biên int x (data của nút) rồi nhập dữ liệu cho x; sau đó tạo một nút p mới có data là x Node* p = CreateNode(x) rồi thêm nút đó vào cây InsertNode(root, p).

Bước 6: Tạo hàm void NLR(Tree root) dùng để duyệt cây theo tiền thứ tự. Trong hàm ta dùng if kiểm tra xem nếu gốc không rỗng (root!=NULL) thì ta in root->data ra màn hình, sau đó gọi dệ quy cây con trái NLR(root->left) rồi gọi đệ quy cây con phải NLR(root->right).

Bước 7: Ta tạo hàm Node* SearchNode(Tree root, int x) dùng để tìm kiếm nút trong cây. Trong hàm, ta dùng if để kiểm tra xem cây có khac rỗng không (root!=NULL) nếu có thì:

• Nếu root->data == x nếu data của nút = x thì ta trả về vị trí của root.
• Nếu root->data > x nếu data của nút > x thì ta gọi lại hàm tìm kiếm về cây con trái SearchNode(root->left, x).
• Ngược lại nếu data của nút < x thì ta gọi lại hàm tìm kiếm về cây con phải SearchNode(root->right, x).

Ngược lại nếu cây rỗng ta trả về NULL.

Bước 8: Trong hàm main khai báo cây Tree root rồi gọi hàm Init(root), Input(root), NLR(root) để hiển thị cây.

Bước 9: Ta khai báo biến int x là số nút muốn tìm kiếm. Nhập dữ liệu cho x và khai báo Node *p = SearchNode(root,x). Dùng if kiểm tra nếu p == NULL (cây rỗng) thì không tìm thấy nút ngược lại tìm thấy x.

Bước 10: Chạy chương trình.

Chương trình giải bài tập tìm kiếm một nút trong cây nhị phân tìm kiếm bằng ngôn ngữ lập trình C như sau:

#include <stdio.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;
};
//Cay nhi phan Tree
typedef struct Node* Tree;
//goc root
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 node p duoc cap phat bo nho
    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 CUA CAY: "); 
    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){
        //hien thi du lieu cua tung node sau khi duyet
        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);
    }
}
Node* SearchNode(Tree root, int x){
    //neu cay khong rong
    if(root!=NULL){
        //neu data cua node goc bang x can tim
        if(root->data == x){
            //tra ve node goc cua cay
            return root;
        }
        //neu data cua node goc lon hon x can tim  
        if(root->data > x){
            //goi lai ham tim kiem theo cay con trai
            return SearchNode(root->left, x);
        }else{//nguoc lai data cua node goc nho hon x can tim
            //goi lai ham tim kiem theo cay con phai
            return SearchNode(root->right, x);
        }
    }
    //neu khong tim thay node co data bang x thi tra ve rong
    return NULL;
}
int main(){
    //tao cay voi node goc la root
    Tree root;
    //khoi tao cay
    Init(root);
    //nhap n phan tu vao cay
    Input(root);
    printf("\nCAY SAU KHI DUYET:\n");
    //duyet cay theo tien thu tu
    NLR(root);
    int x;//so nut muon tim kiem
    printf("\nNHAP NUT MUON TIM:");
    scanf("%d",&x);
    Node *p = SearchNode(root,x);
    if(p == NULL){//neu node p la rong
        printf("Khong tim thay node");
    }else{
        printf("Tim thay phan tu %d", x);
    }
}

Kết quả:

NHAP SO LUONG NODE CUA CAY: 5
NHAP DATA CUA NODE 1: 10
NHAP DATA CUA NODE 2: 12
NHAP DATA CUA NODE 3: 9
NHAP DATA CUA NODE 4: 13
NHAP DATA CUA NODE 5: 7

CAY SAU KHI DUYET:
10      9       7       12      13
NHAP NUT MUON TIM:12
Tim thay phan tu 12

Bạn cũng có thể thử tìm kiếm nút trong cây bằng phương pháp sau:

Node* SearchNode(Tree root, int x){
    //tao va gan node p bang node goc
    Node *p = root;
    //duyet tu node goc den het cay
    while (p != NULL){
        //neu co data cua node p dang xet bang x can tim
        if(p->data==x){
            //tra ve node dang duoc xet
            return p;
        }else{
            //neu phan tu x can tim nho hon data cua node dang xet
            if(x < p->data){
                //tim kiem theo cay con trai
                p = p->left;
            }else{//nguoc lai neu phan tu x can tim lon hon data cua node dang xet
                //tim kiem theo cay con phai
                p = p->right;
            }
        }
    }
    //neu khong tim thay node co data bang x thi tra ve rong
    return NULL;
}

3. Tổng kết

Sau khi làm bài tập này các bạn cần phải hiểu và nắm được những kiến thức sau:

• Cách nhập xuất cơ bản trong ngôn ngữ lập trình C.
• cách dùng vòng lặp for trong C để duyệt từng phần tử.
• Cách sử dụng struct trong C.
• Cấu trúc cây nhị phân tìm kiếm trong C.
• Cách duyệt cây trong C.
• Cách tìm kiếm nút trong cây nhị phân tìm kiếm C.