如何建立二叉樹

By Long Luo

之前的如何根據陣列或者字串建立連結串列？詳述了Leetcode中連結串列相關演算法題的測試方法。在Leetcode中關於樹的演算法題中，很多樹的題目，測試用例都是一個數組，比如102。 二叉樹的層序遍歷中所示：

給定二叉樹： ［3，9，20，null，null，15，7］ 3 / \ 9 20 / \ 15 7

那麼問題來了，如何根據陣列構造一顆樹呢？ 為了加快刷題，我們需要一個工具來實現構造樹和列印樹結構這2個問題。

樹

樹是一種抽象資料型別（ADT）或是實現這種抽象資料型別的資料結構，用來模擬具有樹狀結構性質的資料集合。它是由 n（n>0）個有限節點組成一個具有層次關係的集合。

樹結構

如上圖所示，把它叫做「樹」是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

樹具有以下的特點：

每個節點都只有有限個子節點或無子節點；

沒有父節點的節點稱為根節點；

每一個非根節點有且只有一個父節點；

除了根節點外，每個子節點可以分為多個不相交的子樹；

樹裡面沒有環路。

當我們完成一棵樹的構建之後，雖然我們已經有樹的前序、中序和後序遍歷這種可以遍歷樹，但是如果我們如上圖一樣展示這棵樹的結構，如何才能直觀地打印出來呢？

如何列印一棵樹？

這裡我們借用Leetcode中二叉樹的資料結構定義：

/** * Definition for a binary tree node。 */public class TreeNode { public int val； public TreeNode left； public TreeNode right； public TreeNode（int x） { this。val = x； } public TreeNode（int val， TreeNode left， TreeNode right） { this。val = val； this。left = left； this。right = right； }}

思路

樹的展示方式有2種，

水平展示和豎直展示

。

豎直展示比較直觀，水平展示更適合用於節點元素大小長短不一致的情況，Linux下展示檔案結構就是水平展示。

水平樹

程式碼如下所示：

public static int getTreeDepth（TreeNode root） { if （root == null） { return 0； } return 1 + Math。max（getTreeDepth（root。left）， getTreeDepth（root。right））； } private static String traversePreOrder（TreeNode root） { if （root == null） { return “”； } StringBuilder sb = new StringBuilder（）； sb。append（root。val）； String pointerRight = “└──”； String pointerLeft； if （root。right ！= null） { pointerLeft = “├──”； } else { pointerLeft = “└──”； } traverseNodes（sb， “”， pointerLeft， root。left， root。right ！= null）； traverseNodes（sb， “”， pointerRight， root。right， false）； return sb。toString（）； } private static void traverseNodes（StringBuilder sb， String padding， String pointer， TreeNode node， boolean hasRightSibling） { if （node == null） { return； } sb。append（“\n”）； sb。append（padding）； sb。append（pointer）； sb。append（node。val）； StringBuilder paddingBuilder = new StringBuilder（padding）； if （hasRightSibling） { paddingBuilder。append（“│ ”）； } else { paddingBuilder。append（“ ”）； } String paddingForBoth = paddingBuilder。toString（）； String pointerRight = “└──”； String pointerLeft = （node。right ！= null） ？ “├──” ： “└──”； traverseNodes（sb， paddingForBoth， pointerLeft， node。left， node。right ！= null）； traverseNodes（sb， paddingForBoth， pointerRight， node。right， false）； } public static void printTreeHorizontal（TreeNode root） { System。out。print（traversePreOrder（root））； }

垂直樹

程式碼如下所示：

