查找算法系列文（一）一文入門二叉樹
微信公眾號：小超說
這是查找算法系列文章的第一篇，助你快速入門二叉樹
什麼是樹(Tree)？
我們首先來看一些圖片：
其中，第一、二、四個都是樹，第三個不是。樹的特點很明顯吧！
其中每個元素叫做「節點」；用來連接相鄰節點之間的關係，我們稱之為「父子關係」。例如在圖一中，A節點是B節點的父節點，B節點是A節點的子結點,同時，B節點和Q節點是同一個父節點A的子節點，所以它們之間互相成為兄弟節點。我們把沒有父節點的節點稱為根節點，也就是圖一中的A節點。我們把沒有子節點的節點稱為葉子節點，比如圖一中的D、E、F、G節點。這些概念都是顯而易見，但卻是最基本的東西。
二叉樹
二叉樹，自然就是每個節點最多有兩個分支，即兩個子節點的一種樹，兩個分支分別稱為左子樹和右子樹。還是那上面那張圖舉例，圖一、圖二和圖四都是二叉樹，因為它們每個節點都最多含有兩個子節點。其中，圖一又稱為滿二叉樹，圖四又稱為完全二叉樹。而之所以出現完全二叉樹的概念，其實是基於二叉樹的物理存儲方式。
二叉樹的存儲方法
- 基於鏈表的鏈式存儲法
- 基於數組的順序存儲法
鏈式存儲法：
我們為每個節點創建一個Node對象:
class Node{
int data;
Node left,right;
}
每個節點都是一個Node對象，它包含我們所需要存儲的數據，指向左子節點的引用，直向右子節點的引用，就像鏈表一樣將整個樹串起來。如果該節點沒有左子節點，則Node.left==null或者Node.right==null.
順序存儲法：
我們把根節點儲存在下標為i=1的位置，那麼左子節點儲存在2*i=2的位置，右子節點儲存在下標為2*i+1=2的位置。依此類推，完成樹的存儲。藉助下標運算，我們可以很輕鬆的從父節點跳轉到左子節點和右子節點或者從任意一個子節點找到它的父節點。如果X的位置為i，則它的兩個子節點的下標分別為2i和2i+1,它的父節點的位置為i/2(這裡結果向下取整)。
具體如下圖所示：可以發現，只有完全二叉樹存儲的效率才最高，最省內存
二叉樹的遍歷
二叉樹的遍歷操作主要有三種
- 前序遍歷
- 中序遍歷
- 後序遍歷
前序遍歷是指，對於樹中的任意節點來說，先打印這個節點，然後再打印它的左子樹，最後打印它的右子樹。
中序遍歷是指，對於樹中的任意節點來說，先打印它的左子樹，然後再打印它本身，最後打印它的右子樹。
後序遍歷是指，對於樹中的任意節點來說，先打印它的左子樹，然後再打印它的右子樹，最後打印這個節點本身。
注意，這其中有點遞歸的味道
還是以剛才的圖為例：
- 前序遍歷：A->B->D->E->C->F
- 中序遍歷：D->B->E->A->F->C
- 後序遍歷：D->E->B->F->C->A
具體的代碼實現(寫出遞歸即可）：
public void preOrder(Node root){
if(root==null) return;
System.out.println(root.data);//打印root節點的值
preOrder(root.left);
preOrder(root.right);
}
public void inOrder(Node root){
if(root==null) return;
inOrder(root.left);
Systrm.out.println(root.data);
inOrder(root.right);
}
public void inOrder(Node root){
if(root==null) return;
inOrder(root.left)
inOrder(root.right);
Systrm.out.println(root.data);
}
二叉樹遍歷的時間複雜度是O(n),這是因為每個節點最多會被訪問兩次，（遞歸時函數進棧和出棧），所以遍歷操作的訪問次數跟節點的個數 n 成正比，也就是說二叉樹遍歷的時間複雜度是 O(n)。
展望
經過上面的介紹，我們已經大致對二叉樹有了一個基本的認識，那麼，二叉樹存在的意義是什麼呢？我們可以基於這種數據結構設計出哪些高效的算法呢？下一次我們將介紹二叉查找樹（Binary Search Tree），我們將定義一種數據結構並維護它的性質。
題外話：對於算法初學者，推薦一本十分 nice 的書籍 《算法第四版》，裏面各種配圖十分詳細。如果你需要電子版文件，後台回復算法4即可獲得下載鏈接。後台回復 算法01 送你一份 算法與數據結構思維導圖。最後，希望我們一起進步，一起成長！
