15數(shù)據(jù)結(jié)構(gòu)tree_堆排序-創(chuàng)新互聯(lián)

python內(nèi)置數(shù)據(jù)結(jié)構(gòu)——tree樹

10多年的東港網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營(yíng)銷的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整東港建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)從事“東港網(wǎng)站設(shè)計(jì)”,“東港網(wǎng)站推廣”以來(lái)，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

tree：

非線性結(jié)構(gòu)，每個(gè)元素可以有多個(gè)前驅(qū)（前面）和后繼（后面）；而線性結(jié)構(gòu)中，前面有一個(gè)后面有一個(gè)；

樹是n(n>=0)個(gè)元素的集合：

n=0時(shí)，稱為空樹；

樹只有一個(gè)特殊的沒(méi)有前驅(qū)的元素，稱為樹的root根；

樹中除了根結(jié)點(diǎn)外，其余元素只能有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼；

遞歸定義：

樹T是n(n>=0)個(gè)元素的集合，n=0時(shí)，稱為空樹；

有且只有一個(gè)特殊元素根，剩余元素都可被劃分為m個(gè)互不相交的集合T1,T2,T3...Tn，而每一個(gè)集合都是樹，稱為T的子樹SubTree，子樹也有自己的根；

樹的概念：

結(jié)點(diǎn)，樹中的數(shù)據(jù)元素；

結(jié)點(diǎn)的degree度，結(jié)點(diǎn)擁有的子樹的數(shù)目稱為度，記作d(v)；

葉子結(jié)點(diǎn)，結(jié)點(diǎn)的度為0，稱為葉子結(jié)點(diǎn)leaf、終端結(jié)點(diǎn)、末端結(jié)點(diǎn)；

分支結(jié)點(diǎn)，結(jié)點(diǎn)的度不為0，稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)；

分支，結(jié)點(diǎn)之間的關(guān)系；

內(nèi)部結(jié)點(diǎn)，除根結(jié)點(diǎn)外的分支結(jié)點(diǎn)，當(dāng)然也不包括葉子結(jié)點(diǎn)，掐頭去尾；

樹的度是樹內(nèi)各結(jié)點(diǎn)的度的大值，D結(jié)點(diǎn)大為3，樹的度數(shù)就是3；

child，孩子結(jié)點(diǎn)|兒子結(jié)點(diǎn)，結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子，B是A的孩子結(jié)點(diǎn)；

parent，雙親結(jié)點(diǎn)|父結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)是它各子樹的根結(jié)點(diǎn)的雙親，A是B的雙親結(jié)點(diǎn)；

sibling，兄弟結(jié)點(diǎn)，具有相同雙親結(jié)點(diǎn)的結(jié)點(diǎn)，B、C；

祖先結(jié)點(diǎn)，從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上所有的結(jié)點(diǎn)，A、B、D都是G的祖先結(jié)點(diǎn)，A、C、E是J的祖先結(jié)點(diǎn)；

子孫結(jié)點(diǎn)，結(jié)點(diǎn)的所有子樹上的結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫，B的子孫是D、G、H、I；

level，結(jié)點(diǎn)的層次，根節(jié)點(diǎn)為第一層，根的孩子為第二層，以此類推，記作L(v)，上圖L(4)；

depth，樹的深度|高度，樹的層次的大值，上圖樹的深度為4；

堂兄弟，雙親在同一層的結(jié)點(diǎn)，D和E，D和F；

有序樹，結(jié)點(diǎn)的子樹是有順序的（兄弟有大小，有先后次序），不能交換；（計(jì)算機(jī)要處理的數(shù)據(jù)都是有序的，所謂的隨機(jī)是假隨機(jī)）；

無(wú)序樹，結(jié)點(diǎn)的子樹是無(wú)序的，可以交換；

路徑，樹中的k個(gè)結(jié)點(diǎn)n1,n2...nk，滿足ni是n(i+1)的雙親，稱為n1到nk的一條路徑，就是一條線串下來(lái)的，前一個(gè)都是后一個(gè)的雙親結(jié)點(diǎn)（父結(jié)點(diǎn)|前驅(qū)）；

路徑長(zhǎng)度=路徑上結(jié)點(diǎn)數(shù)-1，也是分支樹，上圖路徑長(zhǎng)度為3；

森林，m(m>=)棵不相交的樹的集合，對(duì)于結(jié)點(diǎn)而言，其子樹的集合就是森林，A結(jié)點(diǎn)的2棵子樹的集合就是森林；

樹的特點(diǎn)：

唯一的根；

子樹不相交；

除了根以外，每個(gè)元素只能有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼；

根結(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)（前驅(qū)），葉子結(jié)點(diǎn)沒(méi)有孩子結(jié)點(diǎn)（后繼）；

vi是vj的雙親，則L(vi)=L(vj)-1，即雙親比孩子結(jié)點(diǎn)的層數(shù)少1；

堂兄弟的雙親是兄弟關(guān)系嗎？不一定

二叉樹：

每個(gè)結(jié)點(diǎn)最多2棵子樹，二叉樹不存在度數(shù)大于2的結(jié)點(diǎn)；

