二叉樹詳解

二叉樹

度： 結(jié)點擁有子樹的個數(shù)
葉子節(jié)點：沒有子節(jié)點的節(jié)點
樹的深度：節(jié)點的層數(shù)， 根節(jié)點默認為第一層。
有序 ：樹的左右位置不能改變。

二叉樹常被用作二叉查找樹和二叉堆

性質(zhì)１：在非空二叉樹的第i層至多有2^{i-1}個結(jié)點
性質(zhì)２：深度為k的二叉樹至多有2^k-1個結(jié)點
性質(zhì)３：對任何一棵二叉樹Ｔ,如果其中終端節(jié)點數(shù)為n0,度數(shù)為２的節(jié)點數(shù)為ｎ2，則n0 = n2 + 1（n0表示度數(shù)為0的節(jié)點總數(shù)， n2表示度數(shù)為2的節(jié)點總數(shù)）
性質(zhì)４：在完全二叉樹中，具有n個節(jié)點的完全二叉樹的深度為[log2n]+1，其中[log2n]+1是向下取整。
性質(zhì)５：若對含 n 個結(jié)點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結(jié)點：
(1) 若 i=1，則該結(jié)點是二叉樹的根，無雙親, 否則，編號為 [i/2] 的結(jié)點為其雙親結(jié)點;  
(2) 若 2i>n，則該結(jié)點無左孩子，  否則，編號為 2i 的結(jié)點為其左孩子結(jié)點；
(3) 若 2i+1>n，則該結(jié)點無右孩子結(jié)點，  否則，編號為2i+1 的結(jié)點為其右孩子結(jié)點。

滿二叉樹

除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉結(jié)點都處在最底層的二叉樹,。   
一棵深度為k，且有2^k-1個節(jié)點的二叉樹，稱為滿二叉樹

完全二叉樹

 葉節(jié)點只能出現(xiàn)在最下層和次下層，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置的二叉樹

完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，堆是一種完全二叉樹或者近似完全二叉樹，所以效率極高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能優(yōu)化，幾乎每次都要考到的二叉排序樹的效率也要借助平衡性來提高，而平衡性基于完全二叉樹。

葉子結(jié)點只可能在最大的兩層上出現(xiàn),對任意結(jié)點，若其右分支下的子孫最大層次為L，則其左分支下的子孫的最大層次必為L 或 L+1。

具有n個結(jié)點的完全二叉樹的深度為int（log2n）+1

出于簡便起見,完全二叉樹通常采用數(shù)組而不是鏈表存儲:

（1）若i為奇數(shù)且i>1，那么tree的左兄弟為tree[i-1]；
（2）若i為偶數(shù)且i<n，那么tree的右兄弟為tree[i+1]；
（3）若i>1，tree的父親節(jié)點為tree[i div 2]；
（4）若2*i<=n，那么tree的左孩子為tree[2*i]；若2*i+1<=n，那么tree的右孩子為tree[2*i+1]；
（5）若i>n div 2,那么tree[i]為葉子結(jié)點（對應(yīng)于（3））；
（6）若i<(n-1) div 2.那么tree[i]必有兩個孩子（對應(yīng)于（4））。
（7）滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。  

平衡二叉樹

• 平衡二叉搜索樹（Self-balancing binary search tree）又被稱為AVL樹（有別于AVL算法），且具有以下性質(zhì)：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹，同時，平衡二叉樹必定是二叉搜索樹，反之則不一定。
• 二叉樹的每個節(jié)點的左子樹減去右子樹定義為該節(jié)點的平衡因子。二叉平衡樹的平衡因子只能是1、0或者-1。
• 平衡二叉樹的常用實現(xiàn)方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等。
• 二叉搜索樹有一個缺點就是，樹的結(jié)構(gòu)是無法預(yù)料的，隨意性很大，它只與節(jié)點的值和插入的順序有關(guān)系，往往得到的是一個不平衡的二叉樹。在最壞的情況下，可能得到的是一個單支二叉樹，其高度和節(jié)點數(shù)相同，相當于一個單鏈表，對其正常的時間復(fù)雜度有O(lb n)變成了O(n)，從而喪失了二叉排序樹的一些應(yīng)該有的優(yōu)點。
• 其高度一般都良好地維持在O（log（n）），大大降低了操作的時間復(fù)雜度。
• 當插入一個新的節(jié)點的時候，在普通的二叉樹中不用考慮樹的平衡因子，只要將大于根節(jié)點的值插入到右子樹，小于節(jié)點的值插入到左子樹，遞歸即可。而在平衡二叉樹則不一樣，在插入節(jié)點的時候，如果插入節(jié)點之后有一個節(jié)點的平衡因子要大于2或者小于-2的時候，他需要對其進行調(diào)整，現(xiàn)在只考慮插入到節(jié)點的左子樹部分（右子樹與此相同）
• 平衡二叉樹是在構(gòu)造二叉排序樹的過程中，每當插入一個新結(jié)點時，首先檢查是否因插入新結(jié)點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈接關(guān)系，進行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。
• 采用平衡樹的優(yōu)點是：使樹的結(jié)構(gòu)較好，從而提高查找運算的速度。缺點是：是插入和刪除運算變得復(fù)雜化，從而降低了他們的運算速度。

