汉扬编程 编程大纲 已知二叉树的前序和后序遍历,怎么求中序遍历啊?

已知二叉树的前序和后序遍历,怎么求中序遍历啊?

  按照自己的思路写的,仅供参考,
int creat(BiTree &T, ElemType pre[],ElemType post[],int low_x,int high_x,int low_h,int high_h)
{//根据先序序列和后序序列建立二叉链表,先序序列和后序序列存于一维数组中,四个整型变量表示数组的范围,0号单元留空,函数返回可建立二叉树的数目
count=1;
if(low_x>high_x || low_h >high_h) {T==NULL;return count;}
if(low_x high_h])
{
T=new BiNode;
T->data=pre。
  elem[low_x];
}
if(low_x 1= low_h)
{
if(pre [low_x 1] ! = post [high_h-1])
{
顺序查找pre [low_x 1]在后序序列的位置a;
顺序查找post [high_h-1]在先序序列的位置b;
creat(T->lchild,pre,post,low_x 1,b-1,low_h,a);
creat(T->rchild,pre,post,b,high_x,a 1,high_h-1);
}
else if(pre [low_x 1] = = post [high_h-1])
{
count*=2;
请选择建立左子树或右子树,左输入0,右输入1,用L_R表示
cin>>L_R;
if(L_R= =0)
{
creat(T->lchild,pre,post,low_x 1,high_x,low_h,high_h-1);
creat(T->rchild,pre,post,1,0,1,0);
else {
creat(T->lchild,pre,post,1,0,1,0);
creat(T->rchild,pre,post,low_x 1,high_x,low_h,high_h-1);
}
}
if (low_x 1> high_x || high_h-1 lchild,pre,post,1,0,1,0);
creat(T->rchild,pre,post, 1,0,1,0);
}
}。
  

1编码完成二叉树的相关操作

  #include
#include
#define FALSE 0
#define TRUE 1
#define OK 1
#define maxsize 100
typedef int status;
typedef int elemtype;
typedef struct binode
{
elemtype data;
struct binode *lchild,*rchild;
}binode,*bitree;
status treecreated=FALSE;
int leafcount=0;
status createbitree(bitree *t);
status preordertraverse(bitree t);
int height(bitree t);
void swap(bitree *t);
void leafcounts(bitree t);
void main()
{
int choice=0;
status leave=FALSE,flag;
binode *bt;
cout>choice;
switch(choice)
{
case 1:
if(treecreated)
{
cout>ch;
if(ch==0) //输入如果是0表示是空
(*t)=NULL;
else
{
(*t)=(bitree)malloc(sizeof(binode)); //申请空间
(*t)->data=ch; //把数据传给他
createbitree(&(*t)->lchild); //左孩子重新进入创建函数
createbitree(&(*t)->rchild); //右孩子重新进入创建函数
}
return OK;
}
//递归方法实现先序遍历
status preordertraverse(bitree t)
{
if(t)
{
coutdatalchild); //然后是左结点
preordertraverse(t->rchild); //然后是右结点
return OK;
}
else
return OK;
}
int height(bitree t)
{
int hl,hr;
if(t==NULL)
return 0;
hl=height(t->lchild) 1; //最下面的左孩子加一
hr=height(t->rchild) 1; //最下面的右孩子加一
return (hl>hr?hl:hr); //比较谁大就取谁
}
void swap(bitree *t) //进行左右翻转
{
bitree p;
if(*t!=NULL)
{
p=(*t)->lchild; //p为中间变量
(*t)->lchild=(*t)->rchild;
(*t)->rchild=p;
swap(&(*t)->lchild);
swap(&(*t)->rchild);
}
}
void leafcounts(bitree t) //求叶子数
{
if(t) //如果不为空
{
if(t->lchild==NULL && t->rchild==NULL)//左右孩子都为空 表明是叶子
leafcount ;
leafcounts(t->lchild);
leafcounts(t->rchild);
}
}。
  

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/6420.html

二叉树遍历要怎么算才快?

上机实验报告建立二叉树A(B(D

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部