CTDL-Tree-root
//---------------Chen nut gia tri k vao cay root------------------
int InsertTree(tree &root,int k)
{
if (root!=NULL)
{ //neu can ca so trung nhau thi bo dong ngay duoi
if (root->info==k) return 0;
if (root->info>k) return InsertTree(root->left,k);
else return InsertTree(root->right,k);
}
else
{ root=(tree)malloc(sizeof(node));
if (root==NULL) return -1;
root->info=k;
root->left=root->right=NULL;
return 1;
}
}
//---------------Tao cay root---------------
void CreateTree(tree &root)
{ root=NULL;
int k;
cout<<"
In put n=";
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>k;
InsertTree(root,k);
}
H=Height(root);
T1=root;
}
//---------------Cac ham duyet cay---------------
void LNR(tree root)
{
if (root!=NULL)
{
LNR(root->left);
cout<<root->info<<" ";
LNR(root->right);
}
}
void NLR(tree root)
{
if (root!=NULL)
{
cout<<root->info<<" ";
NLR(root->left);
NLR(root->right);
}
}
void LRN(tree root)
{
if (root!=NULL)
{
LRN(root->left);
LRN(root->right);
cout<<root->info<<" ";
}
}
//---------------Kiem tra xem k co trong cay root khong ?---------------
int SearchTree_recursive(tree root,int k)
{
if (root==NULL) return 0;
else
if (root->info==k) return 1;
if (k>root->info) return SearchTree_recursive(root->right,k);
else return SearchTree_recursive(root->left,k);
}
node* SearchTree1(tree root,int k)
{
if (root==NULL) return NULL;
else
if (root->info==k) return root;
if (k>root->info) return SearchTree1(root->right,k);
else return SearchTree1(root->left,k);
}
//---------------Chieu cao cua cay---------------
int Height(tree root)
{ if (root==NULL) return 0;
else
{
long HL=Height(root->left);
long HR=Height(root->right);
return 1+((HL<HR) ? HR:HL);
}
}
//---------------Xoa nut co gia tri k trong cay root--------
int DelTree(tree &root,int k)
{
if (root==NULL) return 0;
if (root->info>k) return DelTree(root->left,k);
if (root->info<k) return DelTree(root->right,k);
else
{
node *p=root;
if (root->right==NULL)
root=root->left;
else
if (root->left==NULL)
root=root->right;
else
{
node *q=root->right;
SearchStandfor(p,q);
}
delete(p);
}
}
void SearchStandfor(tree &p,tree &q)
{
if (q->left) SearchStandfor(p,q->left);
else
{ p->info=q->info;
p=q;
q=q->right;
}
}
//---------------Do lech cua cay root---------------
int Declination(tree root)
{ return abs(Height(root->left) - Height(root->right));
}
//----------Tinh tong cac nut cua cay----------
int Sumtree(tree root)
{
if (root==NULL) return 0;
return root->info+Sumtree(root->left)+Sumtree(root->right);
}
//-----------------Tim so lon nhat cua cay-----------
int Findmax(tree root)
{
int max=root->info;
while (root->right!=NULL)
{
root=root->right;
max=root->info;
}
return max;
}
//------------Dem so nut trong cay----------------
int Countnode(tree root)
{
if (root==NULL) return 0;
return Countnode(root->left)+Countnode(root->right)+1;
}
//-------------Dem so nut la trong cay-------------
int CountLeaf(tree root)
{
if (root==NULL) return 0;
if ((root->left==NULL) && (root->right==NULL)) return 1;
else return CountLeaf(root->left)+CountLeaf(root->right);
}
//---------------So nut co dung 2 cay con---------------
int Count2subTree(tree root)
{
if (root==NULL) return 0;
else
{
if (root->left!=NULL && root->right!=NULL)
return 1+Count2subTree(root->left)+Count2subTree(root->right);
return Count2subTree(root->left)+Count2subTree(root->right);
}
}
//---------------Tim muc cua mot nut co gia tri x----------------
int Levelnode(tree root, int x)
{
if (root!=NULL)
{
if (root->info==x) return 0;
if (root->info>x) return 1+Levelnode(root->left,x);
if (root->info<x) return 1+Levelnode(root->right,x);
}
}
//---------------In cac nut cua muc k---------------
void TraversalLevel(tree root, int k)
{
if (root!=NULL)
{
TraversalLevel(root->left,k);
if (Levelnode(T1,root->info)==k)
cout<<root->info<<" ";
TraversalLevel(root->right,k);
}
}
//---------In cac nut cua cay theo tung cac muc tu 0 den H-1--------
void TraversalLevelTree(tree root)
{
for (int i=0;i<H;i++)
{
TraversalLevel(root,i);
cout<<endl;
}
}
//------------In cac nut tren duong di tu goc den x----------
void PathfromROOT(tree root, int x)
{
cout<<"
In put x = ";cin>>x;
if (SearchTree_recursive(root,x))
{
while (root->info!=x)
{
cout<<root->info<<" ->";
if (root->info>x)
root=root->left;
else
if (root->info<x)
root=root->right;
}
cout<<root->info;
}
else
cout<<"Khong co duong di tu goc den "<<x;
Bạn đang đọc truyện trên: Truyen2U.Pro