一 树基础

1 树的定义

1 两种定义方式

树: 非线性结构

1 树是n(n>=0)个元素的集合
n=0时,称为空树
树只有一个特殊的节点是没有前驱元素的,称为树的根,及Root
树中除了根节点外,其余的元素只能有一个前驱,可以有0个或多个后继,根没有前驱,只有后继


2 递归定义
树T 是n(n>=0)个元素的集合,n=0时,称为空树
其有且只有一个特殊元素及根,剩余的元素都可以被划分为m个互不相交的集合,T1,T2,T3...Tm,而每个集合都是树,称为T的子树subtree,其子树也有自己的根

2 数的集群术语

前驱: 当前节点前面的元素
后驱: 当前节点后面的元素
结点: 树中的数据元素
节点的度degree:节点拥有的子树的数目称为度,记做d(v)
叶子结点: 结点的度为0,称为叶子结点,终端结点,末端结点
分支结点:结点的度不为0,称为非终端结点或分支结点
分支:结点之间的关系,及连线
内部结点:除根节点以外的分支结点,当然不包括叶子节点,及掐头,去尾,留中间
树的度: 树的度是各个节点的度的最大值。


孩子(儿子child)结点:结点的子树的根节点称为该结点的孩子
双亲(父Parent)结点:一个结点是它各子树的根结点的双亲。
兄弟(sibling)结点:具有相同双亲结点的结点
祖先结点:从根结点到该结点所经分支上的所有结点
子孙结点:结点所有子树上的结点都称为子孙
结点的层次:根结点为第一层,根结点的孩子为第二层,依次类推,记做L(v)
树的深度(高度Depth):树的层次的最大值
堂兄弟:双亲在同一层的结点。

有序树:结点的子树是有序的(兄弟有大小,有先后次序),不能交换
无序树:结点的子树是无序的,可以交换


路径:树中的K个节点n1,n2...nk,满足ni是n(i+1)的双亲,称为n1到nk的一条路径,就是一条线串下来的,前一个都是后一个的父(前驱)节点

路径长度=路径上结点长度-1,及分支数

森林:m(m>=0)棵不相交的树的集合
对于结点而言,其子树的集合就是森林,

3 树特点:

1 唯一的根
2 子树不相交
3 除了根以外,每个元素只能有一个前驱,可以有0个或多个后继
4 根结点没有双亲节点(前驱),叶子节点没有孩子结点(后继)
5 vi是vj的双亲,则L(vi)=L(vj)-1,也就是说双亲比孩子节点的层次小1

2 二叉树概念

1 特点

1 每个结点最多2个子树
二叉树不存在度数大于2的节点
2 它是有序树,左子树,右子树是顺序的,不能交换次序
3 即使某一个结点只有一颗子树,也要确定其是左子树还是右子树

2 二叉树的五种形态

1 空二叉树
2 只有一个根结点
3 根结点只有左子树
4 根结点只有右子树
5 根结点有左子树和右子树

3 斜树

树,树的遍历和堆排序

左斜树:所有结点都只有左子树
右斜树:所有结点都只有右子树

4 满二叉树

树,树的遍历和堆排序

一颗二叉树的所有分支结点都存在左子树和右子树,且所有叶子节点都只存在在最下面一层。
同样深度的二叉树,满二叉树节点最多
k为深度(1<=k<=n),则节点总数为 2**(k)-1

5 完全二叉树

树,树的遍历和堆排序

若二叉树的深度为k,二叉树的层数从1到k-1层的结点都打到了最大个数,在第k层的所有结点都集中在最左边,这就是完全二叉树
完全二叉树由满二叉树引出
满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树
k为深度(1<=k<=n),则结点总数最大值为2**k-1,当达到最大值的时候就是满二叉树

3 二叉树的性质

1 在二叉树中的第i层上最多有2**i-1 个节点(i>=1)

2 深度为k的二叉树,至多有2**k -1个节点(k>=1)

3 对于任何一颗二叉树T,如果其终点节点数为n0,度数为2的节点为n2,则有n0=n2+1,及叶子结点数-1=度数为2的节点数。

