樹
在程式設計世界中，樹其實是一種非線性的資料結構，相對於線性的資料結構(連結串列、陣列)而言，樹的平均執行時間更短(往往與樹相關的排序時間複雜度都不會高)
在現實生活中，我們一般的樹長這個樣子的：
但是在我們實際程式設計的世界中，我們一般把樹“倒”過來看，從根到開始讀起。如下圖所示：
為什麼需要二叉樹這種資料結構1、陣列儲存方式的分析優點:透過下標方式訪問元素，速度快。對於有序陣列，還可使用二分查詢提 高檢索速度。缺點:如果要插入值(按一定順序)會整體移動，效率較低畫出操作示意圖:
2、連結串列儲存方式的分析
缺點:在進行檢索時，效率仍然較低，比如(檢索某個值，需要從頭節點開始遍歷)
操作示意圖:
案例: [7, 3, 10, 1, 5, 9, 12]
樹的常用術語樹的常用術語(結合示意圖理解):1) 節點2)根節點3)父節點4)子節點5)葉子節點(沒有子節點的節點)6)節 點的權(節點值)7)路徑(從root節點找到該節點的路線)8)層9)子樹10)樹的高度(最大層數)1)樹有很多種，每個節點最多隻能有兩個子節點的一種形式稱為二叉樹。
2)二叉樹的子節點分為左節點和右節點
3)示意圖
4)如果該二叉樹的所有葉子節點都在最後一層，並且結點總數= 2^n -1 , n 為層數，則我們稱為滿二叉樹。
5)如果該二叉樹的所有葉子節點都在最後一層或者倒數第二層，而且最後一層的葉子節點在左邊連續，倒數第二層的葉子節點在右邊連續，我們稱為完全二叉樹.
如何建立二叉樹靜態建立二叉樹由上面的知識瞭解到了二叉樹是由多個節點組成的，而節點與節點之間的連結就成了樹。
所以首先建立樹的過程是先建立多個節點。然後將節點與節點之間連線起來。下面是程式碼：
class TreeNode{ private int no;//資料 private TreeNode left; //左節點 private TreeNode right;//右節點 public int getNo() { return no; } public void setNo(int no) { this.no = no; } public TreeNode getLeft() { return left; } public void setLeft(TreeNode left) { this.left = left; } public TreeNode getRight() { return right; } public void setRight(TreeNode right) { this.right = right; }}下面我們就拿這個二叉樹為例來構建吧：
//根節點 TreeNode treeNode = new TreeNode(10); //左節點-->9 TreeNode treeNode2 = new TreeNode(9); //右節點-->20 TreeNode treeNode3 = new TreeNode(20); //20的左節點-->15 TreeNode treeNode4 = new TreeNode(15); //20的右節點-->35 TreeNode treeNode5 = new TreeNode(35); //根節點的左節點 treeNode.setLeft(treeNode2); //根節點的右節點 treeNode.setRight(treeNode3); //20節點的左節點 treeNode3.setLeft(treeNode4); //20節點的右節點 treeNode3.setRight(treeNode5);使用前序，中序和後序對下面的二叉樹進行遍歷.
1) 前序遍歷: 先輸出父節點，再遍歷左子樹和右子樹
2) 中序遍歷: 先遍歷左子樹，再輸出父節點，再遍歷右子樹
3) 後序遍歷: 先遍歷左子樹，再遍歷右子樹，最後輸出父節點
4) 小結: 看輸出父節點的順序，就確定是前序，中序還是後序
以上圖的二叉樹為例：
分析二叉樹的前序，中序，後序的遍歷步驟1.建立一顆二叉樹2. 前序遍歷2.1先輸出當前節點(初始的時候是root節點)2.2如果左子節點不為空，則遞迴繼續前序遍歷2.2如果右子節點不為空，則遞迴繼續前序遍歷 10->9->20->15->353.中序遍歷3.1如果當前節點的左子節點不為空，則遞迴中序遍歷，3.2輸出當前節點3.2如果當前節點的右子節點不為空，則遞迴中序遍歷 9->10->15->20->354.後序遍歷3.1如果當前節點的左子節點不為空，則遞迴後序遍歷，3.2如果當前節點的右子節點不為空，則遞迴後序遍歷3.3輸出當前節點 9->15->35->20->10 下面程式碼演示：
/** * 前序遍歷 */ public void preOrder(){ //輸出當前節點 System.out.println(this); //遞歸向左子樹前序遍歷 if(this.left!=null){ this.left.preOrder(); } //遞歸向右子樹前序遍歷 if(this.right!=null){ this.right.preOrder(); } } /** * 中序遍歷 */ public void indexOrder(){ //遞歸向左子樹前序遍歷 if(this.left!=null){ this.left.indexOrder(); } //輸出當前節點 System.out.println(this); //遞歸向右子樹前序遍歷 if(this.right!=null){ this.right.indexOrder(); } } /** * 後序遍歷 */ public void postOrder(){ //遞歸向左子樹前序遍歷 if(this.left!=null){ this.left.postOrder(); } //遞歸向右子樹前序遍歷 if(this.right!=null){ this.right.postOrder(); } //輸出當前節點 System.out.println(this); }最後結果
二叉樹-查詢指定節點
要求
1) 請編寫前序查詢，中序查詢和後序查詢的方法。2) 並分別使用三種查詢方式，查詢 value = 15 的節點3) 並分析各種查詢方式，分別比較了多少次4) 思路分析圖解使用前序，中序，後序的方式來查詢指定的結點
前序查詢思路
1.先判斷當前結點的no是否等於要查詢的
2.如果是相等，則返回當前結點
3.如果不等，則判斷當前結點的左子節點是否為空，如果不為空，則遞迴前序查詢
4.如果左遞迴前序查詢，找到結點，則返回，否繼續判斷，當前的結點的右子節點是否為空，如果不空，則繼續向右遞迴前序查詢.
中序查詢思路
1. 判斷當前結點的左子節點是否為空,如果不為空,則遞迴中序查詢
2.如果找到，則返回，如果沒有找到，就和當前結點比較，如果是則返回當前結點，否則繼續進行右遞迴的中序查詢
3.如果右遞迴中序查詢，找到就返回，否則返回null
後序查詢思路
1.判斷當前結點的左子節點是否為空，如果不為空，則遞迴後序查詢
2.如果找到，就返回，如果沒有找到，就判斷當前結點的右子節點是否為空，如果不為空，則右遞迴進行後序查詢，如果找到，就返回
3.就和當前結點進行，比如，如果是則返回，否則返回null