二叉樹

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

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

10年積累的成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)經(jīng)驗(yàn)，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識你，你也不認(rèn)識我。但先網(wǎng)站制作后付款的網(wǎng)站建設(shè)流程，更有田東免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

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

滿二叉樹

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

完全二叉樹

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

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

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

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為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é)點(diǎn)為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é)點(diǎn)（對應(yīng)于（3））；
（6）若i<(n-1) div 2.那么tree[i]必有兩個(gè)孩子（對應(yīng)于（4））。
（7）滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。

平衡二叉樹

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

遍歷方式

前序遍歷

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

中序遍歷

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

后序遍歷

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

層次遍歷

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

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

線索二叉樹

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

網(wǎng)站題目：二叉樹詳解-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://aaarwkj.com/article14/dgdege.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、全網(wǎng)營銷推廣、外貿(mào)網(wǎng)站建設(shè)、電子商務(wù)、搜索引擎優(yōu)化、外貿(mào)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)