原文鏈接:http://blog.csdn.net/qq_22329521/article/details/52948072
二叉樹的遍歷常見方式
enter image description here
- 前序遍歷,先訪問跟節(jié)點(diǎn),在訪問子結(jié)點(diǎn),最后訪問右子結(jié)點(diǎn)順序是abdefgc
- 中序遍歷,先訪問左子結(jié)點(diǎn),再訪問根結(jié)點(diǎn)宪睹,最后訪問右子結(jié)點(diǎn)debgfac
- 后序遍歷,先訪問左子結(jié)點(diǎn)蚕钦,在訪問右子結(jié)點(diǎn)亭病,最后訪問更結(jié)點(diǎn)edgfbca
- 寬度優(yōu)先遍歷,先訪問樹的第一層結(jié)點(diǎn)嘶居,再訪問樹的第二層結(jié)點(diǎn)罪帖,一致到訪問到最下面一層結(jié)點(diǎn),同一層結(jié)點(diǎn)邮屁,從左到右一次遍歷abcdfeg
重構(gòu)二叉樹
輸入二叉樹的前序遍歷和中序遍歷都不含重復(fù)數(shù)字整袁,重建該二叉樹
思路:已知前序找根結(jié)點(diǎn),然后判斷跟結(jié)點(diǎn)在中序輸出中的位置佑吝,根節(jié)點(diǎn)左邊的就是左子樹坐昙,右邊就是右子樹,遞歸查找
public static void test4() {
int[] frontOrder = {1, 2, 4, 7, 3, 5, 6, 8};
int[] inOrder = {4, 7, 2, 1, 5, 3, 8, 6};
BinaryTreeNode root = BinaryTree(frontOrder, inOrder);
printPostOrder(root);
}
public static void printPostOrder(BinaryTreeNode root) {
if (root != null) {
printPostOrder(root.getLeft());
printPostOrder(root.getRight());
System.out.println(root.getValue());
}
}
public static BinaryTreeNode BinaryTree(int[] frontOrder, int[] inOrder) {
//根據(jù)前序結(jié)點(diǎn)獲取當(dāng)前的跟結(jié)點(diǎn)
BinaryTreeNode root = new BinaryTreeNode(frontOrder[0]);
root.setLeft(null);
root.setRight(null);
int leftLength = 0;
//從中序結(jié)點(diǎn)中獲取前序結(jié)點(diǎn)這個(gè)數(shù)所在的位置芋忿,因?yàn)橹行蚪Y(jié)點(diǎn)中左側(cè)是左字?jǐn)?shù)炸客,右側(cè)是右字?jǐn)?shù)
for (int i = 0; i < inOrder.length; i++) {
if (inOrder[i] == root.getValue()) {
break;
} else {
leftLength++;
}
}
//獲取右子樹的個(gè)數(shù)
int rightLength = inOrder.length - leftLength - 1;
if (leftLength > 0) {
//再次初始化左側(cè)的左子樹
int[] leftFrontOrder = new int[leftLength];
int[] leftInorder = new int[leftLength];
for (int j = 0; j < leftLength; j++) {
//因?yàn)榈谝粋€(gè)被取走了
leftFrontOrder[j] = frontOrder[j + 1];
leftInorder[j] = inOrder[j];
}
BinaryTreeNode leftRoot = BinaryTree(leftFrontOrder, leftInorder);
root.setLeft(leftRoot);
}
//再次初始化右側(cè)的右子樹
if (rightLength > 0) {
int[] rightFrontOrder = new int[rightLength];
int[] rightInorder = new int[rightLength];
for (int k = 0; k < rightLength; k++) {
rightFrontOrder[k] = frontOrder[k + 1 + leftLength];
rightInorder[k] = inOrder[k + 1 + leftLength];
}
BinaryTreeNode rightRoot = BinaryTree(rightFrontOrder, rightInorder);
root.setRight(rightRoot);
}
return root;
}
public class BinaryTreeNode {
private int value;
private BinaryTreeNode left;
private BinaryTreeNode right;
public BinaryTreeNode(int value){
this.value = value;
}
public BinaryTreeNode(int value,BinaryTreeNode left,BinaryTreeNode right){
this.value = value;
this.left = left;
this.right = right;
}
public int getValue( ){
return this.value;
}
public void setValue(BinaryTreeNode node){
this.value = value;
}
public void setLeft(BinaryTreeNode node){
this.left = node;
}
public void setRight(BinaryTreeNode node){
this.right = node;
}
public BinaryTreeNode getLeft( ){
return this.left;
}
public BinaryTreeNode getRight( ){
return this.right;
}
}