1. 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
Bài tập này chúng ta sẽ sử dụng các kiến thức từ ngôn ngữ lập trình C như: cách nhập xuất dữ liệu 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 qua từng phần tử, cách sử dụng hàm trong C, các dùng struct trong C.
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.
2. Lời giải
Để thực hiện bài toán này chúng ta cần có kiến thức cơ bản về ngôn ngữ lập trình C, các cách nhập xuất chuỗi cơ bản trong C, cách dùng vòng lặp for trong C để duyệt qua từng phần tử, cách sử dụng hàm trong C, các dùng struct trong C.
Để hiểu hơn về bài tập này bạn có thể tìm hiểu nhiều hơn về cây nhị phân từ chương trình học của chúng tôi Tại Đây
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 void FindReplNode(Tree &p, Tree &q) dùng để tìm nút thế vào nút đã xóa. Trong hàm, dùng if với điều kiện nếu q->left thỏa mãn ta gọi đệ quy FindReplNode(p, q->left). Ngược lại ta gán p->data = q->data, p = q, q = q->right.
Bước 8: Tạo hàm void DeleteNode(Tree &root, int X) dùng để xóa nút trong cây.
- Dùng if kiểm tra cây có rỗng hay không (root== NULL) nếu có thì kết thúc.
- Nếu root->data > X thì return DeleteNode(root->left, X) về bên trái.
- Nếu root->data < X thì return DeleteNode(root->right,X) về bên phải.
- Tạo 1 nút mới thay thế nút đã xóa Node* p = root.
- Nếu root->right == NULL thì gán root = root->right.
- Nếu root->left == NULL thì gán root = root->left.
- Ngược lại gọi hàm FindReplNode (p, root->right).
- Xóa đi nút p (delete p).
Bước 9: 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 10: Ta khai báo biến int X là số nút muốn xóa. Nhập dữ liệu cho X và gọi hàm DeleteNode(root,X) rồi duyệt lại cây bằng hàm NLR(root).
Bước 11: Chạy chương trình.
Chương trình giải 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:
#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);
}
}
void FindReplNode(Tree &p, Tree &q){
if(q->left){
FindReplNode(p, q->left);
}else{
p->data = q->data;
p = q;
q = q->right;
}
}
void DeleteNode(Tree &root, int X){
//neu cay rong thi ket thuc ham xoa
if(root== NULL){
return;
}
//neu khoa X nho hon data cua node dang xet
if(root->data > X){
//de quy ham xoa theo nhanh trai
return DeleteNode(root->left, X);
}
//neu khoa X lon hon data cua node dang xet
if (root->data < X){
//de quy ham xoa theo nhanh phai
return DeleteNode(root->right, X);
}
//tao node p lam node the mang
Node* p = root;
//neu cay con trai la rong
if(root->left == NULL){
//gan lai node goc theo nhanh phai
root = root->right;
}else if(root->right == NULL){//neu cay con phai la rong
//gan lai node goc theo nhanh trai
root = root->left;
}else{ // nguoc lai, neu cay co du 2 con
//su dung node the mang
FindReplNode (p, root->right);
}
//xoa di node p
delete p;
}
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;//nut muon xoa
printf("\nNHAP NUT MUON XOA:");
scanf("%d",&X);
DeleteNode(root,X);
printf("\nCAY SAU KHI XOA:\n");
//duyet cay theo tien thu tu
NLR(root);
}
Kết quả:
NHAP SO LUONG NODE CUA CAY: 5 NHAP DATA CUA NODE 1: 10 NHAP DATA CUA NODE 2: 9 NHAP DATA CUA NODE 3: 13 NHAP DATA CUA NODE 4: 7 NHAP DATA CUA NODE 5: 15 CAY SAU KHI DUYET: 10 9 7 13 15 NHAP NUT MUON XOA:7 CAY SAU KHI XOA: 10 9 13 15
Bạn cũng có thể xóa toàn bộ các nút trong cây bằng cách sau:
void RemoveTree(Tree &root){
//neu van ton tai node goc
if(root){
//de quy sang nhanh trai
RemoveTree(root->left);
//de quy sang nhanh phai
RemoveTree(root->right);
//xoa node goc
delete(root);
}
}
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 xóa nút trong cây nhị phân tìm kiếm C.
