文章出處：極客時間《數據結構和算法之美》-作者：王爭。該系列文章是本人的學習筆記。

1 樹

1.1 概念

概念：樹、根、父節點、子節點、葉子節點。
幾個度：高度、深度、層。與實際生活中的這幾個概念類比。
高度：從下往上數（從葉子往根），從0開始。
深度：從上往下看（從根往葉子），從0開始。
層數：深度+1

2 二叉樹

2.1 定義

定義：每個節點最多有兩個子節點。

　滿二叉樹：除了葉子節點沒有子節點，其余每個節點都有2個子節點。
　完全二叉樹：1 葉子節點在最下面兩層；2 最后一層的葉子節點都靠左排列；3 除了最后一層，其他層的節點達到最大個數。
　二叉樹的存儲：有兩種方式。一種是鏈式存儲,一個節點存儲數據，兩個指針分別指向左右子節點。一種是順序存儲(數組存儲)。根節點在下標為1的位置。左節點存儲下標為2i=2，右節點存儲下標為2i+1=3。依次類推。下標為i的節點，左子節點存儲在下標為2i的位置，右子節點存儲在2i+1的位置。

class Node{T value;Node leftChild;Node rightChild; }

如果一棵樹是完全二叉樹，使用數組存儲的話，只有下標為0的位置是空的，其余完全利用。而且不需要額外的指針，更節約空間。這也是完全二叉樹單獨提出來的原因。

2.2 遍歷

二叉樹的遍歷有前序遍歷、中序遍歷、后續遍歷，和層次遍歷。前中后序遍歷是指訪問節點與其子節點的相對順序。
前序遍歷：訪問節點，訪問左子節點，訪問右子節點
中序遍歷：訪問左子節點，訪問節點，訪問右子節點
后續遍歷：訪問左子節點，訪問右子節點，訪問節點
　前中后序遍歷是一個遞歸過程。遞歸的重點是不是能寫出遞歸公式。寫遞歸公式的重點是能不能將要解決的問題A，分解為子問題B、C、D，假設B、C、D已經解決，如何利用B、C、D的結果來解決問題A。

前序遍歷遞推公式： preOrder(r)=print r->preOrder(r.leftChild)->preOrder(r.rightChild); 中序遍歷遞推公式 inOrder(r)=inOrder(r.leftChild)->print r->inOrder(r.rightChild); 后序遍歷遞推公式 postOrder(r)=postOrder(r.leftChild)->postOrder(r.rightChild)->print r;

2.3思考題

給定一組數據1，3，5，6，9，10。可以構造出多少種不同的二叉樹。
答案：卡特蘭數。

3 二叉查找樹

定義：二叉查找樹中任意一個節點的左子樹中的每一個節點都要求小于當前節點，右子樹的任意一個節點都要求大于當前節點。

3.1 二叉查找樹的查找

當要查找一個數的時候，從根節點開始。如果要查找的值等于根節點的值，則返回。如果要查找的值大于根節點的值，則在右子樹遞歸查找。否則，要從左子樹遞歸查找。

3.2 二叉查找樹的插入

插入操作與查找操作類似。從根節點開始。如果要插入的數據比節點數據大，并且節點的右子樹是空的，則直接插入右子節點；如果右子樹不為空，遞歸查找右子樹，尋找插入位置。
如果要插入的數據比節點數據小，并且節點的左子樹是空的，則直接插入左子節點；如果左子樹不為空，則遞歸查找左子樹，尋找插入位置。

3.3 二叉查找樹的刪除

二叉樹的刪除操作比較復雜，需要分情況討論。
　規則1：要刪除的節點是一個葉子節點，例如55。將其父節點指向該節點的引用置為空即可。
　規則2：要刪除的節點有一個子節點，例如13。將13父節點指向該節點的引用指向13的葉子節點。
　規則3：要刪除的節點有兩個子節點，例如18。在18的右子樹查找最小值19，將18節點的value值改為最小值19，刪除節點19，應用規則1或者規則2刪除節點19。

二叉樹的刪除還有一種操作方法是將要刪除的數據標記為刪除狀態，并且真正刪除。這樣做會浪費部分空間，但整體時間復雜度不會受影響，且實現簡單。

3.4其他操作

查找最大值
查找最小值
中序遍歷得到一個順序數組，時間復雜度O(n)，非常高效，所以二叉查找樹又被稱為二叉排序樹。

3.5 支持重復元素

如果要插入的元素有重復的，該怎么處理？
　一種處理方法參考散列表的鏈式存儲。樹的每個節點存儲數值的是一個鏈表，遇到值相同的元素就依次添加到鏈表中。
　一種處理方法是，大于等于當前節點的元素都插入到右子樹。當要查找的時候，遇到相等的元素不停下來，而是繼續查找，直到找到所有要查找的值值相同的元素。刪除的時候也是同樣。要刪除每一個等于要刪除值的節點。

3.6二叉查找樹的時間復雜度分析

　二叉查找樹因為形態多樣，查找時間復雜度也不相同。例如圖中第一棵樹已經退化為鏈表，時間復雜度O(n)。
　第三棵樹是一棵完全二叉樹。無論查找、插入
　刪除，時間復雜度與它的高度成正比。一棵 包含n個節點的完全二叉樹，高度是多少？
　完全二叉樹每一層節點數量是：1、2、4…$2^{k?2}$，假設有k層。最后一層節點數量在1到$2^{k?1}$之間。假設最后一層節點數量是$2^{k?1}$。那么$1+2+4+....+2^{k?1}=n$，則$k=lo{g}_2(n+1)$。假設最后一層節點數量是1，那么$1+2+4+....+2^{k?2}+1=n$，$k=lo{g}_{2}n+1$。k值的區間是$[lo{g}_2(n+1),lo{g}_{2}n+1]$。完全二叉樹的層數小于等于$lo{g}_{2}n+1$,則完全二叉樹的高度小于等于$lo{g}_{2}n$。
　所以在理想情況下完全二叉樹的時間復雜度是O(logn)。

4 平衡二叉查找樹-紅黑樹

紅黑樹目前我只了解概念，關于從二三樹到紅黑樹之后再學習。

總結

以上是生活随笔為你收集整理的数据结构五——二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。