当前位置:编程学习 > C/C++ >>

求助C语言问题。

1.已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是什么?

 帮我解释下这些词是什么意思。“  后序遍历、中序遍历、前序遍历”把做这个题得技巧顺带给我说说。谢谢

答案:同时知道一棵二叉树的先序序列和中序序列,或者同时知道中序序列和后序序列,就能确定这棵二叉树的结构。构造算法相信你已经学习过,在任一本介绍数据结构的书上应该也有描述的。由于涉及到算法细节,这里就不细说了。
下面根据你例子中给出的序列来介绍确定二叉树结构的步骤:
(1)后序序列中最后一个为树的根节点,即c为二叉树的根结点;
(2)中序遍历中根节点把序列分为左右子树的中序遍历序列两个部分,在你的例子在右子树没有中序遍历序列(中序遍历序列中c右边没有序列),故可知二叉树的左子树的后序遍历序列为dabe,中序遍历序列为deba;
(3)应用(1)的方法,确定c的左子树的根结点为e,并把以e为根结点的子树的中序遍历序列划分为d(以e为根结点的左子树的中序遍历序列)和ba(以e为根结点的右子树的中序遍历序列)两个部分,后序遍历序列为dab;
(4)应用(1)的方法,可确定e的左结点为b;
(5)应用(1)的方法,可确定e的右结点为a;
(6)最后,可确定a无左结点,右结点为d。
构造的二叉树如图中所示。


那么可获得前序遍历序列为cedba

 

分析:后序遍历和中序遍历的顺序开始都是以最左叶子结点开始的,dabec和debac串的初始都是d那么d就是最左的叶子结点。通过后序遍历最终字符为c,可知道c为跟结点,同时中序遍历最终也为c,说明二叉树没有右子树。通过中序遍历de可知d是e的子结点,而后序中dabec可知e为c的左子树的根。而后序和中序中间序列都为b那么b一定为e的右结点。a为b的右结点。构造的二叉树为:

#include "malloc.h"  #include "stdio.h"  #define maxsize 80  typedef char datatype;  typedef struct
{ datatype data[maxsize]; int last ; }seqlist ,*lnode;
seqlist *init_seqlist() { seqlist *l; l=(seqlist *)malloc(sizeof(seqlist)); l->last=-1; return l; } int insert_seqlist(seqlist *l,int i,datatype x) {
int j; if(l->last+1==maxsize) { printf("full!\n"); return 0; } if(i<1||i>l->last+2) { printf("error!\n"); return 0; } for(j=l->last;j>=i-1;j--) l->data[j+1]=l->data[j]; l->data[i-1]=x; l->last++; return 1; }

int delete_seqlist(seqlist *l,int i) { int j; if(i<1 ||i>l->last+1 ) // i位置出错 { printf("error!\n"); return 0; }
for(j=i;j<=l->last;j++) // i后面的所有元素前移一个位置 l->data[j-1]=l->data[j]; l->last--; //顺序表长减1 return 1; //成功返回1 } void search(seqlist *l,datatype x) { int i=0; while(i<= l->last)
{
if(l->data[i]==x ) //判断顺序表中的元素是否与查找的元素x相等 printf("数据元素%d在顺序表的第%d个位置出现\n",x,i+1); i++; } }
void outdata(seqlist *l) { int i=0; while( i<= l->last )
{
printf("在顺序表的第%d个位置数据元素:%d\n",i+1,l->data[i]); i++; } } void main() { int i,j=1; char x[30]; seqlist *l; l=init_seqlist(); while(j!=0) { printf("----------------------------------------------------------------------------\n"); printf("请输入要执行的操作:(0)结束***(1)插入***(2)删除***(3)查找***(4)打印顺序表\n"); printf("----------------------------------------------------------------------------\n"); scanf("%d",&j); switch(j) { case 0: break;
case 1: printf("输入要插入的位置和姓名、电话号码、住址:输入形式(姓名,电话号码,住址)"); fflush(stdin); scanf("%d%s",&i,x);
if( insert_seqlist(l,i,x[30])==1) outdata(l); break;
case 2: printf("请输入要删除的位置:"); scanf("%d",&i); if( delete_seqlist(l,i))
outdata(l); break;
case 3: printf("请输入要查找的位置:"); scanf("%d",&x); search(l,x[30]); break;
case 4: outdata(l); break; } } }

前序cedba

后序就是先访问左子树 再访问右子树 最后是节点

前序是先节点 再左右子树

中序是先左子树 然后节点 最后是右子树

一个被小金毒害的人哪

上一个:计算机c语言关键字是什么
下一个:c语言的变量名

CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,