在前文數(shù)據(jù)結(jié)構(gòu)：二叉樹的原理及java實(shí)現(xiàn)中懊纳，我們已經(jīng)了解了二叉樹的原理及二叉樹的三種遍歷方式揉抵，假設(shè)父節(jié)點(diǎn)是N，左節(jié)點(diǎn)是L嗤疯，右節(jié)點(diǎn)是R：
- 前序遍歷 N－>L－>R
- 中序遍歷 L－>N－>R
- 后序遍歷 L－>R－>N
對于下面的二叉樹冤今，遍歷結(jié)果分別為
- 前序遍歷：ABDECF
- 中序遍歷：DBEACF
- 后序遍歷：DEBFCA
已知二叉樹的前序遍歷和中序遍歷，如何得到它的后序遍歷
其實(shí)茂缚，只要知道其中任意兩種遍歷的順序戏罢，我們就可以推斷出剩下的一種遍歷方式的順序，這里我們只是以：知道前序遍歷和中序遍歷脚囊，推斷后序遍歷作為例子龟糕，其他組合方式原理是一樣的。要完成這個任務(wù)悔耘，我們首先要利用以下幾個特性：
- 特性A讲岁，對于前序遍歷，第一個肯定是根節(jié)點(diǎn)衬以；
- 特性B缓艳，對于后序遍歷，最后一個肯定是根節(jié)點(diǎn)看峻；
- 特性C阶淘，利用前序或后序遍歷，確定根節(jié)點(diǎn)互妓，在中序遍歷中溪窒，根節(jié)點(diǎn)的兩邊就可以分出左子樹和右子樹坤塞；
- 特性D，對左子樹和右子樹分別做前面3點(diǎn)的分析和拆分霉猛，相當(dāng)于做遞歸尺锚，我們就可以重建出完整的二叉樹；
我們以一個例子做一下這個過程惜浅，假設(shè)：
- 前序遍歷的順序是: CABGHEDF
- 中序遍歷的順序是: GHBACDEF
- 我們根據(jù)特性A瘫辩，可以得知根節(jié)點(diǎn)是C，然后坛悉，根據(jù)特性C伐厌，我們知道左子樹是：GHBA，右子樹是：DEF裸影。
C
/ \
GHBA DEF
- 取出左子樹挣轨，左子樹的前序遍歷是：ABGH，中序遍歷是：GHBA轩猩，根據(jù)特性A和C卷扮，得出左子樹的父節(jié)點(diǎn)是A，并且A沒有右子樹均践。
C
/ \
A DEF
/
GBH
- 使用同樣的方法晤锹，前序是BGH，中序是GHB彤委，得出父節(jié)點(diǎn)是B鞭铆，G和H分別是左右節(jié)點(diǎn)。
C
/ \
A DEF
/
B
/ \
G H
- 回到右子樹焦影，它的前序是EDF车遂，中序是DEF，依然根據(jù)特性A和C斯辰，得出父節(jié)點(diǎn)是E舶担，左右節(jié)點(diǎn)是D和F。
C
/ \
A E
/ / \
B D F
/ \
G H
到此椒涯，我們得到了這棵完整的二叉樹柄沮，因此，它的后序遍歷就是：GHBADFEC废岂。
程序?qū)崿F(xiàn)
下面我們使用程序來實(shí)現(xiàn)根據(jù)前序遍歷和中序遍歷得到后續(xù)遍歷。
首先我們需要建立節(jié)點(diǎn)的實(shí)體類
/**
* 二叉樹的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
*/
public class TreeNode {
private String key = null;
private String data = null;
public boolean isVisted = false;
/**
* 左兒子節(jié)點(diǎn)
*/
public TreeNode leftChild = null;
/**
* 右兒子節(jié)點(diǎn)
*/
public TreeNode rightChild = null;
/**
* 默認(rèn)構(gòu)造方法
*/
public TreeNode(){}
/**
* @param key 層序編碼
* @param data 數(shù)據(jù)域
*/
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;
}
}
具體實(shí)現(xiàn)代碼
/**
* 給出前序遍歷和終須遍歷狱意，求得二叉樹及后續(xù)遍歷
* Created by sschen on 17/5/2.
*
* 前序遍歷 N－>L－>R
* 中序遍歷 L－>N－>R
* 后序遍歷 L－>R－>N
*
* 特性A湖苞，對于前序遍歷，第一個肯定是根節(jié)點(diǎn)详囤；
* 特性B财骨，對于后序遍歷镐作，最后一個肯定是根節(jié)點(diǎn)；
* 特性C隆箩，利用前序或后序遍歷该贾，確定根節(jié)點(diǎn)，在中序遍歷中捌臊，根節(jié)點(diǎn)的兩邊就可以分出左子樹和右子樹杨蛋；
* 特性D，對左子樹和右子樹分別做前面3點(diǎn)的分析和拆分理澎，相當(dāng)于做遞歸逞力，我們就可以重建出完整的二叉樹；
*/
public class BinaryTreeFind {
public static void main(String[] args) {
/**
* A
* / \
* B C
* / \ \
* D E F
* / / \ \
* G H I J
* \ /
* K L
*
* 前序遍歷： ABDGKEHLICFJ
* 中序遍歷糠爬； GKDBLHEIACFJ
* 后續(xù)遍歷： KGDLHIEBJFCA
*/
String pr = "ABDGKEHLICFJ";
String in = "GKDBLHEIACFJ";
TreeNode node = GetTree(pr, in, "root");
postOrder(node);
}
/**
* 遞歸計算節(jié)點(diǎn)列表
* @param pr 前序遍歷字符串
* @param in 中序遍歷字符串
* @param index 層級序號
* @return 節(jié)點(diǎn)
*/
private static TreeNode GetTree(String pr, String in, String index){
if (pr == "" || in == "") {//如果字符串為空直接返回空值
return null;
}
//前序遍歷的第一個節(jié)點(diǎn)必然是該段根節(jié)點(diǎn)
String firstNodeValue = pr.substring(0, 1);
TreeNode node = new TreeNode(index, firstNodeValue);
if (in.length() == 1) {//中序遍歷沒有節(jié)點(diǎn)了寇荧，直接返回自身
return node;
}
//得到跟節(jié)點(diǎn)在中序遍歷中的位置
int iLeftLength = in.indexOf(firstNodeValue);
if (iLeftLength == 0) {//已經(jīng)是中序遍歷的第一個元素，則代表沒有左兒子
node.leftChild = null;
}
else {
node.leftChild = GetTree(pr.substring(1, iLeftLength + 1), in.substring(0, iLeftLength),index + "-L");
}
if (iLeftLength == in.length() - 1) {//已經(jīng)是中序遍歷的最后一個節(jié)點(diǎn)执隧，代表沒有右兒子
node.rightChild = null;
}
else {
node.rightChild = GetTree(pr.substring(iLeftLength + 1), in.substring(iLeftLength + 1),index + "-R");
}
return node;
}
/**
* 對二叉樹進(jìn)行后續(xù)遍歷
* @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());;
}
}
執(zhí)行結(jié)果為：
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
