1. Bài tập thêm nút mới vào 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 thêm nút mới vào 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 thêm nút mới vào 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: 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 8: Ta khai báo biến int x là số nút muốn thêm. Ta dùng vòng lặp for bắt đầu từ int i=1, kết thúc khi i<=x, mỗi lần lặp i tăng lên 1. Trong vòng lặp ta khai báo biến int data (dữ liệu của từng nút) và nhập dữ liệu cho data; khai báo con trỏ Node*p = CreateNode(data) (tạo nút mới) rồi thêm node vào cây InsertNode(root,p).
Bước 9: Duyệt lại cây bằng hàm NLR(root) rồi chạy chương trình.
Chương trình giải bài tập thêm nút mới vào 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);
}
}
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 LA:\n");
//duyet cay theo tien thu tu
NLR(root);
int x;//so nut muon them
printf("\nNHAP SO NUT MUON THEM:");
scanf("%d",&x);
for(int i=1;i<=x;i++){
int data;//du lieu cua nut muon them
printf("DATA NODE THEM THU %d:",i);
scanf("%d",&data);
Node*p = CreateNode(data);//tao nut moi
InsertNode(root,p);//them nut vao cay
}
printf("\nCAY SAU KHI THEM LA:\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 LA: 10 9 7 13 15 NHAP SO NUT MUON THEM:3 DATA NODE THEM THU 1:4 DATA NODE THEM THU 2:20 DATA NODE THEM THU 3:14 CAY SAU KHI THEM LA: 10 9 7 4 13 15 14 20
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.
- Thêm nút vào cây trong C.