遍歷方式

前序遍歷

規(guī)則是若二叉樹為空，則空操作返回，否則先訪問根節(jié)點，然后前序遍歷左子樹，再前序遍歷右子樹。
應(yīng)用場景：判斷兩個二叉樹是否相等，只要子樹根節(jié)點不同，那么就不等

中序遍歷

規(guī)則是若二叉樹為空，則空操作返回，否則從根節(jié)點開始（注意并不是先訪問根節(jié)點），中序遍歷根節(jié)點左子樹，然后訪問根節(jié)點，最后中序遍歷右子樹

后序遍歷

        規(guī)則是若二叉樹為空，則空操作返回，否則從左到右先葉子后節(jié)點的方式遍歷左右子樹，最后訪問根節(jié)點　　
        應(yīng)用場景：刪除二叉樹，必須先刪除左右子樹，然后才能刪除根節(jié)點

層次遍歷

        規(guī)則是若二叉樹為空，則空操作返回，否則從樹的第一層，也就是根節(jié)點開始訪問，從上到下逐層遍歷，在同一層中，按照從左到右的順序?qū)?jié)點逐個訪問

已知前序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹
已知后序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹

線索二叉樹

• n個結(jié)點的二叉鏈表中含有n+1個空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點在某種遍歷次序下的前驅(qū)和后繼結(jié)點的指針（這種附加的指針稱為"線索"），這些指針稱為線索，加上線索的二叉樹稱為線索二叉樹。根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。
• 二叉樹的遍歷本質(zhì)上是將一個復(fù)雜的非線性結(jié)構(gòu)轉(zhuǎn)換為線性結(jié)構(gòu)，使每個結(jié)點都有了唯一前驅(qū)和后繼（第一個結(jié)點無前驅(qū)，最后一個結(jié)點無后繼）
• 建立線索二叉樹，或者說對二叉樹線索化，實質(zhì)上就是遍歷一棵二叉樹。在遍歷過程中，訪問結(jié)點的操作是檢查當前的左，右指針域是否為空，將它們改為指向前驅(qū)結(jié)點或后續(xù)結(jié)點的線索。為實現(xiàn)這一過程，設(shè)指針pre始終指向剛剛訪問的結(jié)點，即若指針p指向當前結(jié)點，則pre指向它的前驅(qū)，以便設(shè)線索。
  另外，在對一顆二叉樹加線索時，必須首先申請一個頭結(jié)點，建立頭結(jié)點與二叉樹的根結(jié)點的指向關(guān)系，對二叉樹線索化后，還需建立最后一個結(jié)點與頭結(jié)點之間的線索。
• 在遍歷二叉樹的同時，使用二叉樹中空閑的內(nèi)存空間記錄某些結(jié)點的前驅(qū)和后繼元素的位置（不是全部）。這樣在算法后期需要遍歷二叉樹時，就可以利用保存的結(jié)點信息，提高了遍歷的效率。使用這種方法構(gòu)建的二叉樹，即為“線索二叉樹”
• 線索化的過程即為在遍歷的過程中修改空指針的過程。
• LTag 和 RTag 為標志域。實際上就是兩個布爾類型的變量：
  LTag 值為 0 時，表示 lchild 指針域指向的是該結(jié)點的左孩子；為 1 時，表示指向的是該結(jié)點的直接前驅(qū)結(jié)點；
  RTag 值為 0 時，表示 rchild 指針域指向的是該結(jié)點的右孩子；為 1 時，表示指向的是該結(jié)點的直接后繼結(jié)點。