03、数据结构与算法实战:根据中序后序遍历序列还原二叉树

Description
已知一棵二叉树的中序遍历和后序遍历,求二叉树的先序遍历序列。

Input
输入数据有多组,第一行是一个整数t (t<1000),代表有t组测试数据。每组包括两个长度小于50 的字符串,第一个字符串表示二叉树的中序遍历序列,第二个字符串表示二叉树的后序遍历序列。

Output
输出二叉树的先序遍历序列。

Sample Input
2
dbgeafc
dgebfca
lnixu
linux

Sample Output
abdegcf
xnliu

参考程序(C语言实现)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ROOM sizeof(struct TreeNode)
#define LEN 50

char Z[LEN],H[LEN];
struct TreeNode
{
   
     
	char data;
	struct TreeNode *LeftChild;
	struct TreeNode *RightChild;
};

struct TreeNode* CreateTree(int Z_start,int Z_end,int H_start,int H_end)
{
   
     
	struct TreeNode *p;
	int i,LeftLength,RightLength;
	p=(struct TreeNode*)malloc(ROOM);
	if(H_start>H_end)
	{
   
     
		p=NULL;
	}
	else
	{
   
     
		p->data=H[H_end];
		for(i=Z_start;i<=Z_end;i++)
		{
   
     
			if(Z[i]==H[H_end])
			{
   
     
				break;
			}
		}
		LeftLength=i-Z_start;
		RightLength=Z_end-i;
		p->LeftChild=CreateTree(Z_start,i-1,H_start,H_start+LeftLength-1);
		p->RightChild=CreateTree(i+1,Z_end,H_start+LeftLength,H_end-1);
	}
	return p;
}

void PreOrder(struct TreeNode *p)
{
   
     
	if(p)
	{
   
     
		printf("%c",p->data);
		PreOrder(p->LeftChild);
		PreOrder(p->RightChild);
	}
}

int main()
{
   
     
	int t;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
   
     
		struct TreeNode* root;
		gets(Z);
		gets(H);
		root=CreateTree(0,strlen(Z)-1,0,strlen(H)-1);
		PreOrder(root);
		printf("\n");
	}
	return 0;
}

分析:本题的思路是:根据后序遍历的规则可知,后序遍历的最后一个结点一定是整棵树的根结点root,因此确定根结点以后,回到中序序列中,查找此根结点root所在的位置。查找完毕再根据中序遍历的规则,该root结点左侧子序列组成了以root为根的左子树,root结点右侧子序列组成了以root为根的右子树。根据递归思路分别进一步处理左子序列和右子序列,确定每个子序列的根结点,直至子序列不存在(end<start)为止,这样二叉树就得以还原了。因而问题主要分为两步:第一步,确定序列(子序列)的根结点,对中序序列和后序序列进行划分;第二步,准确求出两组下标Z_start, Z_end进而确定中序序列的左子序列和右子序列(较容易);准确求出两组下标H_start,H_end进而确定后序序列的左子序列和右子序列(左子序列的H_start,右子序列的H_end较容易得到;左子序列的H_end和右子序列的H_start均通过左子序列的长度计算即可)。

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: