樹，樹的遍歷和堆排序

一 樹基礎(chǔ)

1 樹的定義

1 兩種定義方式

樹： 非線性結(jié)構(gòu)

1 樹是n(n>=0)個(gè)元素的集合
n=0時(shí)，稱為空樹
樹只有一個(gè)特殊的節(jié)點(diǎn)是沒有前驅(qū)元素的，稱為樹的根，及Root
樹中除了根節(jié)點(diǎn)外，其余的元素只能有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼，根沒有前驅(qū)，只有后繼

2 遞歸定義
樹T 是n(n>=0)個(gè)元素的集合，n=0時(shí)，稱為空樹
其有且只有一個(gè)特殊元素及根，剩余的元素都可以被劃分為m個(gè)互不相交的集合，T1,T2,T3...Tm，而每個(gè)集合都是樹，稱為T的子樹subtree，其子樹也有自己的根

2 數(shù)的集群術(shù)語(yǔ)

前驅(qū)： 當(dāng)前節(jié)點(diǎn)前面的元素
后驅(qū)： 當(dāng)前節(jié)點(diǎn)后面的元素
結(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)，終端結(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)，及掐頭，去尾，留中間
樹的度： 樹的度是各個(gè)節(jié)點(diǎn)的度的最大值。

孩子（兒子child）結(jié)點(diǎn)：結(jié)點(diǎn)的子樹的根節(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子
雙親（父Parent）結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)是它各子樹的根結(jié)點(diǎn)的雙親。
兄弟（sibling）結(jié)點(diǎn)：具有相同雙親結(jié)點(diǎn)的結(jié)點(diǎn)
祖先結(jié)點(diǎn)：從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)
子孫結(jié)點(diǎn)：結(jié)點(diǎn)所有子樹上的結(jié)點(diǎn)都稱為子孫
結(jié)點(diǎn)的層次：根結(jié)點(diǎn)為第一層，根結(jié)點(diǎn)的孩子為第二層，依次類推，記做L(v)
樹的深度（高度Depth）：樹的層次的最大值
堂兄弟：雙親在同一層的結(jié)點(diǎn)。

有序樹：結(jié)點(diǎn)的子樹是有序的（兄弟有大小，有先后次序），不能交換
無(wú)序樹：結(jié)點(diǎn)的子樹是無(wú)序的，可以交換

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

路徑長(zhǎng)度=路徑上結(jié)點(diǎn)長(zhǎng)度-1，及分支數(shù)

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

3 樹特點(diǎn)：

1 唯一的根
2 子樹不相交
3 除了根以外，每個(gè)元素只能有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼
4 根結(jié)點(diǎn)沒有雙親節(jié)點(diǎn)（前驅(qū)），葉子節(jié)點(diǎn)沒有孩子結(jié)點(diǎn)（后繼）
5 vi是vj的雙親，則L(vi)=L(vj)-1,也就是說(shuō)雙親比孩子節(jié)點(diǎn)的層次小1

2 二叉樹概念

1 特點(diǎn)

1 每個(gè)結(jié)點(diǎn)最多2個(gè)子樹
二叉樹不存在度數(shù)大于2的節(jié)點(diǎn)
2 它是有序樹，左子樹，右子樹是順序的，不能交換次序
3 即使某一個(gè)結(jié)點(diǎn)只有一顆子樹，也要確定其是左子樹還是右子樹

2 二叉樹的五種形態(tài)

1 空二叉樹
2 只有一個(gè)根結(jié)點(diǎn)
3 根結(jié)點(diǎn)只有左子樹
4 根結(jié)點(diǎn)只有右子樹
5 根結(jié)點(diǎn)有左子樹和右子樹

3 斜樹

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

4 滿二叉樹

一顆二叉樹的所有分支結(jié)點(diǎn)都存在左子樹和右子樹，且所有葉子節(jié)點(diǎn)都只存在在最下面一層。
同樣深度的二叉樹，滿二叉樹節(jié)點(diǎn)最多
k為深度(1<=k<=n)，則節(jié)點(diǎn)總數(shù)為 2**(k)-1

5 完全二叉樹

若二叉樹的深度為k，二叉樹的層數(shù)從1到k-1層的結(jié)點(diǎn)都打到了最大個(gè)數(shù)，在第k層的所有結(jié)點(diǎn)都集中在最左邊，這就是完全二叉樹
完全二叉樹由滿二叉樹引出
滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹
k為深度(1<=k<=n)，則結(jié)點(diǎn)總數(shù)最大值為2**k-1,當(dāng)達(dá)到最大值的時(shí)候就是滿二叉樹

3 二叉樹的性質(zhì)

1 在二叉樹中的第i層上最多有2**i-1 個(gè)節(jié)點(diǎn)(i>=1)

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

3 對(duì)于任何一顆二叉樹T，如果其終點(diǎn)節(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，其中n0為度數(shù)為0的節(jié)點(diǎn)，及葉子節(jié)點(diǎn)的數(shù)量，n1為度數(shù)為1 的節(jié)點(diǎn)的數(shù)量，n2為節(jié)點(diǎn)為2度數(shù)的數(shù)量。
一棵樹的分支數(shù)為n-1，因?yàn)槌烁?jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)分支，及n0+n1+n2-1
分支數(shù)還等于n0*0+n1*1+n2*2及 n1+2n2=n-1
可知 2*n2+n1=n0+n1+n2-1 及就是 n2=n0-1

4 高度為k的二叉樹，至少有k個(gè)節(jié)點(diǎn)
5 具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為int(log2n)+1 或者 math.ceil(log2(n+1))

6 有一個(gè)n個(gè)節(jié)點(diǎn)的完全二叉樹， 結(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，則左孩子是2i，若有右孩子，則右孩子是2i+1,。
如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子，及結(jié)點(diǎn)為葉子結(jié)點(diǎn)，否則其左孩子節(jié)點(diǎn)存在編號(hào)為2i。

如果2i+1>n，則節(jié)點(diǎn)i無(wú)右孩子，此處未說(shuō)明是否不存在左孩子，否則右孩子的節(jié)點(diǎn)存在編號(hào)為2i+1。

二 二叉樹遍歷

1 遍歷方式

遍歷： 及對(duì)樹中的元素不重復(fù)的訪問一遍，又稱為掃描

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

一次將一層全部拿完，層序遍歷

及 1 2 3 4 5一層一層的從左向右拿取

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

設(shè)樹的根結(jié)點(diǎn)為D，左子樹為L(zhǎng)，右子樹為R。且要求L一定要在R之前，則有下面幾種遍歷方式

1 前序遍歷，也叫先序遍歷，也叫先跟遍歷，DLR

1-2-4-5-3-6
2 中序遍歷，也叫中跟遍歷， LDR

4-2-5-1-6-3
3 后序遍歷，也叫后跟遍歷，LRD

4-5-2-6-3-1

三 堆排序

1 堆定義

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

3 每個(gè)非葉子結(jié)點(diǎn)都要小于或者等于其左右孩子結(jié)點(diǎn)的值稱為小頂堆

4 根節(jié)點(diǎn)一定是大頂堆的最大值，小頂堆中的最小值

2 堆排序

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

1 待排序數(shù)字為 49 38 65 97 76 13 27 49

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

3 構(gòu)造一個(gè)列表為 [0,49,38,65,97,76,13,27,49]的列表

2 構(gòu)建大頂堆

1 度數(shù)為2的結(jié)點(diǎn)，如果他的左右孩子最大值比它大，則將這個(gè)值和該節(jié)點(diǎn)交換
2 度數(shù)為1 的結(jié)點(diǎn)，如果它的左孩子的值大于它，則交換
3 如果節(jié)點(diǎn)被置換到新的位置，則還需要和其孩子節(jié)點(diǎn)重復(fù)上述過程

3 構(gòu)建大頂堆--起點(diǎn)選擇

1 從完全二叉樹的最后一個(gè)結(jié)點(diǎn)的雙親開始，及最后一層的最右邊的葉子結(jié)點(diǎn)的父結(jié)點(diǎn)開始
2 結(jié)點(diǎn)數(shù)為n,則起始節(jié)點(diǎn)的編號(hào)為n//2(及最后一個(gè)結(jié)點(diǎn)的父節(jié)點(diǎn))

4 構(gòu)建大頂堆--下一個(gè)節(jié)點(diǎn)的選擇

從起始節(jié)點(diǎn)開始向左尋找其同層節(jié)點(diǎn)，到頭后再?gòu)纳弦粚拥淖钣疫吂?jié)點(diǎn)開始繼續(xù)向左逐步查找，直到根節(jié)點(diǎn)

5 大頂堆目標(biāo)

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

第一步，調(diào)換97和38，保證跟大

第二步，調(diào)換49和97

第三步，調(diào)換76和49

第四步，調(diào)換38和49

此時(shí)大頂堆的構(gòu)建已經(jīng)完成

3 排序

將大頂堆根節(jié)點(diǎn)這個(gè)最大值和最后一個(gè)葉子節(jié)點(diǎn)進(jìn)行交換，則最后一個(gè)葉子節(jié)點(diǎn)成為了最大值，將這個(gè)葉子節(jié)點(diǎn)排除在待排序節(jié)點(diǎn)之外，并從根節(jié)點(diǎn)開始，重新調(diào)整為大頂堆，重復(fù)上述步驟。

四 實(shí)戰(zhàn)和代碼

1 打印樹

l1=[1,2,3,4,5,6,7,8,9]
打印結(jié)果應(yīng)當(dāng)如下

思路：可通過將其數(shù)字映射到下方的一條線上的方式進(jìn)行處理及就是 8 4 9 2 0 5 0 1 0 6 0 3 0 7 0 的數(shù)字，其之間的空格可以設(shè)置為一個(gè)空格的長(zhǎng)度，其數(shù)字的長(zhǎng)度也可設(shè)置為固定的2，則

則第一層第一個(gè)數(shù)字據(jù)前面的空格個(gè)數(shù)為7個(gè)，據(jù)后面的空格也是7個(gè)，
第二層第一個(gè)數(shù)字據(jù)前面的空格個(gè)數(shù)為3個(gè)，第二個(gè)數(shù)字距離后面的空格也是3個(gè)，
第三層據(jù)前面的空格為1，第三層最后一個(gè)據(jù)后面的空格也是1，
第四層據(jù)前面的空格是0，第四層最后一個(gè)據(jù)后面的空格也是0，
現(xiàn)在在其標(biāo)號(hào)前面從1開始，則層數(shù)和空格之間的關(guān)系是

1 7
2 3
3 1
4 0
轉(zhuǎn)換得到
4 7
3 3
2 1
1 0

及就是 2**(l-1) -1 l 表示層數(shù)
間隔關(guān)系如下
1 0
2 8
3 4
4 2
轉(zhuǎn)換得到
4 0
3 8
2 4
1 2
及就是 2**l其中l(wèi) 表示層數(shù)。

代碼如下

import  math 
# 打印二叉樹
def  t(list):
    '''
    層數(shù)      層數(shù)取反(depth+1-i,depth表示總層數(shù)，此處為4，i表示層數(shù))   據(jù)前面的空格數(shù)            間隔數(shù)        每層字?jǐn)?shù)為
    1            4                                                              7                     0              1
    2            3                                                              3                     7              2
    3            2                                                              1                     3              4
    4            1                                                              0                     1              8
                                                                    (2**(depth-i)-1)      (2**(depth-i)-1)        (2**i）   

    層數(shù)和數(shù)據(jù)長(zhǎng)度的關(guān)系是 n表示的是數(shù)據(jù)長(zhǎng)度
    1     1  
    2-3   2   
    4-7   3
    8-15  4       
    2**(i-1)<num<(2**i)-1,及就是int(log2n) +1 及 math.ceil(log2n)
    '''
    index=1
    depth=math.ceil(math.log(len(list),2))    #此處獲取到的是此列表轉(zhuǎn)換成二叉樹的深度，此處前面插入了一個(gè)元素，保證列表和二叉樹一樣，其真實(shí)數(shù)據(jù)都是從1開始
    sep='  ' # 此處表示數(shù)字的寬度 
    for  i in range(depth):
        offset=2**i #每層的數(shù)字?jǐn)?shù)量1  2  4  8  
        print (sep*(2**(depth-i-1)-1),end="")  # 此處取的是前面空格的長(zhǎng)度
        line=list[index:index+offset] #提取每層的數(shù)量
        for  j,x  in enumerate(line):
            print ("{:>{}}".format(x,len(sep)),end="") # 此處通過format來(lái)獲取其偏移情況,第一個(gè)x表示其大括號(hào)中的內(nèi)容，第二個(gè)表示偏移的程度
            interval= 0  if  i ==0  else  2**(depth-i)-1  # 此處獲取到的是間隔數(shù)，當(dāng)值大于1時(shí)，滿足如此表達(dá)式
            if  j < len(line)-1: #選擇最后一個(gè)時(shí)不打印最后一個(gè)的后面的空格，及就是1,3,7后面的空格
                print (sep*interval,end="")
        index += offset
        print ()

