http://www.csdn.net/ http://www.arm.com/zh/ https://www.kernel.org/ http://www.linuxpk.com/ http://www.51develop.net/ http://linux.chinaitlab.com/ http://www.embeddedlinux.org.cn http://bbs.pediy.com/
分类: C/C++
2012-12-14 16:38:47
/*creat a bittree*/
#include "stdlib.h"
#include "stdio.h"
typedef struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;
BiTNode* getnode()
{
BiTNode* p;
p = (BiTNode*)malloc(sizeof(BiTNode));
p->lchild = NULL;
p->rchild = NULL;
return p;
}
int *Create_array(int *q) //创建数组
{
int n,i;
printf("please input the number:");
scanf("%d",&n);
for(i=0;i
scanf("%d",q++);
}
*q='\0';
return q;
}
void insert(BiTNode **T,BiTNode *S) //插入
{
if(*T==NULL)*T=S;
else if((*T)->data>S->data)
insert(&(*T)->lchild,S);
else if((*T)->data<=S->data)
insert(&(*T)->rchild,S);
}
BiTNode **CreateBiTree(BiTNode **T,int *w) //创建二叉排序树
{
BiTNode *S;
*T=NULL;
while(*w!='\0')
{
S=getnode();
S->data=*w;
insert(T,S);
w++;
}
return T;
}
BiTree deleteBST(BiTree tptr)//删除
{
BiTree p,tmp,parent=NULL;
p=tptr;
int key;
printf("please input the data to delete:");
scanf("%d",&key);
while(p)
{
if(p->data==key)
break;
parent=p;
p=(key
}
if(!p) return NULL;
tmp=p;
if(!p->rchild&&!p->lchild) /*p的左右子树都为空*/
{
if(!parent) //要删根,须修改根指针
tptr=NULL;
else if(p==parent->rchild)
parent->rchild=NULL;
else
parent->lchild=NULL;
free(p);
}
else if(!p->rchild) //p的右子树为空,则重接p的左子树
{
p=p->lchild;
if(!parent) //要删根,须修改根指针
tptr=p;
else if(tmp==parent->lchild)
parent->lchild=p;
else
parent->rchild=p;
free(tmp);
}
else if(!p->lchild) //的左子树为空,则重接p的左子树
{
p=p->rchild;
if(!parent) //要删根,须修改根指针
tptr=p;
else if(tmp==parent->lchild)
parent->lchild=p;
else
parent->rchild=p;
free(tmp);
}
else if(p->rchild&&p->lchild) //p有左子树和右子树,用p的后继覆盖p然后删去后继
{ //另有方法:用p的前驱覆盖p然后删去前驱||合并p的左右子树
parent=p; //由于用覆盖法删根,则不必特殊考虑删根
p=p->rchild;
while(p->lchild)
{
parent=p;
p=p->lchild;
}
tmp->data=p->data;
if(p==parent->lchild)
parent->lchild=NULL;
else
parent->rchild=NULL;
free(p);
}
return tptr;
}
int Inorder(BiTree T)
{
if(T!=NULL)
{
Inorder(T->lchild);
printf("%d ",T->data);
Inorder(T->rchild);
}
else
return 0;
}
void main(void)
{
BiTNode **T;
int n;
int *s,*q,*w;
s=(int *)malloc(100*sizeof(int));
T=(BiTNode **)malloc(100*sizeof(BiTNode));
q=s;
while(1)
{
printf("please selcet the function :\n");
printf("0 for exit\n");
printf("1 for input the data to insert to the binary tree\n");
printf("2 for rmmod the data from the binary tree\n");
printf("3 for Inorder the binary tree\n");
printf("please select:");
scanf("%d",&n);
if(n==0)
break;
if(n==1)
{ w=s;
q=Create_array(q);
T=CreateBiTree(T,w);
if(n==2)
{
deleteBST(*T);
}
if(n==3)
{
Inorder(*T);
printf("\n");
}
}
system("pause");
}