当前位置:文库下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 从先序中序重建二叉树输出层序后
免费下载此文档侵权投诉

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

标题: 从先序中序重建二叉树输出层序后序
时 限: 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);

第1页

免费下载Word文档免费下载:从先序中序重建二叉树输出层序后

(下载1-2页,共2页)

猜你喜欢

返回顶部