二叉树的相关操作,转载http://www.programfan.com/club/showbbs.asp?id=135842
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#define OK 1
#define MAXLEN 100
typedef int ElemType;
typedef struct bnode
{
ElemType data;
struct bnode *left,*right;
}bnode,*btree;
int creat(btree &b)//创建二叉树并向树输入结点
{
void insert(btree &b,bnode *t);
int x;
bnode *s;
b=NULL;
scanf("%d",&x);
while(x!=0)
{
s=(bnode *)malloc(sizeof(bnode));
s->data=x;
s->left=NULL;
s->right=NULL;
insert(b,s);
scanf("%d",&x);
}//输入结点以0结束
return OK ;
}
void insert(btree &b,bnode *s)//向树中插入结点
{
if(b==NULL) b=s;
else if(s->data==b->data)
return;
else if(s->data<b->data)
insert(b->left,s);
else if(s->data>b->data)
insert(b->right,s);
}
void putout(btree b)//输出此二叉树结构
{
if(b!=NULL)
{
printf("%d",b->data);
if(b->left!=NULL||b->right!=NULL)
{
printf("(");//用广义表的形式输出树的结构
putout(b->left);
if(b->right!=NULL) printf(",");
putout(b->right);
printf(")");
}
}
}
void first(btree &b)//先序遍历
{
if(b!=NULL)
{
printf("%d ",b->data);
first(b->left);
first(b->right);
}
}
void middle(btree &b)//中序遍历
{
if(b!=NULL)
{
middle(b->left);
printf("%d ",b->data);
middle(b->right);
}
}
void last(btree &b)//后序遍历
{
if(b!=NULL)
{
last(b->left);
last(b->right);
printf("%d ",b->data);
}
}
void midd(btree &b)//中序的非递归算法
{
btree stack[255],p;
int top=0;
p=b;
do
{
while(p!=NULL)
{
top++; stack[top]=p;
p=p->left;
}
if(top>0)
{
p=stack[top]; top--;
printf("%d ",p->data);
p=p->right;
}
}while(p!=NULL||top!=0);
}
void leveltran(btree b)//二叉排序树的层次遍历
{
struct node
{
btree vec[MAXLEN];
int f,r;
}q;
q.f=0;
q.r=0;
if(b!=NULL) printf("%d ",b->data);
q.vec[q.r]=b;
q.r=q.r+1;
while(q.f<q.r)//模拟队列,用q.r和q.f做标志,当两者相等时即队列为空
{
b=q.vec[q.f];
q.f=q.f+1;
if(b->left!=NULL)
{
printf("%d ",b->left->data);
q.vec[q.r]=b->left;
q.r=q.r+1;
}
if(b->right!=NULL)
{
printf("%d ",b->right->data);
q.vec[q.r]=b->right;
q.r=q.r+1;
}
}
}
bnode *search(btree q,int t)//查找结点,返回指向该结点的指针
{
if(q==NULL)
{
printf("找不到你要的结点或树为空\n");
return(NULL);
}
else
{
if(q->data==t) return(q);
if(t<q->data) q=search(q->left,t);
else q=search(q->right,t);
} return q;
}
bnode *swap(btree b)//交换左右子树产生新的树t返回到主函数
{
btree t,t1,t2;
if(b==NULL)
t=NULL;
else
{
t=(bnode *)malloc(sizeof(bnode));
t->data=b->data;
t1=swap(b->left);
t2=swap(b->right);
t->left=t2;
t->right=t1;
} return(t);
}
int depth(btree &b)//求树的深度
{
int dep1,dep2;
if(b==NULL) return 0;
else
{
dep1=depth(b->left);
dep2=depth(b->right);
if(dep1>dep2) return(dep1+1);
else return(dep2+1);
}
}
int leafs(btree b)//求树的叶子结点数
{
int num1,num2;
if(b==NULL) return 0;
else
if(b->left==NULL&&b->right==NULL)
return 1;
else
{
num1=leafs(b->left);
num2=leafs(b->right);
return (num1+num2);
}
}
int deletet(btree &b)//删除结点
{
btree s,p,q;
int x;
printf("请输入你要删除的结点:\n");
scanf("%d",&x);
if((b->data==x)&&(b->left==NULL)&&(b->right==NULL))
{
b=NULL;return OK;
}//只有根结点时并删除的情况
if(b->data==x&&(b->left!=NULL)&&(b->right==NULL))
{
s=b;b=b->left;
free(s); return OK;
}//根结点只有左子树时删除根的情况
if(b->data==x&&(b->left==NULL)&&(b->right!=NULL))
{
s=b; b=b->right;
free(s); return OK;
}//根结点只有右子树时删除根的情况
p=b;
q=NULL;
while(p!=NULL&&p->data!=x)
{
if(x<p->data)
{
q=p; p=p->left;
}
else
{
q=p; p=p->right;
}
}//while,q指向要删除结点的前驱,p指向被删除的结点
if(p==NULL)
{
printf("找不到你要删除的结点\n");
return -1;
}//if
if(!p->right)//右子树为空接左子树
{
if(q->left==p)//q是p的前驱,看看p是q的左子树还是q右子树
{
s=p; q->left=p->left;
free(s);
}
else
{
s=p; q->right=p->left;
free(s);
} return OK;
}//if
if(!p->left)//左子树为空接右子树
{
if(q->left==p)//q是p的前驱,看看p是q的左子树还是q右子树
{
s=p; q->left=p->right;
free(s);
}
else
{
s=p; q->right=p->right;
free(s);
} return OK;
}//if
else//左右子树都不为空,此时不是删除p而是用s指向的结点代替
{
q=p; s=p->left;
while(s->right)
{
q=s; s=s->right;
}
p->data=s->data;
if(q!=p) q->right=s->left;
else q->left=s->left;
free(s); return OK;
}//else
}
//主函数
void main()
k{
btree b,t,n;
int k,x,dep,leaf;
while(1)
{
printf("请输入你要执行的操作:\n");
printf("0------------------------结束此次操作\n");
printf("1-----输入结点并建二叉排序树(以0结束)\n");
printf("2--------------广义表形式输出树的结构\n");
printf("3----------------------------先序遍历\n");
printf("4----------------------------中序遍历\n");
printf("5----------------------------后序遍历\n");
printf("6----------------------中序非剃归遍历\n");
printf("7----------------------------层次遍历\n");
printf("8----------------------查找你要的结点\n");
printf("9------------------------交换左右子树\n");
printf("10---------------求此二叉排序树的深度\n");
printf("11---------求此二叉排序树的叶子结点数\n");
printf("12---------------------------删除结点\n");
scanf("%d",&k);
switch(k)
{
case 0:
system("cls");
return;
case 1:
system("cls");
printf("请输入结点(以0结束输入):\n");
creat(b);
break;
case 2:
system("cls");
printf("树的结构为:\n");
putout(b);
printf("\n");
break;
case 3:
system("cls");
printf("先序遍历为:\n");
first(b);
printf("\n");
break;
case 4:
system("cls");
printf("中序遍历为:\n");
middle(b);
printf("\n");
break;
case 5:
system("cls");
printf("后序遍历为:\n");
last(b);
printf("\n");
break;
case 6:
system("cls");
printf("中序非剃归遍历为:\n");
midd(b);
printf("\n");
break;
case 7:
system("cls");
printf("层次遍历为:\n");
leveltran(b);
printf("\n");
break;
case 8:
system("cls");
printf("请输入你要查找的结点:\n");
scanf("%d",&x);
t=search(b,x);
if(t!=NULL)
printf("你要查找的结点为: %d\n",t->data);
break;
case 9:
system("cls");
printf("交换左右子树后树的结构为:\n");
n=swap(b);
putout(n);
printf("\n");
break;
case 10:
system("cls");
printf("树的深度为:\n");
dep=depth(b);
printf("%d\n",dep);
break;
case 11:
system("cls");
printf("此树的叶子结点数为:\n");
leaf=leafs(b);
printf("%d\n",leaf);
break;
case 12:
system("cls");
deletet(b);
break;
}
}
}
评论