?

創(chuàng)新互聯(lián)公司主營新羅網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,app軟件定制開發(fā),新羅h5小程序制作搭建,新羅網(wǎng)站營銷推廣歡迎新羅等地區(qū)企業(yè)咨詢

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

?

tree：

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

?

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

n=0時，稱為空樹；

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

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

?

遞歸定義：

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

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

?

樹的概念：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

無序樹，結(jié)點的子樹是無序的，可以交換；

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

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

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

?

樹的特點：

唯一的根；

子樹不相交；

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

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

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

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

?

?

?

二叉樹：

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

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

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

?

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

空二叉樹；

只有一個根結(jié)點；

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

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

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

斜樹：

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

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

?

滿二叉樹：

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

?

complete binary tree完全二叉樹：

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

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

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

k為深度（1=

舉例：

?

二叉樹性質(zhì)：

性質(zhì)1：

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

?

性質(zhì)2：

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

一層2-1；

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

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

?

性質(zhì)3：

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

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

證明：

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

一棵樹的分支樹為n-1，因為除了根結(jié)點外，其余結(jié)點都有一個分支，即n0+n1+n2-1；

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

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

?

其它性質(zhì)：

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

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

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

?

性質(zhì)4：

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

?

性質(zhì)5：

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

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

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

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

如果2i+1>n，則結(jié)點i無右孩子，注意并不能說明結(jié)點i沒有左孩子，否則右孩子結(jié)點存在編號為2i+1；

?

?

?

樹的遍歷：

二叉樹的遍歷：

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

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

?

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

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

?

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

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

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

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

?

遍歷序列：

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

?

?

?

heap sort，堆排序：

heap堆，是一個完全二叉樹；

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

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

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

?

注：

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

?

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

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

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

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

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

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

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

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

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

?

起點結(jié)點的選擇：

從完全二叉樹的最后一個結(jié)點的雙親結(jié)點開始，即最后一層的最右邊葉子結(jié)點的父結(jié)點開始；

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

?

下一個結(jié)點的選擇：

從起始結(jié)點開始向左找其同層結(jié)點，到頭后再從上一層的最右邊結(jié)點開始繼續(xù)向左逐個查找，直至根結(jié)點（編號為1，即索引為1）；

?

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

確保每個根結(jié)點的都比左右結(jié)點的值大；

?

排序：

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

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

?

總結(jié)：

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

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

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

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

?

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

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

?

?