Code Cây Nhị Phân C++ - Thư Viện Hướng Dẫn

Cây tìm kiếm nhị phân

Cây tìm kiếm ứng với n khóa {\displaystyle k_{1},k_{2},…k_{n}} {\displaystyle k_{1},k_{2},…k_{n}} là cây nhị phân mà mỗi nút đều được gán một khóa sao cho với mỗi mỗi nút k:

Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút k Mọi khóa trên cây con phải đều lớn hơn khóa trên nút k Cây tìm kiếm nhị phân là một cấu trúc dữ liệu cơ bản được sử dụng để xây dựng các cấu trúc dữ liệu trừu tượng hơn như các tập hợp, đa tập hợp, các dãy kết hợp.

Nếu một BST có chứa các giá trị giống nhau thì nó biểu diễn một đa tập hợp. Cây loại này sử dụng các bất đẳng thức không nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ hơn khóa của nút cha, mọi nút trên cây con phải có nút lớn hơn hoặc bằng khóa của nút cha.

Nếu một BST không chứa các giá trị giống nhau thì nó biểu diễn một tập hợp đơn trị như trong lý thuyết tập hợp. Cây loại này sử dụng các bất đẳng thức nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ hơn khóa của nút cha, mọi nút trên cây con phải có khóa lớn hơn khóa của nút cha.

Việc chọn đưa các giá trị bằng nhau vào cây con phải (hay trái) là tùy theo mỗi người. Một số người cũng đưa các giá trị bằng nhau vào cả hai phía, nhưng khi đó việc tìm kiếm trở nên phức tạp hơn.

Ở đây có một vài thao tác với cây nhị phân được code bằng C++:

#include typedef struct tagnode { int data; struct tagnode *pleft;// nhánh bên trái struct tagnode *pright;//nhánh bên phải }tNode; typedef struct tagtree { tNode *root; }TREE;// khai báo 1 cáy (TREE) có kiểu dữ liệu là tNode void init(TREE &t) { t.root=NULL; } // khởi tạo cây NULL tNode *Createnode(int data) { tNode *p; p=new tNode; if(p!=NULL) { p->data=data; p->pleft=NULL; p->pright=NULL; } return p; }// hàm tạo 1 node void insert(tNode *&r,int data) { if(r==NULL) r=Createnode(data); else if(r->data>data) insert(r->pleft,data); else insert(r->pright,data); }// thêm 1 node vào cây, nếu nhỏ hơn thì bên trái, lớn hơn thì bên phải, dữ liệu là số nguyên data void insert1(TREE &t,int data) { insert(t.root,data); } void print(tNode *r) { if(r==NULL) return; print(r->pleft); printf("%4d",r->data); print(r->pright); }// hàm in danh sách cây void print(TREE t) { print(t.root); }// in cả cây nhị phân void timthemang(tNode *&p,tNode *&q) { if(q->pleft!=NULL) timthemang(p,q->pleft); else { p->data=q->data; p=q; q=q->pright; } }// hàm tìm 1 node trên cây int del(tNode *&p,int data) { if(p==NULL) return 0; if(p->data>data) del(p->pleft,data); if(p->datapright,data); if(p->data==data) { tNode *p1=p; if(p->pleft==NULL) p=p->pright; else if(p->pright==NULL) p=p->pleft; else { tNode *q=p->pright; timthemang(p1,q); } delete p1; } return 0; }// hàm xóa 1 node trên cây void demnode(tNode *p,int &dem) { if(p==NULL) return ; demnode(p->pleft,dem); dem++; demnode(p->pright,dem); }// hàm đếm node trên cây, với biến dem là tham biến int demnode1(tNode *t) { if(t==NULL) return 0; int x=demnode1(t->pleft); int y=demnode1(t->pright); /* if(r->pleft==NULL&&r->pright==NULL) return 1; return(x+y); */ return x+y+1; }//hàm đếm node trên cây, với kêt quả trả về là số lượng node trên cây void demla(tNode *t,int &dem) { if(t==NULL) return; if(t->pleft==NULL) if(t->pright==NULL) dem++; demla(t->pleft,dem); demla(t->pright,dem); }// đếm nút là, và nút cuối cùng ở các nhánh void docaonode(tNode *t,int data,int &dem) { if(t->data>data) { docaonode(t->pleft,data,dem); } else if(t->datapright,data,dem); } else { return; } dem++; }// hàm đếm độ cao của cây, tức là nhánh có nhiều nút nhất //tim kiem tNode* timnode(tNode *t,int data) { if(t) { if(t->data==data) return t; if(t->data>data) return timnode(t->pleft,data); else return timnode(t->pright,data); } return NULL; }// hàm tìm kiếm 1 data cho trước, kêt quả null là không tìm thấy, ngược lại sẽ trả về node đó int tinhchieucaonut(tNode *r) { if(r==NULL) return 0; if(r->pleft==NULL&&r->pright==NULL) return 0; int h1=tinhchieucaonut(r->pleft); int h2=tinhchieucaonut(r->pright); return 1+(h1>h2?h1:h2); }// tính chiều cao của cây // hàm chính để gọi các hàm cần chạy void main() { TREE t; init(t); int n,data,dem=0; printf("nhap so luong"); scanf("%d",&n); for(int i=0;i