二叉樹詳解

二叉樹

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

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

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

滿二叉樹

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

完全二叉樹

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

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

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

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

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

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

平衡二叉樹

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

遍歷方式

前序遍歷

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

中序遍歷

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

后序遍歷

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

層次遍歷

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

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

線索二叉樹

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