- # 二叉树的遍历
- # 对二叉树中的所有元素不重复的访问一遍
- # 广度优先遍历
- # 层序遍历
- # 从第一层开始, 没一层从左至右遍历元素
- # 深度优先遍历
- # 假设树的根节点为 D, 左子树为 L, 右子树为 R, 且要求 L 一定在 R 之前, 则有以下遍历方式:
- # 前序遍历: 也叫先序遍历, 也叫先根遍历, DLR
- # 中序遍历: 也叫中根遍历, LDR
- # 后序遍历: 也叫后根遍历, LRD
- # 遍历序列: 将树中所有元素遍历一遍后, 得到的元素的序列, 将层次结构转换成了线性结构
- # 堆排序
- # 堆是一个完全二叉树
- # 每个非叶子结点的值都要大于或者等于其左右孩子结点的值, 称为大顶堆
- # 每个非叶子结点的值都要小于或者等于其左右孩子结点的值, 称为小顶堆
- # 根结点一定是大顶堆中的最大值, 一定是小顶堆中的最小值
- # 例子: 构建一个完全二叉树 (序列 -> 完全二叉树 -> 大顶堆 -> 排序 -> 大顶堆 -> 排序 ...)
- # 待排序数字为: 30 20 80 40 50 10 60 70 90
- # 构建一个完全二叉树存放数据, 并根据性质 5 对元素编号, 放入顺序的数据结构中
- # 性质 5: 按层依次编号
- # 构建一个列表为 [0, 30, 20, 80, 40, 50, 10, 60, 70, 90]***
- # 0 为补位, 因为列表下表从 0 开始, 想从 1 开始进行使用
- # 构建大顶堆的核心算法
- # 度数为 2 的结点 A, 如果它的左右孩子结点的最大值比它大, 将这个最大值和该结点交换
- # 度数为 1 的结点 A, 如果它的左孩子的值比它大, 则交换
- # 如果结点 A 被交换到新的位置, 还需要和其孩子结点重复上面的过程
- # 构建大顶堆 - 起点结点的选择
- # 从完全二叉树的最后一个结点的双亲结点开始, 即最后一层的最右边叶子结点的父节点开始 ***
- # 结点数为 n, 则起始结点的编号 n//2(性质 5)
- # 构建大顶堆 - 下一个结点的选择
- # 从起始结点开始向左找其同层结点, 到头后再从上一层的最右边结点开始继续向左逐个查找, 直到根节点
- # 下一结点: n -> n-1 -> n-2 ... 1
- # 跟结点计算完毕后, 如果有交换, 则还需要向下对左右子树进行再次排序
- # 大顶堆的目标
- # 确保每个结点的值都比左右结点的值大
- # 排序
- # 将大顶堆根结点这个最大值和最后一个叶子结点交换, 那么最后一个叶子结点就是最大值, 将这个叶子结点排除在待排序结点外
- # 从根结点开始 (新的根结点), 重新调整为大顶堆后, 重复上一步
- # 将列表打印成树 (堆排序辅助函数)
- import math
- def printTree(lst):
- treeLen = len(lst)
- treeLay = math.ceil(math.log2(treeLen + 1)) # 树层数
- index = 0
- treeWidth = 2 ** treeLay - 1 # 树宽度
- for i in range(treeLay):
- for j in range(2**i):
- print('{:^{}}'.format(lst[index], treeWidth), end=' ')
- index += 1
- if index>= treeLen:
- break
- treeWidth = treeWidth//2
- print()
- lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
- printTree(lst)
- # 调整当前节点
- def heap_adjust(n, i, array:list): # array:list 表示 array 变量的类型是 list
- '''
- 调整当前节点核心算放
- :param n: 待比较数字的个数
- :param i: 当前节点的下标
- :param array: 待排序数据
- :return:None
- '''
- while 2 * i <= n: # 性质 5,=n 只有左子树
- # 孩子结点判断 2i 为左孩子, 2i+1 为右孩子
- lChild_index = 2 * i
- maxChild_index = lChild_index # n=2i
- if n> lChild_index and array[lChild_index + 1]> array[lChild_index]: # n>2i 说明还有右孩子
- maxChild_index = lChild_index + 1 # n=2i+1
- # 和子树的根节点比较
- if array[maxChild_index]> array[i]:
- array[i], array[maxChild_index] = array[maxChild_index], array[i] # 交换
- i = maxChild_index # 被交换后, 需要判断是否还需要调整
- else:
- break
- printTree(array)
- print('--------------------------')
- # 构建大顶堆
- def maxHeap(total, array:list):
- for i in range(total//2, 0, -1):
- heap_adjust(total, i, array) # 调整当前结点
- return array
- total = 9
- origin = [0,30, 20, 80, 40, 50, 10, 60, 70, 90]
- print('maxHeap is')
- printTree(maxHeap(total, origin))
- # 结论: 第一层是最大值, 第二层一定有个次大值
来源: http://www.bubuko.com/infodetail-2769866.html