它是有序樹，左子樹、右子樹是順序的，不能交換次序；

即使某個(gè)結(jié)點(diǎn)只有一棵子樹，也要確定它是在左子樹還是右子樹；

二叉樹的五種基本形態(tài)：

空二叉樹；

只有一個(gè)根結(jié)點(diǎn)；

根結(jié)點(diǎn)只有左子樹；

根結(jié)點(diǎn)只有右子樹；

根結(jié)點(diǎn)有左子樹和右子樹；

斜樹：

左斜樹，所有結(jié)點(diǎn)都只有左子樹；

右斜樹，所有結(jié)點(diǎn)都只有右子樹；

滿二叉樹：

一棵二叉樹的所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子結(jié)點(diǎn)只存在最下面一層；

complete binary tree完全二叉樹：

若二叉樹的深度為k，二叉樹的層數(shù)從1到k-1層的結(jié)點(diǎn)數(shù)都達(dá)到了大個(gè)數(shù)，在第k層的所有結(jié)點(diǎn)都集中在最左邊，這就是完全二叉樹；

完全二叉樹由滿二叉樹引出；

滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹；

k為深度（1=<k<=n），由結(jié)點(diǎn)總數(shù)大值為（2**k）-1，當(dāng)達(dá)到大值的時(shí)候就是滿二叉樹；

舉例：

二叉樹性質(zhì)：

性質(zhì)1：

在二叉樹的第i層上至多有2**(i-1)個(gè)結(jié)點(diǎn)（i>=1），1,2,4,8,16；

性質(zhì)2：

深度為k的二叉樹，至多有(2**k)-1個(gè)結(jié)點(diǎn)（k>=1）；

一層2-1；

二層4-1=1+2=3；

三層8-1=1+2+4=7；

性質(zhì)3：

對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度數(shù)為2的結(jié)點(diǎn)為n2，則有n0=n2+1；

即，葉子結(jié)點(diǎn)數(shù)-1=度數(shù)為2的結(jié)點(diǎn)數(shù)；

證明：

總結(jié)點(diǎn)數(shù)為n=n0+n1+n2，n1為度數(shù)為1的結(jié)點(diǎn)總數(shù)；

一棵樹的分支樹為n-1，因?yàn)槌烁Y(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)分支，即n0+n1+n2-1；

分支樹還等于n0*0+n1*1+n2*2，n2是2分支結(jié)點(diǎn)，所以乘以2，2*n2+n1；

可得2*n2+n1=n0+n1+n2-1==>n2=n0-1；

其它性質(zhì)：

高度為k的二叉樹，至少有k個(gè)結(jié)點(diǎn)（含有n(n>=1)的結(jié)點(diǎn)的二叉樹高度至多為n）；

含有n(n>=1)的結(jié)點(diǎn)的二叉樹的高度至多為n，最小為math.ceil(log2(n+1))，不小于對(duì)數(shù)值的最小整數(shù)向上取整；

假設(shè)高度為h，(2**h)-1=n，層次數(shù)是取整，如果是8個(gè)結(jié)果，3.1699要向上取整為4，為4層，h=log2(n+1)；

性質(zhì)4：

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為int(log₂n)+1或math.ceil(log₂(n+1))；

性質(zhì)5：

如果有一棵n個(gè)結(jié)點(diǎn)的完全二叉樹（深度為性質(zhì)4），結(jié)點(diǎn)按照層序編號(hào)，i為結(jié)點(diǎn)編號(hào)；

如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無(wú)雙親；