证明:
总结点数为n=n0+n1+n2,其中n0为度数为0的节点,及叶子节点的数量,n1为度数为1 的节点的数量,n2为节点为2度数的数量。
一棵树的分支数为n-1,因为除了根节点外,其余结点都有一个分支,及n0+n1+n2-1
分支数还等于n0*0+n1*1+n2*2及 n1+2n2=n-1
可知 2*n2+n1=n0+n1+n2-1 及就是 n2=n0-1


4 高度为k的二叉树,至少有k个节点
5 具有n个节点的完全二叉树的深度为int(log2n)+1 或者 math.ceil(log2(n+1))

6 有一个n个节点的完全二叉树, 结点按照层序编号,如图

树,树的遍历和堆排序

如果i=1,则节点i是二叉树的根,无双亲,如果i>1,则其双亲为int(i/2),向下取整。就是叶子节点的编号整除2得到的就是父节点的编号,如果父节点是i,则左孩子是2i,若有右孩子,则右孩子是2i+1,。
如果2i>n,则结点i无左孩子,及结点为叶子结点,否则其左孩子节点存在编号为2i。

如果2i+1>n,则节点i无右孩子,此处未说明是否不存在左孩子,否则右孩子的节点存在编号为2i+1。

二 二叉树遍历

1 遍历方式

遍历: 及对树中的元素不重复的访问一遍,又称为扫描

1 广度优先遍历

一次将一层全部拿完,层序遍历

树,树的遍历和堆排序
及 1 2 3 4 5一层一层的从左向右拿取

2 深度优先遍历

设树的根结点为D,左子树为L,右子树为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 是一个完全二叉树
2 每个非叶子结点都要大于或等于其左右孩子结点的值称为大顶堆

树,树的遍历和堆排序

3 每个非叶子结点都要小于或者等于其左右孩子结点的值称为小顶堆

树,树的遍历和堆排序

4 根节点一定是大顶堆的最大值,小顶堆中的最小值

2 堆排序

1 构建完全二叉树

1 待排序数字为 49 38 65 97 76 13 27 49

2 构建一个完全二叉树存放数据,并根据性质5对元素进行编号,放入顺序的数据结构中

树,树的遍历和堆排序

3 构造一个列表为 [0,49,38,65,97,76,13,27,49]的列表

2 构建大顶堆

1 度数为2的结点,如果他的左右孩子最大值比它大,则将这个值和该节点交换
2 度数为1 的结点,如果它的左孩子的值大于它,则交换
3 如果节点被置换到新的位置,则还需要和其孩子节点重复上述过程

3 构建大顶堆--起点选择

树,树的遍历和堆排序

1 从完全二叉树的最后一个结点的双亲开始,及最后一层的最右边的叶子结点的父结点开始
2 结点数为n,则起始节点的编号为n//2(及最后一个结点的父节点)

4 构建大顶堆--下一个节点的选择

从起始节点开始向左寻找其同层节点,到头后再从上一层的最右边节点开始继续向左逐步查找,直到根节点

树,树的遍历和堆排序

5 大顶堆目标

确保每个结点的都比其左右结点的值大

树,树的遍历和堆排序
第一步,调换97和38,保证跟大

树,树的遍历和堆排序
第二步,调换49和97

树,树的遍历和堆排序
第三步,调换76和49

树,树的遍历和堆排序
第四步,调换38和49

此时大顶堆的构建已经完成

3 排序

将大顶堆根节点这个最大值和最后一个叶子节点进行交换,则最后一个叶子节点成为了最大值,将这个叶子节点排除在待排序节点之外,并从根节点开始,重新调整为大顶堆,重复上述步骤。

树,树的遍历和堆排序
树,树的遍历和堆排序
树,树的遍历和堆排序
树,树的遍历和堆排序
树,树的遍历和堆排序
树,树的遍历和堆排序
树,树的遍历和堆排序

四 实战和代码

1 打印树

l1=[1,2,3,4,5,6,7,8,9]
打印结果应当如下

树,树的遍历和堆排序

思路:可通过将其数字映射到下方的一条线上的方式进行处理及就是 8 4 9 2 0 5 0 1 0 6 0 3 0 7 0 的数字,其之间的空格可以设置为一个空格的长度,其数字的长度也可设置为固定的2,则

树,树的遍历和堆排序

