#include <stdio.h>
#include <conio.h>
#include <string.h>
typedef struct node
{
int data;
node* left;
node* right;
};
typedef struct node* ptree;
ptree root;
void init(node* &ptree)
{
ptree=NULL;
}
// Tạo node mới
node *createNode(node* ptree,int x)
{
node* p=new node;
p->data=x;
p->left=NULL;
p->right=NULL;
return p;
}
void taonode(node* &ptree, int n)
{
node *p=new node;
if(ptree==NULL)
{
p=createNode(ptree,n);
ptree=p;
}
else
if(ptree->data < n)
taonode(ptree->right,n) ;
else
if(ptree->data > n)
taonode(ptree->left,n) ;
}
//nhập dữ liệu cho node
void nhap(node* &ptree)
{
int n=0;
int x;
do
{
printf("Nhap nut %d: ",n);
scanf("%d",&x);
if(x != -1)
{
taonode(ptree,x);
n++;
}
}
while(x != -1);
}
// In cây dạng nằm ngan
void InCay(node* p,int k)//k la muc tuong ung voi node p
{
if(p == NULL) return;
InCay(p->right,k+1);
for(int n=0;n<k;n++)
{
printf(" ");
}
printf("%d\n",p->data);
InCay(p->left,k + 1);
}
// Xuất dạng chuỗi LRN
void LRN(node* ptree)
{
if(ptree==NULL) return;
LRN(ptree->left);
LRN(ptree->right);
printf("\t%d",ptree->data);
}
// Xuất dạng chuỗi LNR
void LNR(node* ptree)
{
if(ptree==NULL) return;
LNR(ptree->left);
printf("\t%d",ptree->data);
LNR(ptree->right);
}
// Xuất dạng chuỗi NLR
void NLR(node* ptree)
{
if(ptree==NULL) return;
printf("\t%d",ptree->data);
NLR(ptree->left);
NLR(ptree->right);
}
// Đếm số node
int DemNut(node *root)
{
if(!root)
return 0;
return 1 + DemNut(root->left) + DemNut(root->right);
}
// Đếm số nút lá
int DemNutLa(node *root)
{
if(!root)
return 0;
int dem =DemNutLa(root->left) + DemNutLa(root->right);
if(root->left == NULL && root->right == NULL)
dem++;
return dem;
}
// Đếm số nút nhánh
int DemNutNhanh(node *root)
{
return DemNut(root) - DemNutLa(root) -1;
}
// Độ cao của cây
int DoCaoCay(node* t)
{
if(t != NULL)
{
int a=DoCaoCay(t->left);
int b=DoCaoCay(t->right);
int Max=(a>b)?a:b;
return 1+Max;
}
return 0;
}
// giá trị node lớn nhất
int MAX(node* t)
{
while(t->right!=NULL)
{
t=t->right;
}
return t->data;
}
// giá trị node bé nhất
int MIN(node* t)
{
while(t->left!=NULL)
{
t=t->left;
}
return t->data;
}
// Tìm node theo giá trị node xem có tồn tại không
int searchNode(node *root,int x)
{
node *p = root;
while (p != NULL)
{
if(x == p->data) return 1;
else
if(x < p->data) p = p->left;
else p = p->right;
}
return 0;
}
void tim(node *root)
{
int x;
printf("nhap so can tim :");
scanf("%d",&x);
searchNode(root,x);
if(searchNode(root,x) == 1)
{
printf("tim thay pt");
}
else
printf("ko tim thay pt");
}
// Xóa node theo giá trị tìm thấy
void SearchStandfor(node* &p,node* &q)//lon nhat ben trai
{
if (q->right != NULL) SearchStandfor(p, q->right);// 92-97: r->l,l->r
else
{
p->data = q->data;
p = q;
q = q->left;
}
}
bool DeleteNode(node* &p, int x )
{
if (p == NULL) return false;
if (p->data > x) return DeleteNode(p->left, x);
if (p->data <x) return DeleteNode(p->right, x);
if (p->data == x)
{
node* q = p;
if (p->left == NULL)// co 1 phai
p = p->right;
else if (p->right == NULL) // co 1 trai
p = p->left;
else// co du trai phai
SearchStandfor(q,p->left);// sua lai right
return true ;
}
}
void Xoa(ptree &root)
{
int x;
printf("\nnhap so can xoa:");
scanf("%d",&x);
DeleteNode (root,x);
}
// IN node ở tầng K
void InNodeTangK(ptree t, int k)
{
if(!t)
return;
if(k==0)
{
printf("%4d",t->data);
return;
}
InNodeTangK(t->left,k-1);
InNodeTangK(t->right,k-1);
}
// Thêm một node
int InsertTree(ptree &root , int x)
{
if(root != NULL)
{
if(root->data==x) return 0;
if(root->data>x) return InsertTree(root->left,x);
else return InsertTree(root->right,x);
}
else
{
root=new node;
if(root ==NULL) return -1;
root->data=x;
root->left=root->right=NULL;
return 1;
}
}
int them(ptree &root)
{
int x;
printf(" nhap so can them :");
scanf("%d",&x);
InsertTree(root,x);
return 0;
}
void main()
{
node* ptree;
init(ptree);
nhap(ptree);
InCay(ptree,0);
printf("L R N :\n");
LRN(ptree);
printf("\nL N R :\n");
LNR(ptree);
printf("\nN L R :\n");
NLR(ptree);
printf("\nSo node : %d\n",DemNut(ptree));
printf("\nSo node la : %d\n",DemNutLa(ptree));
printf("\nSo node nhanh : %d\n",DemNutNhanh(ptree));
printf("\nDo cao cay :%d\n",DoCaoCay(ptree));
printf("Max :%d\n",MAX(ptree));
printf("Min :%d\n",MIN(ptree));
tim(ptree);
printf("\nxoa node :\n");
Xoa(ptree);
printf("L R N :\n");
LRN(ptree);
InCay(ptree,0);
int k;
printf("nhap K :");
scanf("%d",&k);
InNodeTangK(ptree,k);
them(ptree);
InCay(ptree,0);
}
