1. 基本介紹

樹結構多種多樣，但是最常用的還是二叉樹。二叉樹中每個節(jié)點最多有兩個子節(jié)點，這兩個節(jié)點分別是左子節(jié)點和右子節(jié)點。注意：不要求都有兩個子節(jié)點，可以只有左子節(jié)點，也可以只有右子節(jié)點。

 

2. 二叉樹的存儲

2.1. 鏈式存儲法

每個節(jié)點至少有三個字段，其中一個存儲數(shù)據(jù)，另外兩個是指向左右子節(jié)點的指針。這種存儲方式比較常用，大部分二叉樹代碼都是通過這種結構來實現(xiàn)的。

 

2.2. 數(shù)組存儲法

我們把根節(jié)點存儲在下標 i=1 的位置，它的左子節(jié)點存儲在下標為 2 * i 的位置，右子節(jié)點存儲在下標為 2*i+1 的位置。以此類推，B 節(jié)點、C 節(jié)點的左右子節(jié)點都按照這種規(guī)律進行存儲，最終如下圖所示。

綜上，如果節(jié)點 X 存儲在數(shù)組中下標為 i 的位置，那么下標為 2*i 的位置存儲的就是它的左子節(jié)點，下標為 2*i+1 的位置存儲的就是它的右子節(jié)點。反過來，i/2 的位置存儲的就是它的父節(jié)點。一般情況下，為了方便計算，根節(jié)點會被存儲在下標為 1 的位置。

 

通過上述可以看到，針對一般樹來說，使用數(shù)組的方式存儲樹會浪費比較多的存儲空間。但是針對下文會提到的滿二叉樹或者完全二叉樹來說，數(shù)組存儲的方式是最節(jié)省內(nèi)存的一種方式。因為數(shù)組存儲時，不需要再存儲額外的左右子節(jié)點的指針。

3. 二叉樹的遍歷

二叉樹的遍歷就是將二叉樹中的所有節(jié)點遍歷打印出來。經(jīng)典的方法有三種，前序遍歷、中序遍歷和后序遍歷，還可以按層遍歷（個人理解的按層遍歷其實就是按照圖的廣度優(yōu)先遍歷方法來進行遍歷）。

前、中、后是根據(jù)節(jié)點被打印的先后來進行區(qū)分的：前序就是先打印節(jié)點本身，之后再打印它的左子樹，最后打印它的右子樹；中序就是先打印節(jié)點的左子樹，再打印節(jié)點本身，最后打印右子樹，即把節(jié)點放中間的位置輸出；后序就是先打印節(jié)點的左子樹，再打印節(jié)點的右子樹，最后打印節(jié)點本身。如下圖所示

 

按層遍歷類似于圖的廣度優(yōu)先遍歷，先打印第一層的節(jié)點，之后再依次打印第二層的節(jié)點，以此類推。

 

3.1. 代碼實現(xiàn)

實際上，二叉樹的前、中、后序遍歷是一個遞歸的過程。比如，前序遍歷，其實就是先打印根節(jié)點，然后遞歸遍歷左子樹，最后遞歸遍歷右子樹。遞歸遍歷左右子樹其實就跟遍歷根節(jié)點的方法一樣。下面先寫出這三者遍歷的遞推公式：

前序遍歷的遞推公式：
preOrder(r) = print r ---> preOrder(r->left) ---> preOrder(r->right)

中序遍歷的遞推公式：
inOrder(r) = inOrder(r--->left) ---> print r ---> inOrder(r->right)

后序遍歷的遞推公式：
postOrder(r) = postOrder(r->left) ---> postOrder(r->right) --->print r

之后將遞推公式轉化為代碼如下所示：

/**
* 前序遍歷
*/
public void preOrder(Node tree) {
   if (tree == null) {
       return;
   }

   System.out.print(tree.data + "  ");

   preOrder(tree.left);

   preOrder(tree.right);
}