結(jié)果如下

2 堆排序算法實(shí)現(xiàn)

# 構(gòu)建一個(gè)子樹的大頂堆
def  heap_adjust(n,i,array):
    '''
    調(diào)整當(dāng)前結(jié)點(diǎn)（核心算法）
    調(diào)整的結(jié)點(diǎn)的起點(diǎn)在n//2（二叉樹性質(zhì)5結(jié)論），保證所有調(diào)整的結(jié)點(diǎn)都有孩子結(jié)點(diǎn)
    :param  n : 待比較數(shù)個(gè)數(shù)
    :param  i : 當(dāng)前結(jié)點(diǎn)下標(biāo)
    :param array : 待排序數(shù)據(jù)
    :return : None
    '''
    while  2*i<=n: # 孩子結(jié)點(diǎn)判斷，2i為左孩子，2i+1為右孩子 
        lchile_index= 2*i  #選擇結(jié)點(diǎn)起始并記錄 n=2*i-1,因?yàn)槠涫菑?開始，因此只有l(wèi)en()-1
        max_child_index=lchile_index  
        # 判斷左右孩子的大小，并將大的賦值給max_child_index 
        if  n > lchile_index  and  array[lchile_index+1] > array[lchile_index]: #說(shuō)明其有右孩子,且右孩子大于左孩子 
            max_child_index=lchile_index+1  #n=2i+1 # 此時(shí)賦值的是下標(biāo)
        # 判斷左右孩子的最大值和父結(jié)點(diǎn)比較，若左右結(jié)點(diǎn)的最大值大，則進(jìn)行交換
        if  array[max_child_index] > array[i]:  #此處的i是父節(jié)點(diǎn)，通過和父節(jié)點(diǎn)進(jìn)行比較來(lái)確認(rèn)其最大，
            array[i],array[max_child_index]=array[max_child_index],array[i]
            i= max_child_index   #右子節(jié)點(diǎn)的下標(biāo)會(huì)賦值到父結(jié)點(diǎn)，并將其值賦值到父結(jié)點(diǎn)，
        else:
            break 
# 構(gòu)建所有的大頂堆傳入?yún)?shù)
def  max_heap(total,array):
    for i in range(total//2,0,-1):  #構(gòu)建最后一個(gè)葉子結(jié)點(diǎn)的父結(jié)點(diǎn)
        heap_adjust(total,i,array)  #傳入總長(zhǎng)和最后一個(gè)葉子結(jié)點(diǎn)的父結(jié)點(diǎn)和數(shù)列
        print  (t(array))
    return  array
#構(gòu)建大頂堆，起點(diǎn)選擇    
def  sort(total,array):    # 此處起點(diǎn)是1，因此必須在前面添加一個(gè)元素，以保證其位置編號(hào)和樹相同
    while  total>1:
        max_heap(total,array)
        array[1],array[total]=array[total],array[1]  #將最后一個(gè)結(jié)點(diǎn)和第一個(gè)結(jié)點(diǎn)調(diào)換，
        total-=1
    return array

結(jié)果如下

3 總結(jié)

堆排序 Heap Sort 是利用堆性質(zhì)的一種選擇排序，在堆頂選出最大值或最小值
時(shí)間復(fù)雜度
堆排序的時(shí)間復(fù)雜度為O(nlog2 n)，由于堆排序?qū)υ加涗浀呐判驙顟B(tài)不敏感，因此其無(wú)論是最好，最壞和平均時(shí)間復(fù)雜度均為O（nlog2 n）

空間復(fù)雜度
只是使用了一個(gè)交換用的空間，其空間復(fù)雜度為O(1)
穩(wěn)定性
不穩(wěn)定的排序算法