在前文数据结构：二叉树的原理及java实现中，我们已经了解了二叉树的原理及二叉树的三种遍历方式，假设父节点是N，左节点是L，右节点是R：
- 前序遍历 N－>L－>R
- 中序遍历 L－>N－>R
- 后序遍历 L－>R－>N
对于下面的二叉树，遍历结果分别为
- 前序遍历：ABDECF
- 中序遍历：DBEACF
- 后序遍历：DEBFCA
已知二叉树的前序遍历和中序遍历，如何得到它的后序遍历
其实，只要知道其中任意两种遍历的顺序，我们就可以推断出剩下的一种遍历方式的顺序，这里我们只是以：知道前序遍历和中序遍历，推断后序遍历作为例子，其他组合方式原理是一样的。要完成这个任务，我们首先要利用以下几个特性：
- 特性A，对于前序遍历，第一个肯定是根节点；
- 特性B，对于后序遍历，最后一个肯定是根节点；
- 特性C，利用前序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左子树和右子树；
- 特性D，对左子树和右子树分别做前面3点的分析和拆分，相当于做递归，我们就可以重建出完整的二叉树；
我们以一个例子做一下这个过程，假设：
- 前序遍历的顺序是: CABGHEDF
- 中序遍历的顺序是: GHBACDEF
- 我们根据特性A，可以得知根节点是C，然后，根据特性C，我们知道左子树是：GHBA，右子树是：DEF。
C
/ \
GHBA DEF
- 取出左子树，左子树的前序遍历是：ABGH，中序遍历是：GHBA，根据特性A和C，得出左子树的父节点是A，并且A没有右子树。
C
/ \
A DEF
/
GBH
- 使用同样的方法，前序是BGH，中序是GHB，得出父节点是B，G和H分别是左右节点。
C
/ \
A DEF
/
B
/ \
G H
- 回到右子树，它的前序是EDF，中序是DEF，依然根据特性A和C，得出父节点是E，左右节点是D和F。
C
/ \
A E
/ / \
B D F
/ \
G H
到此，我们得到了这棵完整的二叉树，因此，它的后序遍历就是：GHBADFEC。
程序实现
下面我们使用程序来实现根据前序遍历和中序遍历得到后续遍历。
首先我们需要建立节点的实体类
/**
* 二叉树的节点数据结构
*/
public class TreeNode {
private String key = null;
private String data = null;
public boolean isVisted = false;
/**
* 左儿子节点
*/
public TreeNode leftChild = null;
/**
* 右儿子节点
*/
public TreeNode rightChild = null;
/**
* 默认构造方法
*/
public TreeNode(){}
/**
* @param key 层序编码
* @param data 数据域
*/
public TreeNode(String key, String data){
this.setKey(key);
this.setData(data);
this.leftChild = null;
this.rightChild = null;
}
/**
* 序号
*/
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
/**
* 值
*/
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
}
具体实现代码
/**
* 给出前序遍历和终须遍历，求得二叉树及后续遍历
* Created by sschen on 17/5/2.
*
* 前序遍历 N－>L－>R
* 中序遍历 L－>N－>R
* 后序遍历 L－>R－>N
*
* 特性A，对于前序遍历，第一个肯定是根节点；
* 特性B，对于后序遍历，最后一个肯定是根节点；
* 特性C，利用前序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左子树和右子树；
* 特性D，对左子树和右子树分别做前面3点的分析和拆分，相当于做递归，我们就可以重建出完整的二叉树；
*/
public class BinaryTreeFind {
public static void main(String[] args) {
/**
* A
* / \
* B C
* / \ \
* D E F
* / / \ \
* G H I J
* \ /
* K L
*
* 前序遍历： ABDGKEHLICFJ
* 中序遍历； GKDBLHEIACFJ
* 后续遍历： KGDLHIEBJFCA
*/
String pr = "ABDGKEHLICFJ";
String in = "GKDBLHEIACFJ";
TreeNode node = GetTree(pr, in, "root");
postOrder(node);
}
/**
* 递归计算节点列表
* @param pr 前序遍历字符串
* @param in 中序遍历字符串
* @param index 层级序号
* @return 节点
*/
private static TreeNode GetTree(String pr, String in, String index){
if (pr == "" || in == "") {//如果字符串为空直接返回空值
return null;
}
//前序遍历的第一个节点必然是该段根节点
String firstNodeValue = pr.substring(0, 1);
TreeNode node = new TreeNode(index, firstNodeValue);
if (in.length() == 1) {//中序遍历没有节点了，直接返回自身
return node;
}
//得到跟节点在中序遍历中的位置
int iLeftLength = in.indexOf(firstNodeValue);
if (iLeftLength == 0) {//已经是中序遍历的第一个元素，则代表没有左儿子
node.leftChild = null;
}
else {
node.leftChild = GetTree(pr.substring(1, iLeftLength + 1), in.substring(0, iLeftLength),index + "-L");
}
if (iLeftLength == in.length() - 1) {//已经是中序遍历的最后一个节点，代表没有右儿子
node.rightChild = null;
}
else {
node.rightChild = GetTree(pr.substring(iLeftLength + 1), in.substring(iLeftLength + 1),index + "-R");
}
return node;
}
/**
* 对二叉树进行后续遍历
* @param subTree 二叉树
*/
public static void postOrder(TreeNode subTree) {
if (subTree != null) {
postOrder(subTree.leftChild);
postOrder(subTree.rightChild);
visted(subTree);
}
}
public static void visted(TreeNode subTree){
subTree.isVisted=true;
System.out.println("key:" + subTree.getKey() + "--name:" + subTree.getData());;
}
}
执行结果为：
key:root-L-L-L-R--name:K
key:root-L-L-L--name:G
key:root-L-L--name:D
key:root-L-R-L-L--name:L
key:root-L-R-L--name:H
key:root-L-R-R--name:I
key:root-L-R--name:E
key:root-L--name:B
key:root-R-R-R--name:J
key:root-R-R--name:F
key:root-R--name:C
key:root--name:A
网友评论