/**
* 中序遍歷
*/
public void inOrder(Node tree) {
   if (tree == null) {
       return;
   }

   inOrder(tree.left);

   System.out.print(tree.data + "  ");

   inOrder(tree.right);
}

/**
* 后序遍歷
*/
public void postOrder(Node tree) {
   if (tree == null) {
       return;
   }

   postOrder(tree.left);

   postOrder(tree.right);

   System.out.print(tree.data + "  ");
}

★  

遞歸代碼的關鍵，在于寫出遞推公式。而遞推公式的關鍵在于，A 問題可以被拆解成 B、C 兩個問題。假設要解決 A 問題，那么假設 B、C 問題已經(jīng)解決了。那么在 B、C 已經(jīng)解決的提前下，看如何利用 B、C 來解決 A 。千萬不要模擬計算機一層一層想下去，否則你就會發(fā)現(xiàn)你自己都不知道在哪了。

”  

下面是按層遍歷的代碼，按層遍歷需要用到隊列的入隊和出隊等操作。先將根節(jié)點放入到隊列中，然后循環(huán)從隊列中取節(jié)點（出隊），再將該節(jié)點的左右子節(jié)點入隊。出隊的順序就是層次遍歷的結果。

/**
* 層次遍歷
*/
public void BFSOrder(Node tree) {
   if (tree == null) {
       return;
   }

   Queue queue = new LinkedList<>();
   Node temp = null;
   queue.offer(tree);
   while (!queue.isEmpty()) {
       temp = queue.poll();
       System.out.print(temp.data + "  ");
       if (temp.left != null) {
           queue.offer(temp.left);
       }

       if (temp.right != null) {
           queue.offer(temp.right);
       }
   }
}

★  

完整的代碼可查看 github 倉庫 https://github.com/DawnGuoDev/algos ，這個倉庫將主要包含常用數(shù)據(jù)結構及其基本操作的手寫實現(xiàn)（Java），也會包含常用算法思想經(jīng)典例題的實現(xiàn)（Java）。在程序鍋找到工作之前，這個倉庫將會保持更新狀態(tài)，在此之間學到的關于數(shù)據(jù)結構和算法的知識或者實現(xiàn)也都會往里面 commit，所以趕緊來 star 哦。

”  

3.2. 時間復雜度

遍歷過程中的次數(shù)就是訪問所有節(jié)點的所需的次數(shù)，而每個節(jié)點最多被訪問兩次，因此遍歷的時間復雜度是跟節(jié)點的個數(shù) n 成正比的，即遍歷的時間復雜度是 O(n)。

4. 特殊的二叉樹

4.1. 滿二叉樹

滿二叉樹是一種特殊的二叉樹，而且還是完全二叉樹的一種特殊情況。如上圖編號 2 的那棵樹所示，葉子節(jié)點全在底層，除了葉子節(jié)點之外，每個節(jié)點都有左右兩個子節(jié)點。

4.2. 完全二叉樹

完全二叉樹也是一種特殊的二叉樹。如上圖編號 3 的那棵樹所示，葉子節(jié)點都在最底下兩層，最后一層的葉子節(jié)點都靠左排列，并且除了最后一層，其他層的節(jié)點個數(shù)都達到最大。

 

完全二叉樹的特征使得它可以使用數(shù)組就可以很好地存儲數(shù)據(jù)。完全二叉樹要求最后一層的葉子節(jié)點靠左排列也是因為如此。

4.2.1. 完全二叉樹的存儲

• 鏈式存儲

  就是上面提到的那種方式。

• 數(shù)組存儲

  完全二叉樹使用數(shù)組存儲時，如下圖所示。我們發(fā)現(xiàn)使用數(shù)組來存儲完全二叉樹是一種很節(jié)省內(nèi)存的方式。這也是完全二叉樹被作為一種特殊樹的原因，也是完全二叉樹要求最后一層的子節(jié)點必須都靠左的原因。

  在講解堆或者堆排序的時候，堆其實也是一種完全二叉樹，最常用的存儲方式就是數(shù)組。