二叉树：由中序、后序求先序

• 一、题目描述
• 二、代码
• 三、代码详解
• • 1.getPos()
  • 2.dfs函数
  • • 基本的递归思路是
    • 以下几点需要注意
    • • 一、pos-1是中序数组左子树的右端点
      • 二、左子树右端点
      • 三、几种变式
      • 四、关于post_R-cnt_R-1为什么不直接写成pos-1

现给出一棵二叉树的中序与后序排列。求出它的先序排列。

输入：

CBDAFE

CDBFEA

输出：

ABCDEF

//Preorder traversal 先序
//Inorder Traversal 中序
//Postorder Traversal 后序

#include
using namespace std;
#define N 20
char inOrder[N];//存放中序数组
char postOrder[N];//存放后序数组
int getPos(char c){
	int pos;
	for(pos = 0;inOrder[pos]!=c && pos
	int pos = getPos(postOrder[post_R]);
	cout<in_L) dfs(in_L, pos-1, post_L, post_R-cnt_R-1);
	if(pos
	cin>>inOrder;
	cin>>postOrder;
	int len = strlen(inOrder);
	dfs(0,len-1,0,len-1);
	return 0;
}

后续数组的最后一位总是根节点，以下函数

int getPos(char c);

函数用于返回根节点在中序数组中的位置

一、找到根节点，用getPos（）返回其位置，然后输出根节点

二、满足条件时（pos>in_L），在左子树中搜索

三、满足条件时(pos

void dfs(int in_L, int in_R, int post_L, int post_R)

in_L 表示中序数组左端

in_R 表示中序数组右端

post_L 表示后序数组左端

post_R 表示后序数组左端

cnt_L 左子树所含节点的个数（用画图的方法非常直观可以得到为pos-in_L）

cnt_R 右子树所含节点的个数（同上）

if(pos>in_L) dfs(in_L, pos-1, post_L, post_R-cnt_R-1);

后序数组中，左子树右端点向左移动，因此需要知道在后序数组中右端子树的长度，而右子树节点个数在中序数组和后续数组中是一样的，因此确定了cnt_R就可以确定新的左子树右端点。

第一种：

实际上，求出左子树的长度也可以。

因为下面的数学关系是成立的：

post_L - post_R = in_R - in_L = 左子树元素个数（数组长度)

所以有post_L+cnt_L-1 = post_R+cnt_R-1;

所以函数可以替换成：

if(pos>in_L) dfs(in_L, pos-1, post_L, post_L+cnt_L-1);

但这样会产生一个warning，即有一个没有使用的变量cnt_R，不影响程序运行。

第二种：

if(pos>in_L) dfs(in_L, pos-1, post_L, post_R-in_R+pos-1);
if(pos 
省略了cnt_R和cnt_L
 
四、关于post_R-cnt_R-1为什么不直接写成pos-1 
如果你认为两者相等，那么：
 
post_R-in_R+pos-1 = pos-1
post_R = in_R
 
在左子树，这是成立的，但是在右子树，这两个值不一定相等！
 
在右子树中调用函数时，如果经过右子树的左子树（这里的左子树是属于右子树这个树的子树），这样写就会出现错误
 
比如：
 
CBDAFE
 
CDBFEA
 
对CDBFEA，dfs(4,5,3,4),这里4就不等于3,而pos = 3,你如果写成pos-1,就成了dfs(4,5,3,3)
 
然后就可能死循环了（因为有两个3)