一、樹1.樹的概念
以上的資料結構稱為樹，是n（n≥0）個節點的有限集。 當n=0時，稱為空樹。有且僅有一個特定的稱為根的節點。
相關概念：
節點的度：子節點的個數
樹的度：所有節點度的最大值
葉子節點：度為0的節點，即沒有子節點的節點
非葉子節點：度不為0的節點，即存在子節點的節點
節點深度：從根節點到當前節點的唯一路徑上的節點數
節點的高度：從當前節點到最遠葉子節點的路徑上的節點數
層：根節點在第一層，根節點的子節點在第二次，依次類推
數的分類
2.二叉樹二叉樹（binary tree）：每個節點最多有2個孩子節點。注意，這裡是最多有2個，也可能只有1個，或者沒有孩子節點。
2.1 二叉樹分類2.1.1滿二叉樹一個二叉樹的所有非葉子節點都存在左右孩子，並且所有葉子節點都在同一層級上，那麼這個樹就是滿二叉樹。
2.1.2完全二叉樹對一個有n個節點的二叉樹，按層級順序編號，則所有節點的編號為從1到n。如果這個樹所有節點和同樣深度的滿二叉樹的編號為從1到n的節點位置相同，則這個二叉樹為完全二叉樹。
2.2 二叉樹儲存二叉樹的每一個節點包含3部分，儲存資料的data變數，指向左孩子的left指標，指向右孩子的right指標。
3.二叉查詢樹二叉查詢樹(binary search tree)，二叉查詢樹在二叉樹的基礎上增加了以下幾個條件： 如果左子樹不為空，則左子樹上所有節點的值均小於根節點的值；如果右子樹不為空，則右子樹上所有節點的值均大於根節點的值，簡單來說，小於根節點的數放左邊，大於根節點的數放右邊，子樹也保持一樣的規律。
4.二叉樹的遍歷4.0 使用二叉查詢樹做遍歷案例樹節點：分為資料，左節點，右節點
class TreeNode{ int data;//節點資料 TreeNode left;//左節點 TreeNode right;//右節點 public TreeNode(int data) { this.data = data; }}二叉查詢樹的新增節點功能
使用遞迴的方式進行節點資料的新增，主要思想是插入的時候首先判斷插入的節點是否為空，如果為空就直接new一個，如果不為null再將插入的資料和節點的資料比較小於節點樹就插入節點的左子節點，如果大於當前節點數就插入右子節點，依次迭代直到找到空的節點。
public class BinarySearchTree { TreeNode root;//根節點 public void insertNode(int data){ root=insert(root,data); } //遞迴插入節點 private TreeNode insert(TreeNode node,int data){ //如果被插入節點不存在，則建立一個返回 if (node==null) return new TreeNode(data); if (data<node.data){ //左節點 node.left=insert(node.left,data); } else if(data>node.data) { //右節點 node.right=insert(node.right,data); } return node; }原理
二叉樹的前序遍歷，輸出順序是根節點、左子樹、右子樹 。
步驟如下：
1、首先輸出的是根節點1
2、由於根節點1存在左孩子，輸出左孩子節點2
3、由於節點2也存在左孩子，輸出左孩子節點4
4、節點4既沒有左孩子，也沒有右孩子，那麼回到節點2，輸出節點2的右孩子節點5
5、節點5既沒有左孩子，也沒有右孩子，那麼回到節點1，輸出節點1的右孩子節點3
6、節點3沒有左孩子，但是有右孩子，因此輸出節點3的右孩子節點6
到此為止，所有的節點都遍歷輸出完畢
程式碼實現
/** * 前序遍歷:根節點->左子樹->右子樹 * @param node */public void beforeTraver(TreeNode node){ //遞迴結束條件 if (node==null) return; System.out.println(node.data); //接著遍歷左子節點 beforeTraver(node.left); //最後遍歷右子節點 beforeTraver(node.right);}原理
二叉樹的中序遍歷，輸出順序是左子樹、根節點、右子樹。
步驟如下：
1、首先訪問根節點的左孩子，如果這個左孩子還擁有左孩子，則繼續深入訪問下去，一直找到不 再有左孩子 的節點，並輸出該節點。顯然，第一個沒有左孩子的節點是節點4
2、依照中序遍歷的次序，接下來輸出節點4的父節點2
3、再輸出節點2的右孩子節點5
4、以節點2為根的左子樹已經輸出完畢，這時再輸出整個二叉樹的根節點1
5、由於節點3沒有左孩子，所以直接輸出根節點1的右孩子節點3
6、最後輸出節點3的右孩子節點6
到此為止，所有的節點都遍歷輸出完畢
程式碼演示
/** * 中序遍歷:左子樹->右子樹->根節點 * @param node */public void afterTraver(TreeNode node){ //遞迴結束條件 if (node==null) return; midTraver(node.left); midTraver(node.right); System.out.println(node.data);}原理
二叉樹的後序遍歷，輸出順序是左子樹、右子樹、根節點。
步驟如下：
1、首先訪問根節點的左孩子，如果這個左孩子還擁有左孩子，則繼續深入訪問下去，一直找到不 再有左孩子 的節點，並輸出該節點。顯然，第一個沒有左孩子的節點是節點4
2、輸出右節點5
3、輸出節點4的父節點2
4、以節點2為根的左子樹已經輸出完畢，這時再輸出整個二叉樹的右子樹
5、訪問根節點的右孩子，如果這個右孩子擁有左孩子，則繼續深入訪問下去，一直找到不再有左 孩子 的節點，如果沒有左孩子則找右孩子，並輸出該節點6
6、輸出節點6的父節點3
到此為止，所有的節點都遍歷輸出完畢
程式碼演示
/** * 後序遍歷:左子樹->右子樹->根節點 * @param node */public void afterTraver(TreeNode node){ //遞迴結束條件 if (node==null) return; midTraver(node.left); midTraver(node.right); System.out.println(node.data);}原理
就是二叉樹按照從根節點到葉子節點的層次關係，一層一層橫向遍歷各個節點。
其遍歷順序如圖，依次為1,2,3,4,5,6。二叉樹同一層次的節點之間是沒有直接關聯的，可以使用佇列來輔助實現。
實現步驟：
1.根節點1首先進入佇列
2.節點1出佇列，獲取到節點1的子節點2,3先後進入佇列
3.節點2出佇列，獲取到節點2的2個子節點，4,5，並先後進入佇列。
4.節點3出佇列，獲取到其子節點6，如佇列
5.剩下4,5，6節點，沒有子節點就一次出佇列即可
程式碼演示
public void levelTraver(TreeNode node){ //佇列 Queue<TreeNode> queue = new LinkedList<>(); queue.offer(node); while (queue.isEmpty()){ //對頭出並刪除 TreeNode n = queue.poll(); System.out.println("n.data = " + n.data); //左子節點入隊 if (n.left!=null) queue.offer(n.left); //左子節點入隊 if (n.right!=null) queue.offer(n.right); } }上邊幾種遍歷方式可以分為2類：
深度優先：前序遍歷、中序遍歷、後序遍歷
廣度優先：層序遍歷
二叉查詢樹的時間複雜度：通常情況下插入和查詢時間複雜度為:O(logn) ，每次插入和查詢都是2分法。
極端情況下二叉查詢樹退化成連結串列，時間複雜度為O(n)，所以需要平衡二叉查詢樹
應用
非線性資料：選單，組織結構、家譜等等 線性資料：二叉查詢樹 二叉查詢樹是有序的，我們只需要中序遍歷，就可以在 O(n) 的時間複雜度內，輸出有序的資料序列。 二叉查詢樹的效能非常穩定，擴容很方便(連結串列實現)。