从先序中序重建二叉树输出层序后

标题: 从先序中序重建二叉树输出层序后序
时 限: 5000 ms
内存限制: 20000 K
总时限: 3000 ms
描述: 由树的先序和中序遍历生成树的层序遍历后序遍历
给定一个树的先序和中序的遍历结果,构建一棵树,并输出这个棵树的层序遍历和后序遍历结果
注:这棵树的结点是由整数描述
输入: 树结点总数m
先序输出序列
中序输出序列
输出: 层序输出序列



后续输出序列
输入样例: 10
1 2 5 10 3 6 13 7 14 15
2 10 5 1 6 13 3 14 7 15
输出样例: 1 2 3 5 6 7 10 13 14 15
10 5 2 13 6 14 15 7 3 1
提示: 先序遍历的第一个输出是根结点
来源:
#include <stdio.h>
#include <stdlib.h>
//////////////TreeNode///////////////////////////////////////////
typedef struct _TreeNode
{
//char key;
int key;
struct _TreeNode *Lc;
struct _TreeNode *Rc;
}TreeNode;

////Queue//////////////////////////////////////////////////////////////////
//队列结点
typedef struct _QNode
{
TreeNode *treenode;
struct _QNode *next;
}QNode;

//队列
typedef struct _Queue
{
QNode *front;
QNode *rear;
}Queue;

void InitQueue(Queue &Q)
{
Q.front=NULL;
Q.rear=NULL;
}

bool isemptyQ(Queue &Q)
{
if(Q.front==NULL)
return 1;
return 0;
}
void EnQueue(Queue &Q,TreeNode *_treenode)
{
QNode *s=(QNode*)malloc(sizeof(QNode));
s->treenode=_treenode;
s->next=NULL;
if(isemptyQ(Q))
{
Q.front=s;
Q.rear=s;
return;
}
else
{
Q.rear->next=s;
Q.rear=s;
}
}

bool DeQueue(Queue &Q,TreeNode *&treenode)
{
if(isemptyQ(Q))
return false;
else
{
QNode *node=Q.front;
treenode=node->treenode;
Q.front=node->next;
if(Q.front==NULL)
{
Q.rear=NULL;
}
free(node);
}
return true;
}

void DestroyQueue(Queue &Q)
{
TreeNode *temp;
while(DeQueue(Q,temp)){}
}

int Position(int *array, int e, int len)//确定e在数组in中的位置
{
int pos=0;
while(array[pos]!=e)
{
pos++;
if(pos>len-1)
{
return -1;
}
}
return pos;
}

//i: 子树的前序序列字符串的首字符在pre[]中的下标
//j: 子树的中序序列字符串的首字符在mid[]中的下标
//len: 子树的字符串序列的长度
void PreMidCreatTree(TreeNode* &T,int *pre, int *in,int i, int j,int len,int midlength)
{
if(len<=0) return;
T=(TreeNode*)malloc(sizeof(TreeNode));

T->key=pre[i];
T->Lc=NULL;
T->Rc=NULL;
int m=Position(in,pre[i],midlength);
//printf("%d\n",m);
PreMidCreatTree(T->Lc,pre,in,i+1,j,m-j,midlength);

PreMidCreatTree(T->Rc,pre,in,i+(m-j)+1,m+1,len-1-(m-j),midlength);
}

int RePostOrder(TreeNode *T)
{
if(T)
{
RePostOrder(T->Lc);

相关文档
2从先序中序重建二叉树输出层序后
标题: 从先序中序重建二叉树输出层序后序 时限: 5000 ms 内存限制: 20000 K 总时限: 3000 ms 描述: 由树的先序和中序遍历生成树的层序遍历后序遍历给定一...
线性时间重建二叉树
线性表及二叉树的遍历方法 30页 5财富值 2从先序中序重建二叉树输出... 暂无评价 2页 2财富值 线性链表,二叉树的C语言实... 11页 免费 数据结构--线性...
快速判断二叉树遍历 后遍历
快速判断二叉树先序遍历 后序遍历_计算机软件及应用_IT/计算机_专业资料。快速...先序遍历的方法 比如知道先序遍历是 ABDCEF,中序遍历是 DBAECF,那么可以从先序...
chapter 6 树和二叉树
chapter 6 树和二叉树_语文_小学教育_教育专区。...此外,还有一种层序遍历(Levelorder Traversal)。层序...(即从根结点开始,从上 到下,同一层中从先到右)...
第5章 树和二叉树
性质5:如果对一棵有n个结点的完全二叉树的结点按 层序(从1开始)编号,则对...右侧的为根结点的右子树; F E ③ 再把左子树当成 一棵树,再从先序中找其...
数据结构 树的变成习题
从先序中序重建二叉树输出层序后序 时限: 5000 ms 内存限制: 20000 K 总时限: 3000 ms 由树的先序和中序遍历生成树的层序遍历后序遍历 给定一个树的先序和...
二叉树
{ ? if ( BT ) ? { ? printf( “输出格式串...} 中根遍历中根遍历( 中根遍历(中序遍历)的定义...肯定是二叉树的根结点,所以从先根遍历的结点序列中...
chap3-1 树
层序编号,则对任一结点i(1?i?n),有: (1) 如果i=1,则结点i是二叉树的...右侧的为根结点的右子树; F ③ 再把左子树当成 一棵树,再从先序中找其 E...
chap3-1-树
层序编号,则对任一结点i(1?i?n),有: (1) 如果i=1,则结点i是二叉树的...右侧的为根结点的右子树; F ③ 再把左子树当成 一棵树,再从先序中找其 E...
如果对一棵有n个结点的完全二叉树的 结点按层序...从先,中序遍历 过程中可以看出每个结点都只需进一次...输出:B ^ 0 E 0 ^ JD *zxxsh(JD *bt) { ...
相关主题
热门文档