高級數據結構—二叉樹
樹是一種一對多的數據結構，之前的數組，棧這些都是一對一的數據結構。
樹是n個結點的有限集。n=0稱空樹。在任意一棵非空樹中：有且僅有一個根（root）結點；n>1時，其餘結點可分為m個互不相交的的有限集，其中每個集合又是一棵樹，稱為根的子樹。
前面三個都是樹，最後一個不是樹，因為最後一個的數據相交了。
樹結構中的術語：
以下圖為例
結點：樹上面的元素
父子關係：結點之間相連的邊
子樹：當結點大於1時，其餘的結點分為的互不相交的集合稱為子樹.
度：一個結點擁有的子樹數量稱為結點的度(A是root結點度是2，B的度是2，D的度是1)
葉子：度為0的結點（H,E,F,G）
孩子：結點的子樹的根稱為孩子結點
雙親：和孩子結點對應，一個孩子只有一個雙親(A是B的雙親)
兄弟：同一個雙親結點（B,C）
森林：由多個互不相交的樹構成深林
結點高度：結點到葉子結點的最長路徑（A的高度3，B的高度2，H的高度0）
結點深度：根結點到該結點的邊個數（B結點深度1，H結點深度3）
結點的層數：結點的深度加1
樹的高度：根結點的高度
樹的深度：樹的高度+1
樹的表示方法：
雙親表示法：由孩子來記住雙親的位置
public class TreeNode<T> { private T data; private TreeNode<T> parent; }
孩子表示法：由雙親來記住所有孩子的位置
public class TreeNode<T> { private T data; private TreeNode<T> leftChild; private TreeNode<T> rightChild; }
二叉樹：
二叉樹是由一個根結點和兩棵互不相交的，分別稱為根結點的左子樹和右子樹的二叉樹構成。二叉樹的每個最多有兩棵子樹。也就說二叉樹每個結點的度是不會超過2的。
比如上面的ABCDEFGH就是一棵二叉樹。二叉樹非常適合用於每個階段都存在兩種結果的情形的建模。比如開關，01，真假，上下，對錯，正反，選不選（前面動態規劃分析的那個圖）
特殊的二叉樹：
斜樹：所有結點都只有左子樹的叫做左斜樹，所有結點只有右子樹的叫做右斜樹
滿二叉樹：所有結點都存在左右子樹，並且所有的葉子都在同一層
完全二叉樹：每一層的葉子結點都是相鄰的沒有間隔，滿二叉樹也是一種特殊的完全二叉樹
後面的就不是完全二叉樹，因為E和G不相鄰了。完全二叉樹可以基於數組存儲。前面也有說到數組可以基於下標查詢，而且它在記憶體中是連續，CPU有會預讀相鄰的區域的。
完全二叉樹怎麼用數組存儲呢？
雙親索引為i，那麼它的左孩子就是2i，右孩子就是2i+1
比如上面這個完全二叉樹轉換成數組表示：
F是C的左孩子：C在3，F在6,剛好是2n
非完全二叉樹也用數組存儲的話，會導致很多記憶體浪費，分配了卻沒有使用。
二叉樹的遍歷：
遍歷如下這個二叉樹：
先來用程式碼來構建這棵二叉樹：
/** * 構造二叉樹 * @param dataList * @param <T> * @return */ public static <T> TreeNode<T> createBinaryTree(LinkedList<T> dataList) { TreeNode<T> node = null; if (dataList == null || dataList.isEmpty()) { return null; } T data = dataList.removeFirst(); if (data != null) { node = new TreeNode(data); node.setLeftChild((createBinaryTree(dataList))); node.setRightChild((createBinaryTree(dataList))); } return node; }
調用方式：
LinkedList<String> inputList = new LinkedList<>( Arrays.asList(new String[]{"A","B","D","H",null,null,null,"E",null,null,"C","F",null,null,"G"})); TreeNode<String> treeNode = createBinaryTree(inputList);
調用裡面傳的部分null值，是因為有些結點沒有孩子結點，比如H，根據寫的構造樹方法（createBinaryTree）的邏輯傳入合適的null值。
遍歷有關鍵點:不管哪種遍歷，按照其順序遇根輸出
前序遍歷：根 左 右
按照根左右的順序，遇根輸出，再去找左
上面這棵樹的結果應該是ABDHECFG
因為遍歷的時候 對於每個節點的操作都是一樣的，所以我們首先想到的就是使用遞歸
/** * 前序遍歷 根 左子樹 右子樹 * @param node */ public static<T> void preOrderTraversal(TreeNode<T> node) { if(node == null){ return; } //遇根先輸出，再去找左右 System.out.print(node.getData()); preOrderTraversal(node.getLeftChild()); preOrderTraversal(node.getRightChild()); }
也可以利用棧的特性來實現遞歸回溯的功能
/** * 利用棧前序遍歷二叉樹 * @param root */ public static <T> void preOrderTraversalByStack(TreeNode<T> root) { Stack<TreeNode<T>> stack = new Stack<>(); TreeNode<T> node = root; while(node != null || !stack.isEmpty()) { //節點不為空，遍歷節點，併入棧用於回溯 while(node != null) { System.out.print(node.getData()); stack.push(node); node = node.getLeftChild(); } //沒有左節點，彈出該棧頂節點（回溯），訪問右節點 if(!stack.isEmpty()) { node = stack.pop(); node = node.getRightChild(); } } }
中序遍歷：左 根 右
HDBEAFCG
/** * 二叉樹中序遍歷 左子樹 根 右子樹 * @param node 二叉樹節點 */ public static<T> void inOrderTraversal(TreeNode<T> node){ if(node == null){ return; } //先找左再輸出根,再去找右 inOrderTraversal(node.getLeftChild()); System.out.print(node.getData()); inOrderTraversal(node.getRightChild()); }
後序遍歷：左 右 根
HDEBFGCA
/** * 二叉樹後序遍歷 左子樹 右子樹 根 * @param node 二叉樹節點 */ public static<T> void postOrderTraversal(TreeNode<T> node){ if(node == null){ return; } //先找左右，最後輸出根 postOrderTraversal(node.getLeftChild()); postOrderTraversal(node.getRightChild()); System.out.print(node.getData()); }
層次遍歷：按層來遍歷
ABCDEFGH
層次遍歷的時候，利用隊列的特性，將所有的孩子依次入隊進行操作。
public static <T> void levelOrder(TreeNode<T> root) { if (root == null) { return; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); //入隊 while (!queue.isEmpty()) { TreeNode<T> node = queue.poll(); //取出 if (node != null) { System.out.print(node.getData()); queue.offer(node.getLeftChild()); //左孩子入隊 queue.offer(node.getRightChild()); //右孩子入隊 } } }
