至少需要知道前,中,后序遍历中的几种,就能重建二叉树?有无现成代码?
发布网友
发布时间：2022-05-10 21:40
共3个回答
热心网友
时间：2022-04-22 17:59
实验任务:
（1） 创建二叉树，实现二叉树前序、中序、后序遍历算法。
（2）查找指定结点。
（3）设计算法统计二叉树中结点的个数、度为1的结点个数。
（4）设计算法求出二叉树的高度。
*/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define MAXSIZE 100
typedef char datatype;
typedef struct node
{
datatype data;
struct node *lchild, *rchild;
}bitree;
void CreateBitree(bitree * &t,datatype *data)
{
bitree *St[MAXSIZE],*p=NULL;
int top=-1,k,j=0;
char ch;
t=NULL;
ch=data[j];
while(ch!='\0')
{
switch(ch)
{
case '(':top++;St[top]=p;k=1;break;
case ')':top--;break;
case ',':k=2;break;
default:
p=(bitree *)malloc(sizeof(bitree));
p->data=ch;
p->lchild=p->rchild=NULL;
if(t==NULL)
t=p;
else
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=data[j];
}
}
void visite(datatype data)
{
printf("%c\t",data);
}
void preorder ( bitree *t ) //前序遍历二叉树
{
if ( t != NULL )
{
visite (t->data);
preorder ( t->lchild );
preorder ( t->rchild );
}
}
void inorder ( bitree *t )//中序遍历二叉树
{
if ( t != NULL )
{
inorder ( t->lchild );
visite (t->data);
inorder ( t->rchild );
}
}
void postorder ( bitree *t )//后序遍历二叉树
{
if ( t != NULL )
{
postorder ( t->lchild );
postorder ( t->rchild );
visite (t->data);
}
}
bitree * find( bitree *t, datatype x) //在二叉树中查找指定节点
{
bitree *p;
if(t==NULL)
return(NULL);//空树
if (t->data==x)
return(t);//查找成功
p=find(t->lchild,x); //查找左子树
if(p==NULL)
p=find(t->rchild,x); //查找右子树
return(p);
}
int onenodenum(bitree *t)//度为1的结点个数。
{
int nl,nr;
if(t==NULL)
return 0;
if(t->lchild!=NULL && t->rchild!=NULL)
return 0;
else
return 1;
nl=onenodenum(t->lchild);
nr=onenodenum(t->rchild);
return nl+nr;
}
int nodenumber(bitree *t)//统计二叉树中结点的个数
{
int nl,nr;
int leaf;
if ( t == NULL )
return 0;
if(t->lchild==NULL && t->rchild==NULL)
return 1;
nl=nodenumber(t->lchild);
nr=nodenumber(t->rchild);
leaf=nl+nr;
return (2*leaf-1+onenodenum(t));
}
int bitreeHeight(bitree *t)
{
int lchildh,rchildh;
if(t==NULL)
return 0;
else
{
lchildh=bitreeHeight(t->lchild);
rchildh=bitreeHeight(t->rchild);
return(lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}
void printlist()
{
printf("请选择一个功能!\n");
printf("◆(1): 前序遍历\n");
printf("◆(2): 中序遍历\n");
printf("◆(3): 后序遍历\n");
printf("◆(4): 查找指定结点\n");
printf("◆(5): 统计二叉树中结点的个数、度为1的结点个数\n");
printf("◆(6): 求出二叉树的高度\n");
printf("◆(7): 离开\n");
printf("You choose: ");
}
void main()
{
int function;
int b;
bitree *t;
datatype x;
datatype data[MAXSIZE];
printf("Please input the value!\n");
scanf("%s",data);
CreateBitree(t,data);
for(b=0;b>=0;b++)
{
printlist();
scanf("%d",&function);
if(function==7)
break;
else
{
switch(function)
{
case 1:
{
preorder(t);break;
}
case 2:
{
inorder(t);break;
}
case 3:
{
postorder(t);break;
}
case 4://查找指定结点
{
bitree *s;
printf("Please input the value you want to find!\n");
fflush(stdin);//清空缓存区
scanf("%c",&x);
s=find(t,x);//将查找返回的指针赋值给s
if(s!=NULL)
printf("Successfully find!\n");
else
printf("No such node!\n");
break;
}
case 5:
{
int allnode,onenode;
allnode=nodenumber(t);
onenode=onenodenum(t);
printf("结点个数为%d,度为1的结点个数为%d\n",allnode,onenode);
break;
}
case 6:
{
int height;
height=bitreeHeight(t);
printf("二叉树的高度为%d\n",height);
break;
}
default:
printf("No such function!\n");break;
};
}
printf("Press any button to proceed\n");
printf("-------------------------------------\n");
getch();
}
}
热心网友
时间：2022-04-22 19:17
追答因为前序遍历没有办法确定二叉树的结构，所以就只剩下了中后序遍历了《数据结构》里面都有写。就在二叉树那一章。那里讲得非常清楚的。我只是手头么有这本书而已，要不我还可以告诉你在多少页= =
热心网友
时间：2022-04-22 20:52
