Các node (hay các phần tử) của cây đều không tự sinh ra. Vì thế mà khi có một cây nhị phân tìm kiếm, việc đầu tiên ta cần thao tác đó là thêm phần tử vào cây đó trước sau đó mới thực hiện được một số thao tác như: duyệt, tìm kiếm, xóa…
Để thực hiện thêm phần tử vào một cây nhị phân tìm kiếm ta cần tuân theo điều kiện đó là nếu: node được thêm vào bé hơn node gốc sẽ được đặt vào bên trái node gốc, node được thêm vào lớn hơn node gốc sẽ được đặt vào bên phải node gốc.
1.Cách thêm phần tử vào trong cây nhị phân
Việc thêm một node p vào cây phải bảo đảm điều kiện ràng buộc của cây nhị phân tìm kiếm. Cách để ta thêm một phần tử vào trong cây nhị phân tìm kiếm đó là ta sẽ đi kiểm tra khóa (hay data) của 2 node đó là node p và root sau đó ta sử dụng đệ quy cho từng trường hợp như sau:
- Đầu tiên ta sẽ kiểm tra điều kiện của node root, nếu như node root rỗng thì ta gán luôn root = p . Ngược lại, không rỗng thì thực hiện các bước bên dưới:
- Nếu như p->data > root->data , nghĩa là data của node p nhỏ hơn data của node root thì gọi đệ quy lại quá trình chèn ở cây con phải.
- Nếu như p->data < root->data , nghĩa là data của node p lớn hơn data của node root thì gọi đệ quy lại quá trình chèn ở cây con trái.
- Nếu như root->data = p->data , nghĩa là data của node p bằng với data của node root thì dừng lại quá trình đệ quy.
Để hiểu rõ hơn về các bước trên, mời bạn đọc xem ví dụ dưới đây minh họa việc thêm một phần tử vào trong cây nhị phân tìm kiếm.
2.Hàm thêm phần tử vào trong cây nhị phân
Hàm thêm phần tử vào trong cây sẽ là một hàm đệ quy vì trong quá trình thêm phần tử sẽ gọi lại chính hàm này để thêm phần tử vào trong cây theo đúng quy tắc của cây nhị phân tìm kiếm.
Hàm int InsertNode(Tree &root, Node *p) dưới đây nhận đầu vào là node gốc Tree &root và Node *p là phần tử cần thêm vào cây:
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;
}
}
Hàm trên khi được gọi ra sẽ thực hiện thêm 1 phần tử vào trong cây nhị phân tìm kiếm. Tuy nhiên để thực hiện cho việc thêm nhiều phần tử vào trong cây ta sẽ đi xây dựng một hàm sử dụng lại hàm InsertNode() ở trên để thực hiện thêm N phần tử vào trong cây!
Ta sẽ đi xây dựng một hàm void Input(Tree &root) nhận đầu vào là node gốc Tree &root sau đó thực hiện nhập vào N phần tử cho cây ở trong vòng lặp và thông qua hàm InsertNode(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);
}
}
Chú ý: Hàm CreateNode(x) đã được nêu ở bài trước. Hàm này có chức năng tạo ra một node của cây trước khi đưa vào hàm InsertNode(root,p)
Ở trên mới ta mới chỉ có hàm nhập cây, tuy nhiên sau khi nhập ta cần phải hiển thị dữ liệu đó ra, tôi sẽ cung cấp cho các bạn một hàm duyệt cây để các có thể chạy thử nghiệm kết quả:
void NLR(Tree root){
if (root!=NULL){
//hien thi du lieu cua tung node sau khi duyet
printf(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("%d \t",root->right);
}
}
Ngoài hàm duyệt cây ở trên, còn thêm một số hàm duyệt cây theo từng cách khác, chi tiết về các hàm duyệt cây sẽ được đề cập ở bài sau, ở bài này bạn hãy coppy chúng và đưa vào trương trình nếu muốn hiển thị được dữ liệu sau khi nhập vào cây!
3.Chương trình thêm phần tử vào trong cây nhị phân
Để hiểu rõ hơn về việc thêm phần tử vào cây nhị phân, mời bạn đọc cùng tham khảo đoạn code hoàn chỉnh dưới đây!
#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 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 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){
//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);
//them mot phan tu moi vao trong cay
int x = 15;
Node *p = CreateNode(x);
InsertNode(root,p);
//hien thi tat ca du lieu vua them vao cay
NLR(root);
}
Chương trình dưới đây chỉ dừng lại ở việc cài đặt hoàn chỉnh thao tác thêm phần tử vào trong cây nhị phân tìm kiếm. Chương trình khi được thực thi vẫn chưa hiển thị ra được kết quả nào vì ta chưa có hàm duyệt cây. Trong bài sau ta sẽ đi tìm hiểu về các phương pháp duyệt cây và đi xây dựng những hàm duyệt cây. Mời bạn đọc cùng đón xem!
