1. Bài tập duyệt 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 đưa ra cho chúng ta là nhập vào một cấu trúc cây nhị phân tìm kiếm và duyệt cây 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 nhập vào một cấu trúc cây nhị phân tìm kiếm và duyệt cây 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) rồi chạy chương trình.
Chương trình giải bài tập nhập vào một cấu trúc cây nhị phân tìm kiếm và duyệt cây 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){//duyet tien thu tu
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);
//duyet cay theo tien thu tu
printf("CAY DUYET THEO TIEN THU TU:\n")
NLR(root);
}
Kết quả:
NHAP SO LUONG NODE CUA CAY: 5 NHAP DATA CUA NODE 1: 10 NHAP DATA CUA NODE 2: 13 NHAP DATA CUA NODE 3: 15 NHAP DATA CUA NODE 4: 9 NHAP DATA CUA NODE 5: 7 CAY DUYET THEO TIEN THU TU: 10 9 7 13 15
Bạn cũng có thể duyệt cây theo phương pháp dưới đây.
- Duyệt cây trung thứ tự:
void LNR(Tree root){//duyet trung thu tu
if (root!=NULL){
//su dung de quy de duyet tiep cay con trai
LNR(root->left);
//hien thi du lieu cua tung node sau khi duyet
printf("%d \t",root->data);
//su dung de quy de duyet tiep cay con phai
LNR(root->right);
}
}
- Duyệt cây hậu thứ tự:
void LRN(Tree root){//duyet hau thu tu
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);
//hien thi du lieu cua tung node sau khi duyet
printf("%d \t",root->data);
}
}
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.
