當我們有一個 先序遍歷序列：1,3,7,9,5,11 中序遍歷序列：9,7,3,1,5,11 我們可以很輕鬆的用筆寫出對應的二叉樹。但是用代碼又該如何實現？ 下麵我們來簡單談談基本思想。 首先，先序遍歷的順序是根據 根-左孩子-右孩子 的順序遍歷的，那麼我們可以率先確認的是先序遍歷序列的第一個數就是 ...
當我們有一個
先序遍歷序列：1,3,7,9,5,11
中序遍歷序列：9,7,3,1,5,11
我們可以很輕鬆的用筆寫出對應的二叉樹。但是用代碼又該如何實現？
下麵我們來簡單談談基本思想。
首先，先序遍歷的順序是根據 根-左孩子-右孩子 的順序遍歷的，那麼我們可以率先確認的是先序遍歷序列的第一個數就是根節點，然後中序遍歷是根據 左孩子-根-右孩子 的順序遍歷的。我們通過先序遍歷確認了根節點，那麼我們只需要在中序遍歷中找到根節點的位置，然後就可以很好地區分出，那些屬於左子樹的節點，那些是屬於右子樹的節點了。如下圖：
我們確定數字1為根節點，然後根據中序遍歷的遍歷順序確定，中序遍歷序列中數字1的左邊全部為左子樹節點，右邊全部為右子樹。通過左子樹節點的個數，得出先序遍歷序列中從根節點往後的連續3個數是屬於左子樹的，剩下的為右子樹。這樣再在左右子樹的序列中重覆以上步驟，最終找到沒有子節點為止。
實現代碼如下：
1 package com.tree.traverse; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 6 /** 7 * @author Caijh 8 * 9 * 2017年6月2日 下午7:21:10 10 */ 11 12 public class BuildTreePreOrderInOrder { 13 14 /** 15 * 1 16 * / \ 17 * 3 5 18 * / \ 19 * 7 11 20 * / 21 * 9 22 */ 23 public static int treeNode = 0;//記錄先序遍歷節點的個數 24 private List<Node> nodeList = new ArrayList<>();//層次遍歷節點的隊列 25 public static void main(String[] args) { 26 BuildTreePreOrderInOrder build = new BuildTreePreOrderInOrder(); 27 int[] preOrder = { 1, 3, 7, 9, 5, 11}; 28 int[] inOrder = { 9, 7, 3, 1, 5, 11}; 29 30 treeNode = preOrder.length;//初始化二叉樹的節點數 31 Node root = build.buildTreePreOrderInOrder(preOrder, 0, preOrder.length - 1, inOrder, 0, preOrder.length - 1); 32 System.out.print("先序遍歷："); 33 build.preOrder(root); 34 System.out.print("\n中序遍歷："); 35 build.inOrder(root); 36 System.out.print("\n原二叉樹：\n"); 37 build.prototypeTree(root); 38 } 39 40 /** 41 * 分治法 42 * 通過先序遍歷結果和中序遍歷結果還原二叉樹 43 * @param preOrder 先序遍歷結果序列 44 * @param preOrderBegin 先序遍歷起始位置下標 45 * @param preOrderEnd 先序遍歷末尾位置下標 46 * @param inOrder 中序遍歷結果序列 47 * @param inOrderBegin 中序遍歷起始位置下標 48 * @param inOrderEnd 中序遍歷末尾位置下標 49 * @return 50 */ 51 public Node buildTreePreOrderInOrder(int[] preOrder, int preOrderBegin, int preOrderEnd, int[] inOrder, int inOrderBegin, int inOrderEnd) { 52 if (preOrderBegin > preOrderEnd || inOrderBegin > inOrderEnd) { 53 return null; 54 } 55 int rootData = preOrder[preOrderBegin];//先序遍歷的第一個字元為當前序列根節點 56 Node head = new Node(rootData); 57 int divider = findIndexInArray(inOrder, rootData, inOrderBegin, inOrderEnd);//找打中序遍歷結果集中根節點的位置 58 int offSet = divider - inOrderBegin - 1;//計算左子樹共有幾個節點，節點數減一，為數組偏移量 59 Node left = buildTreePreOrderInOrder(preOrder, preOrderBegin + 1, preOrderBegin + 1 + offSet, inOrder, inOrderBegin,inOrderBegin + offSet); 60 Node right = buildTreePreOrderInOrder(preOrder, preOrderBegin + offSet + 2, preOrderEnd, inOrder, divider + 1, inOrderEnd); 61 head.left = left; 62 head.right = right; 63 return head; 64 } 65 /** 66 * 通過先序遍歷找到的rootData根節點，在中序遍歷結果中區分出：中左子樹和右子樹 67 * @param inOrder 中序遍歷的結果數組 68 * @param rootData 根節點位置 69 * @param begin 中序遍歷結果數組起始位置下標 70 * @param end 中序遍歷結果數組末尾位置下標 71 * @return return中序遍歷結果數組中根節點的位置 72 */ 73 public int findIndexInArray(int[] inOrder, int rootData, int begin, int end) { 74 for (int i = begin; i <= end; i++) { 75 if (inOrder[i] == rootData) 76 return i; 77 } 78 return -1; 79 } 80 /** 81 * 二叉樹先序遍歷結果 82 * @param n 83 */ 84 public void preOrder(Node n) { 85 if (n != null) { 86 System.out.print(n.val + ","); 87 preOrder(n.left); 88 preOrder(n.right); 89 } 90 } 91 /** 92 * 二叉樹中序遍歷結果 93 * @param n 94 */ 95 public void inOrder(Node n) { 96 if (n != null) { 97 inOrder(n.left); 98 System.out.print(n.val + ","); 99 inOrder(n.right); 100 } 101 } 102 /** 103 * 還原後的二叉樹 104 * 二叉數層次遍歷 105 * 基本思想： 106 * 1.因為推導出來的二叉樹是保存在Node類對象的子對象裡面的，（類似於c語言的結構體）如果通過遞歸實現層次遍歷的話，不容易實現 107 * 2.這裡採用List隊列逐層保存Node對象節點的方式實現對二叉樹的層次遍歷輸出 108 * 3.如果父節點的位置為i,那麼子節點的位置為，2i 和 2i+1;依據這個規律逐層遍歷，通過保存的父節點，找到子節點。並保存，不斷向下遍歷保存。 109 * @param tree 110 */ 111 public void prototypeTree(Node tree){ 112 //用list存儲層次遍歷的節點 113 if(tree !=null){ 114 if(tree!=null) 115 nodeList.add(tree); 116 nodeList.add(tree.left); 117 nodeList.add(tree.right); 118 int count=3; 119 //從第三層開始 120 for(int i=3;count<treeNode;i++){ 121 //第i層第一個子節點的父節點的位置下標 122 int index = (int) Math.pow(2, i-1-1)-1; 123 /** 124 * 二叉樹的每一層節點數遍歷 125 * 因為第i層的最大節點數為2的i-1次方個， 126 */ 127 for(int j=1;j<=Math.pow(2, i-1);){ 128 //計算有效的節點的個數，和遍歷序列的總數做比較，作為判斷迴圈結束的標誌 129 if(nodeList.get(index).left!=null) 130 count++; 131 if(nodeList.get(index).right!=null) 132 count++; 133 nodeList.add(nodeList.get(index).left); 134 nodeList.add(nodeList.get(index).right); 135 index++; 136 if(count>=treeNode)//當所有有效節點都遍歷到了就結束遍歷 137 break; 138 j+=2;//每次存儲兩個子節點，所以每次加2 139 } 140 } 141 int flag=0,floor=1; 142 for(Node node:nodeList){ 143 if(node!=null) 144 System.out.print(node.val+" "); 145 else 146 System.out.print("# ");//#號表示空節點 147 flag++; 148 /** 149 * 逐層遍歷輸出二叉樹 150 * 151 */ 152 if(flag>=Math.pow(2, floor-1)){ 153 flag=0; 154 floor++; 155 System.out.println(); 156 } 157 } 158 } 159 } 160 /** 161 * 內部類 162 * 1.每個Node類對象為一個節點， 163 * 2.每個節點包含根節點，左子節點和右子節點 164 */ 165 class Node { 166 Node left; 167 Node right; 168 int val; 169 public Node(int val) { 170 this.val = val; 171 } 172 } 173 }
運行結果：
最後逐層輸出二叉樹的基本思想：
* 1.因為推導出來的二叉樹是保存在Node類對象的子對象裡面的，（類似於c語言的結構體）如果通過遞歸實現層次遍歷的話，不容易實現
* 2.這裡採用List隊列逐層保存Node對象節點的方式實現對二叉樹的層次遍歷輸出
* 3.如果父節點的位置為i,那麼子節點的位置為，2i 和 2i+1;依據這個規律逐層遍歷，通過保存的父節點，找到子節點。並保存，不斷向下遍歷保存。
