Code:
#include"stdio.h"
#include"stdlib.h"
#include"conio.h"
struct node{int data;node* lchild;node* rchild;};
typedef node* BST;
void themnode(int x,BST T)
{
if(T->data==x)
{
printf("%d Da co trong cay\n",x);
return;
}
else if(T->data>x)
if(T->lchild!=NULL) themnode(x,T->lchild);
else
{
node* p=(node*)malloc(sizeof(node));
p->data=x;
p->lchild=p->rchild=NULL;
T->lchild=p;
}
else
if(T->rchild!=NULL) themnode(x,T->rchild);
else
{
node* p=(node*)malloc(sizeof(node));
p->data=x;
p->lchild=p->rchild=NULL;
T->rchild=p;
}
}
BST taocay()//Ham tao cay
{
BST T;
int x;
char ch;
T=(node*)malloc(sizeof(node));
printf("Nhap vao node goc :");
scanf("%d",&x);
T->data=x;
T->rchild=T->lchild=NULL;
do
{
printf("muon dung an ESC");
ch=getch();
if(ch!=27)
{
printf("\nNhap vao 1 so :");
scanf("%d",&x);
themnode(x,T);
}
}while(ch!=27);
return T;
}
BST leftmost(BST T)//ham tra ve node cuc trai cua cay con phai
{
if(T==NULL)
{
printf("cay rong :");
return NULL;
}
else if(T->rchild==NULL) return T;
else
{
node* p=T->rchild;
while(p->lchild) p=p->lchild;
return p;
}
}
BST rightmost(BST T)//han tra ve node cuc phai cua cay con trai
{
if(T==NULL)
{
printf("cay rong :");
return NULL;
}
else if(T->lchild==NULL) return T;
else
{
node* p=T->lchild;
while(p->rchild) p=p->rchild;
return p;
}
}
void duyetcay(BST T)//ham in cay theo thu tu trai node phai
{
if(T!=NULL)
{
duyetcay(T->lchild);
printf("%d ;",T->data);
duyetcay(T->rchild);
}
else return;
}
int ktngto(int x)//ham kiem tra nguyen to
{
for(int i=2;i<x;i++)
if(x%i==0) return 0;
return (x>1);
}
void ngtomax(BST T,BST T1)//ham tao 1 cay gom cac so nguyen to trong cay T
{
if(T!=NULL)
{
ngtomax(T->lchild,T1);
if(ktngto(T->data)) themnode(T->data,T1);
ngtomax(T->rchild,T1);
}
else return ;
}
int max(BST T)//ham tra ve so lon nhat
{
node* p=T;
while(p->rchild)
p=p->rchild;
return p->data;
}
int min(BST T)//ham tra ve so nho nhat
{
node* p=T;
while(p->lchild)
p=p->lchild;
return p->data;
}
BST pre(BST x,BST T)//ham tra ve cha cua node x
{
if(x==T->data) return NULL;
BST p=T;
while(p->lchild!=x&&p->rchild!=x)
{
if(x->data>p->data) p=p->rchild;
else p=p->lchild;
}
return p;
}
BST timkiem(int x,BST T)//ham tim kiem xem x co trong cay ko
{
if(T==NULL)
return NULL;
else
{
if(x==T->data) return T;
else if(x<T->data) return timkiem(x,T->lchild);
else return timkiem(x,T->rchild);
}
}
void xoanode1(BST x,BST& T)//xoa node ko co con
{
if(x==T) T=NULL ;
else
{
if(x->data<pre(x,T)->data)
pre(x,T)->lchild=NULL;
else pre(x,T)->rchild=NULL;
free(x);
}
}
void xoanode2(BST x,BST& T)//xoa node chi co 1 con
{
if(x==T)
if(T->lchild) T=T->lchild;
else T=T->rchild;
else
if(x->data<pre(x,T)->data)
{
if(x->lchild)
pre(x,T)->lchild=x->lchild;
else
pre(x,T)->lchild=x->rchild;
free(x);
}
else
{
if(x->lchild)
pre(x,T)->rchild=x->lchild;
else
pre(x,T)->rchild=x->rchild;
free(x);
}
}
void xoanode3(BST x,BST& T)//xoa node co 2 con
{
if(x==T)
{
BST q=leftmost(T);
if(pre(q,T)==T)
{
T->data=q->data;
T->rchild=q->rchild;
}
else
{
int n=q->data;
if(q->lchild==NULL&&q->rchild==NULL)
{
xoanode1(q,T);
T->data=n;
}
else if((q->lchild&&q->rchild==NULL)||(q->rchild&&q->lchild==NULL))
{
xoanode2(q,T);
T->data=n;
}
}
}
else
{
if(x->data<T->data) xoanode3(x,T->lchild);
else xoanode3(x,T->rchild);
}
}
void xoanode(int x,BST& T)//ham xoa x ra khoi cay
{
BST q=timkiem(x,T);
if(q->lchild==NULL&&q->rchild==NULL)
xoanode1(q,T);
else if(q->lchild&&q->rchild)
xoanode3(q,T);
else
xoanode2(q,T);
}
int main()
{
int x;
BST T,T1;
T1=(node*)malloc(sizeof(node));
T1->data=0;
T1->lchild=T1->rchild=NULL;
T=taocay();
printf("\nDuyet theo thu tu TRP:");
duyetcay(T);
puts("");
printf("phan tu lon nhat la :%d\n",max(T));
printf("phan tu nho nhat la :%d\n",min(T));
printf("Nhap vao 1 so nguyen :");
do
{
scanf("%d",&x);
if(timkiem(x,T))
{
printf("%d da co trong cay\n",x);
printf("yeu cau nhap lai :");
}
}while(timkiem(x,T));
themnode(x,T);
printf("Cay sau khi them %d :",x);
duyetcay(T);
puts("");
ngtomax(T,T1);
if(max(T1)>0)
printf("so nguyen to lon nhat la :%d\n",max(T1));
else puts("trong cay ko co so ngto");
printf("nhap vao 1 so nguyen :");
do
{
scanf("%d",&x);
if(timkiem(x,T)==NULL)
{
printf("ko co %d trong cay\n",x);
printf("yeu cau nhap lai :");
}
}while(timkiem(x,T)==NULL);
xoanode(x,T);
printf("Cay sau khi xoa %d :",x);
duyetcay(T);
getch();
return 0;
}
xin hỏi về xóa cây nhị phân??
Trả lời cùng với trích dẫn
Nguyên bản được gửi bởi kaka211
