Bài này sẽ giúp chúng tạo ra một cây nhị phân.Và tổng hợp các hàm về cây nhị phân như: Tạo cây, thêm nút,nhập cây, duyệt cây,hủy cây,đếm nút lá, tìm độ cao của cây,xóa nút, đếm nút của 1 con bên phải. Mình đã tổng hợp các hàm trên thành 1 bài hoàn chỉnh(Viết theo ngôn ngữ C++ trên visual studio 2010)
Sau đây là code:
#include <iostream>
using namespace std;
struct tnode
{
int key;
struct tnode *pLeft,*pRight;
};
typedef struct tnode TNODE;
typedef TNODE * TREE;
int ThemNut(TREE &t, intx)
{
if(t==NULL)
{
t=new TNODE;
if(t==NULL) return-1;
t->key=x;
t->pLeft=t->pRight=NULL;
return 1;
}
if(x==t->key)
return 0;
if(x>t->key) ThemNut(t->pRight,x);
else ThemNut(t->pLeft,x);
}
void NhapCay(TREE &t)
{
int x,kt;
do
{
cout<<"Nhap gia tri cho mot nut: ";
cin>>x;
kt=ThemNut(t,x);
if(kt==0||kt==-1)
return;
}while(true);
}
void DuyetNLR(TREE t)
{
//if(t==NULL);
if(t!=NULL)
{
cout<<t->key<<" ";// Node
DuyetNLR(t->pLeft);//Left
DuyetNLR(t->pRight);//Right
}
}
void HuyCay(TREE &t)
{
if(t!=NULL)
{
HuyCay(t->pLeft);
HuyCay(t->pRight);
delete t;
}
}
int DemNutLa(TREE t)
{
if(t==NULL)
return 0;
if(t->pLeft==0 && t->pRight==0)
return 1;
int demtrai=DemNutLa(t->pLeft);
int demphai=DemNutLa(t->pRight);
return demtrai+demphai;
//return DemNutLa(t->pLeft)+DemNutLa(t->pRight);
}
int DemNutMotConPhai(TREE t)
{
if(t==NULL)
return 0;
if(t->pLeft==NULL && t->pRight!=NULL)
return 1 + DemNutMotConPhai(t->pRight);
return DemNutMotConPhai(t->pLeft) + DemNutMotConPhai(t->pRight);
}
int DoCaoCay(TREE t) // khi su dung ham nay ban nho tru di 1 nha
{
if(t==NULL) return 0;
int d1=DoCaoCay(t->pLeft);
int d2=DoCaoCay(t->pRight);
if(d1>d2) returnd1+1;
else return d2+1;
}
void XoaNut(TREE &t, intx)
{
if(t!=NULL)
{
if(x>t->key) XoaNut(t->pRight,x);
else
if(x<t->key) XoaNut(t->pLeft,x);
else //x==t->key
{
TNODE *p=t;//truoc khi t di chuyen thi luu t vao p
if(t->pLeft==NULL) t=t->pRight;//TH2 (bao gom TH1)
else
if(t->pRight==NULL) t=t->pLeft;//TH2 (bao gom TH1)
else //TH3, tim nut the mang la nut trai nhat cua cay con ben phai
{
TNODE *truocQ=t;
TNODE *q=t->pRight; //q la cay con ben phai
//Doan code nay tuong duong ham SearchStandFor(p,q)
while(q->pLeft!=NULL)
{
truocQ=q;
q=q->pLeft;
}
if(truocQ!=t) truocQ->pLeft=q->pRight;
else t->pRight=q->pRight;
t->key=q->key; // chep noi dung nut the mang vao nut t
p=q;
}
delete p;
}
}
}
void main()
{
int x;
TREE t;
t=NULL;
NhapCay(t);
DuyetNLR(t);
cout<<"\nSo luong nut la': "<<DemNutLa(t);
cout<<"\nSo luong nut chi co 1 cay con ben phai: "<<DemNutMotConPhai(t);
cout<<"\nDo cao cua cay: "<<DoCaoCay(t)-1;
cout<<"\nNhap gia tri key cua nut muon xoa: ";
cin>>x;
XoaNut(t,x);
cout<<"Duyet cay sau khi xoa:";
DuyetNLR(t);
cout<<"\n";
HuyCay(t);
}