则第一层第一个数字据前面的空格个数为7个,据后面的空格也是7个,
第二层第一个数字据前面的空格个数为3个,第二个数字距离后面的空格也是3个,
第三层据前面的空格为1,第三层最后一个据后面的空格也是1,
第四层据前面的空格是0,第四层最后一个据后面的空格也是0,
现在在其标号前面从1开始,则层数和空格之间的关系是

1 7
2 3
3 1
4 0
转换得到
4 7
3 3
2 1
1 0

及就是 2**(l-1) -1 l 表示层数
间隔关系如下
1 0
2 8
3 4
4 2
转换得到
4 0
3 8
2 4
1 2
及就是 2**l其中l 表示层数。

代码如下

import  math 
# 打印二叉树
def  t(list):
    '''
    层数      层数取反(depth+1-i,depth表示总层数,此处为4,i表示层数)   据前面的空格数            间隔数        每层字数为
    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)   

    层数和数据长度的关系是 n表示的是数据长度
    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))    #此处获取到的是此列表转换成二叉树的深度,此处前面插入了一个元素,保证列表和二叉树一样,其真实数据都是从1开始
    sep='  ' # 此处表示数字的宽度 
    for  i in range(depth):
        offset=2**i #每层的数字数量1  2  4  8  
        print (sep*(2**(depth-i-1)-1),end="")  # 此处取的是前面空格的长度
        line=list[index:index+offset] #提取每层的数量
        for  j,x  in enumerate(line):
            print ("{:>{}}".format(x,len(sep)),end="") # 此处通过format来获取其偏移情况,第一个x表示其大括号中的内容,第二个表示偏移的程度
            interval= 0  if  i ==0  else  2**(depth-i)-1  # 此处获取到的是间隔数,当值大于1时,满足如此表达式
            if  j < len(line)-1: #选择最后一个时不打印最后一个的后面的空格,及就是1,3,7后面的空格
                print (sep*interval,end="")
        index += offset
        print ()

结果如下
树,树的遍历和堆排序

2 堆排序算法实现

# 构建一个子树的大顶堆
def  heap_adjust(n,i,array):
    '''
    调整当前结点(核心算法)
    调整的结点的起点在n//2(二叉树性质5结论),保证所有调整的结点都有孩子结点
    :param  n : 待比较数个数
    :param  i : 当前结点下标
    :param array : 待排序数据
    :return : None
    '''
    while  2*i<=n: # 孩子结点判断,2i为左孩子,2i+1为右孩子 
        lchile_index= 2*i  #选择结点起始并记录 n=2*i-1,因为其是从0开始,因此只有len()-1
        max_child_index=lchile_index  
        # 判断左右孩子的大小,并将大的赋值给max_child_index 
        if  n > lchile_index  and  array[lchile_index+1] > array[lchile_index]: #说明其有右孩子,且右孩子大于左孩子 
            max_child_index=lchile_index+1  #n=2i+1 # 此时赋值的是下标
        # 判断左右孩子的最大值和父结点比较,若左右结点的最大值大,则进行交换
        if  array[max_child_index] > array[i]:  #此处的i是父节点,通过和父节点进行比较来确认其最大,
            array[i],array[max_child_index]=array[max_child_index],array[i]
            i= max_child_index   #右子节点的下标会赋值到父结点,并将其值赋值到父结点,
        else:
            break 
# 构建所有的大顶堆传入参数
def  max_heap(total,array):
    for i in range(total//2,0,-1):  #构建最后一个叶子结点的父结点
        heap_adjust(total,i,array)  #传入总长和最后一个叶子结点的父结点和数列
        print  (t(array))
    return  array
#构建大顶堆,起点选择    
def  sort(total,array):    # 此处起点是1,因此必须在前面添加一个元素,以保证其位置编号和树相同
    while  total>1:
        max_heap(total,array)
        array[1],array[total]=array[total],array[1]  #将最后一个结点和第一个结点调换,
        total-=1
    return array

结果如下
树,树的遍历和堆排序

3 总结

堆排序 Heap Sort 是利用堆性质的一种选择排序,在堆顶选出最大值或最小值
时间复杂度
堆排序的时间复杂度为O(nlog2 n),由于堆排序对原始记录的排序状态不敏感,因此其无论是最好,最坏和平均时间复杂度均为O(nlog2 n)

空间复杂度
只是使用了一个交换用的空间,其空间复杂度为O(1)
稳定性
不稳定的排序算法