如果i>1，則其雙親是int(i//2)，向下取整，子結(jié)點(diǎn)的編號(hào)整除2得到的就是父結(jié)點(diǎn)的編號(hào)；父結(jié)點(diǎn)如果是i，那么左孩子結(jié)點(diǎn)就是2i，右孩子結(jié)點(diǎn)就是2i+1；

如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子，即結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，否則其左孩子結(jié)點(diǎn)存在編號(hào)為2i；

如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子，注意并不能說(shuō)明結(jié)點(diǎn)i沒(méi)有左孩子，否則右孩子結(jié)點(diǎn)存在編號(hào)為2i+1；

樹的遍歷：

二叉樹的遍歷：

遍歷，迭代所有元素一遍；

樹的遍歷，對(duì)樹中所有元素不重復(fù)的訪問(wèn)一遍，也稱掃描；

廣度優(yōu)先遍歷：

層序遍歷，按樹的層次，從第一層開(kāi)始，自L左向R右遍歷元素，如ABCDEFGHI；

深度優(yōu)先遍歷：

前序遍歷，也叫先序遍歷，也叫先根遍歷，DLR，從根結(jié)點(diǎn)開(kāi)始，先左子樹后右子樹，每個(gè)子樹內(nèi)部依然是先根結(jié)點(diǎn)，再左子樹后右子樹，遞歸遍歷，如ABDGHCEIF；

中序遍歷，也叫中根遍歷，LDR，從根結(jié)點(diǎn)的械子樹開(kāi)始遍歷，然后是根結(jié)點(diǎn)，再右子樹，每個(gè)子樹內(nèi)部，先左子樹，再根結(jié)點(diǎn)，再右子樹，遞歸遍歷，如GDHBAIECF，GDHBAEICF；

后序遍歷，也叫后根遍歷，LRD，先左子樹，后右子樹，再根結(jié)點(diǎn)，每個(gè)子樹內(nèi)部依然是先左子樹，后右子樹，再根結(jié)點(diǎn)，遞歸遍歷，如GHDBIEFCA；

遍歷序列：

將樹中所有元素遍歷一遍后，得到的元素的序列，將層次結(jié)構(gòu)轉(zhuǎn)換成了線性結(jié)構(gòu)；

heap sort，堆排序：

heap堆，是一個(gè)完全二叉樹；

完全二叉樹的每個(gè)非葉子結(jié)點(diǎn)都要大于或等于其左右孩子結(jié)點(diǎn)的值，稱為大頂堆；

完全二叉樹的每個(gè)非葉子結(jié)點(diǎn)都要小于或等于其左右孩子結(jié)點(diǎn)的值，稱為小頂堆；

根結(jié)點(diǎn)一定是大頂堆中的大值，一定是小頂堆中的最小值，即堆頂一定是一個(gè)極值（極大|極?。?；

注：

不穩(wěn)定，值相同的不同元素順序是固定的；

1、構(gòu)建完全二叉樹：

待排序數(shù)字為3、2、8、4、5、1、6、7、9；

構(gòu)建一個(gè)完全二叉樹存放數(shù)據(jù)，并根據(jù)性質(zhì)5對(duì)元素編號(hào)，放入順序的數(shù)據(jù)結(jié)構(gòu)中；

構(gòu)造一個(gè)列表為[0,3,2,8,4,5,1,6,7,9]，列表的index與性質(zhì)5中元素編號(hào)對(duì)應(yīng)；

2、構(gòu)建大頂堆：

核心算法是堆結(jié)點(diǎn)的調(diào)整；

度數(shù)為2的結(jié)點(diǎn)A，如果它的左右孩子結(jié)點(diǎn)的大值比它大的，將這個(gè)大值和該結(jié)點(diǎn)交換；

度數(shù)為1的結(jié)點(diǎn)A，如果它的左右孩子的值大于它，則交換；

如果結(jié)點(diǎn)A被交換到新的位置，還需要和其孩子結(jié)點(diǎn)重復(fù)上面的過(guò)程；

起點(diǎn)結(jié)點(diǎn)的選擇：

從完全二叉樹的最后一個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)開(kāi)始，即最后一層的最右邊葉子結(jié)點(diǎn)的父結(jié)點(diǎn)開(kāi)始；

結(jié)點(diǎn)數(shù)為n，則起點(diǎn)結(jié)點(diǎn)的編號(hào)為n//2（性質(zhì)5）；

下一個(gè)結(jié)點(diǎn)的選擇：

從起始結(jié)點(diǎn)開(kāi)始向左找其同層結(jié)點(diǎn)，到頭后再?gòu)纳弦粚拥淖钣疫吔Y(jié)點(diǎn)開(kāi)始繼續(xù)向左逐個(gè)查找，直至根結(jié)點(diǎn)（編號(hào)為1，即索引為1）；

大頂堆的目標(biāo)：

確保每個(gè)根結(jié)點(diǎn)的都比左右結(jié)點(diǎn)的值大；

排序：

將大頂堆根結(jié)點(diǎn)空上大值，和最后一個(gè)葉子結(jié)點(diǎn)交換，那么最后一個(gè)葉子結(jié)點(diǎn)就是大值，將這個(gè)葉子結(jié)點(diǎn)排隊(duì)在待排序結(jié)點(diǎn)之外；

從根結(jié)點(diǎn)開(kāi)始（新的根結(jié)點(diǎn)），重新調(diào)整為大頂堆后，重復(fù)上一步；

總結(jié)：

是復(fù)用堆性質(zhì)的一種選擇排序，在堆頂選出大值或最小值；

時(shí)間復(fù)雜度：O(nlogn）；由于堆排序?qū)υ加涗浀呐判驙顟B(tài)并不敏感，因此它無(wú)論是最好、最壞、平均時(shí)間復(fù)雜度均為O(logn；)

空間復(fù)雜度：只是使用了一個(gè)交換用的空間，空間復(fù)雜度O(1)；

穩(wěn)定性：不穩(wěn)定的排序算法；

打印出一個(gè)堆結(jié)構(gòu)的完全二叉樹？用于理解堆排序

思路：投影（光從頂照下來(lái)），網(wǎng)頁(yè)編程中的柵格；

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

新聞標(biāo)題：15數(shù)據(jù)結(jié)構(gòu)tree_堆排序-創(chuàng)新互聯(lián)
本文URL：http://www.muchs.cn/article36/dsjepg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、網(wǎng)站營(yíng)銷、小程序開(kāi)發(fā)、移動(dòng)網(wǎng)站建設(shè)、Google、企業(yè)建站

廣告

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