public static void printTree（TreeNode root） { int maxLevel = getTreeDepth（root）； printNodeInternal（Collections。singletonList（root）， 1， maxLevel）； } private static void printNodeInternal（List nodes， int level， int maxLevel） { if （nodes == null || nodes。isEmpty（） || isAllElementsNull（nodes）） { return； } int floor = maxLevel - level； int endgeLines = （int） Math。pow（2， （Math。max（floor - 1， 0）））； int firstSpaces = （int） Math。pow（2， （floor）） - 1； int betweenSpaces = （int） Math。pow（2， （floor + 1）） - 1； printWhitespaces（firstSpaces）； List newNodes = new ArrayList（）； for （TreeNode node ： nodes） { if （node ！= null） { System。out。print（node。val）； newNodes。add（node。left）； newNodes。add（node。right）； } else { newNodes。add（null）； newNodes。add（null）； System。out。print（“ ”）； } printWhitespaces（betweenSpaces）； } System。out。println（“”）； for （int i = 1； i <= endgeLines； i++） { for （int j = 0； j < nodes。size（）； j++） { printWhitespaces（firstSpaces - i）； if （nodes。get（j） == null） { printWhitespaces（endgeLines + endgeLines + i + 1）； continue； } if （nodes。get（j）。left ！= null） { System。out。print（“/”）； } else { printWhitespaces（1）； } printWhitespaces（i + i - 1）； if （nodes。get（j）。right ！= null） { System。out。print（“\\”）； } else { printWhitespaces（1）； } printWhitespaces（endgeLines + endgeLines - i）； } System。out。println（“”）； } printNodeInternal（newNodes， level + 1， maxLevel）； } private static void printWhitespaces（int count） { for （int i = 0； i < count； i++） { System。out。print（“ ”）； } } private static boolean isAllElementsNull（List list） { for （Object object ： list） { if （object ！= null） { return false； } } return true； }

從陣列構建一棵二叉樹

程式碼如下所示：

public static TreeNode constructTree（Integer［］ array） { if （array == null || array。length == 0 || array［0］ == null） { return null； } int index = 0； int length = array。length； TreeNode root = new TreeNode（array［0］）； Deque nodeQueue = new LinkedList<>（）； nodeQueue。offer（root）； TreeNode currNode； while （index < length） { index++； if （index >= length） { return root； } currNode = nodeQueue。poll（）； Integer leftChild = array［index］； if （leftChild ！= null） { currNode。left = new TreeNode（leftChild）； nodeQueue。offer（currNode。left）； } index++； if （index >= length） { return root； } Integer rightChild = array［index］； if （rightChild ！= null） { currNode。right = new TreeNode（rightChild）； nodeQueue。offer（currNode。right）； } } return root； }

測試

下面就來測試下程式碼吧：

public static void main（String［］ args） { Integer［］ tstData1 = {1， null， 2， 2， 32， 31， 3， 23， 1， 23， 123， 12， 3， 12， 31， 23， 2}； TreeNode tstNode1 = constructTree（tstData1）； System。out。println（“\nTree：”）； printTree（tstNode1）； System。out。println（“\nHorizontal Tree：”）； printTreeHorizontal（tstNode1）； System。out。println（“\nPreOrder：”）； preOrderPrint（tstNode1）； Integer［］ tstData2 = {1， 2， 3， null， 4， 5， 6， 7， null}； TreeNode tstNode2 = constructTree（tstData2）； System。out。println（“\nTree：”）； printTree（tstNode2）； System。out。println（“\nHorizontal Tree：”）； printTreeHorizontal（tstNode2）； System。out。println（“\nPreOrder：”）； preOrderPrint（tstNode2）； System。out。println（“\nInOrder：”）； inOrderPrint（tstNode2）； System。out。println（“\nPostOrder：”）； postOrderPrint（tstNode2）； }

輸出如下所示：

Tree： 1 \ \ \ \ \ \ \ \ 2 / \ / \ / \ / \ 2 32 / \ / \ / \ / \ 31 3 23 1 / \ / \ / \ / \ 23 123 12 3 12 31 23 2 Horizontal Tree：1└──2 ├──2 │ ├──31 │ │ ├──23 │ │ └──123 │ └──3 │ ├──12 │ └──3 └──32 ├──23 │ ├──12 │ └──31 └──1 ├──23 └──2PreOrder：1，2，2，31，23，123，3，12，3，32，23，12，31，1，23，2，Tree： 1 / \ / \ / \ / \ 2 3 \ / \ \ / \ 4 5 6 / 7 Horizontal Tree：1├──2│ └──4│ └──7└──3 ├──5 └──6PreOrder：1，2，4，7，3，5，6，InOrder：2，7，4，1，5，3，6，PostOrder：7，4，2，5，6，3，1，

小結

透過上述，我們最終就完成了我們的任務。