15數據結構tree_堆排序

?

python內置數據結構——tree樹

?

tree：

非線性結構，每個元素可以有多個前驅（前面）和后繼（后面）；而線性結構中，前面有一個后面有一個；

?

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

n=0時，稱為空樹；

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

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

?

遞歸定義：

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

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

?

樹的概念：

結點，樹中的數據元素；

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

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

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

分支，結點之間的關系；

內部結點，除根結點外的分支結點，當然也不包括葉子結點，掐頭去尾；

樹的度是樹內各結點的度的最大值，D結點最大為3，樹的度數就是3；

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

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

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

祖先結點，從根結點到該結點所經分支上所有的結點，A、B、D都是G的祖先結點，A、C、E是J的祖先結點；

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

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

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

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

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

無序樹，結點的子樹是無序的，可以交換；

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

路徑長度=路徑上結點數-1，也是分支樹，上圖路徑長度為3；

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

?

樹的特點：

唯一的根；

子樹不相交；

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

根結點沒有雙親結點（前驅），葉子結點沒有孩子結點（后繼）；

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

堂兄弟的雙親是兄弟關系嗎？不一定

?

?

?

二叉樹：

每個結點最多2棵子樹，二叉樹不存在度數大于2的結點；

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

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

?

二叉樹的五種基本形態：

空二叉樹；

只有一個根結點；

根結點只有左子樹；

根結點只有右子樹；

根結點有左子樹和右子樹；

斜樹：

左斜樹，所有結點都只有左子樹；

右斜樹，所有結點都只有右子樹；

?

滿二叉樹：

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

?

complete binary tree完全二叉樹：

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

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

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

k為深度（1=<k<=n），由結點總數最大值為（2**k）-1，當達到最大值的時候就是滿二叉樹；

舉例：

?

二叉樹性質：

性質1：

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

?

性質2：

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

一層2-1；

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

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

?

性質3：

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

即，葉子結點數-1=度數為2的結點數；

證明：

總結點數為n=n0+n1+n2，n1為度數為1的結點總數；

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

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

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

?

其它性質：

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

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

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

?

性質4：

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

?

性質5：

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

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

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

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

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

?

?

?

樹的遍歷：

二叉樹的遍歷：

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

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

?

廣度優先遍歷：

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

?

深度優先遍歷：

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

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

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

?

遍歷序列：

將樹中所有元素遍歷一遍后，得到的元素的序列，將層次結構轉換成了線性結構；

?

?

?

heap sort，堆排序：

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

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

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

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

?

注：

不穩定，值相同的不同元素順序是固定的；

?

1、構建完全二叉樹：

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

構建一個完全二叉樹存放數據，并根據性質5對元素編號，放入順序的數據結構中；

構造一個列表為[0,3,2,8,4,5,1,6,7,9]，列表的index與性質5中元素編號對應；

2、構建大頂堆：

核心算法是堆結點的調整；

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

度數為1的結點A，如果它的左右孩子的值大于它，則交換；

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

?

起點結點的選擇：

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

結點數為n，則起點結點的編號為n//2（性質5）；

?

下一個結點的選擇：

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

?

大頂堆的目標：

確保每個根結點的都比左右結點的值大；

?

排序：

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

從根結點開始（新的根結點），重新調整為大頂堆后，重復上一步；

?

總結：

是復用堆性質的一種選擇排序，在堆頂選出最大值或最小值；

時間復雜度：O(nlogn）；由于堆排序對原始記錄的排序狀態并不敏感，因此它無論是最好、最壞、平均時間復雜度均為O(logn；)

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

穩定性：不穩定的排序算法；

?

打印出一個堆結構的完全二叉樹？用于理解堆排序

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

?

?