二叉树的遍历和堆排序

二叉树的遍历和堆排序

## 二叉树的遍历

### 广度优先遍历

层序遍历 上到下 左到右 ABCDEFG

### 深度优先遍历

一探到底 根D 左子树L 右子树R
前序遍历 先根遍历 根 左 右 DLR
中序遍历 中根遍历 左 根 右 LDR
后序遍历 后根遍历 左 右 根 LRD

### 遍历序列

## 堆排序Heap Sort

大顶堆
小顶堆

构建完全二叉树

性质5:编号即索引

构建大顶堆
结点的度:叶子度为0,树的度是结点最大的度。

从最后一个叶子的父结点开始 n//2

import math

#居中对齐方案

def print_tree(array, unit_width=2):
length = len(array)
depth = math.ceil(math.log2(length + 1))

index = 0

width = 2 ** depth – 1 #行宽,最深的行 15
for i in range(depth):
for j in range(2 ** i):
#居中打印,后面追加一个空格
print(‘{:^{}}’.format(array[index], width * unit_width), end=’*’ * unit_width)
index += 1
if index >= length:
break
width = width // 2
print()

print_tree([x+1 for x in range(9) ])

#投影栅格实现
def print_tree(array):
index = 1
depth = math.ceil(math.log2(len(array)))
sep = ‘***’
for i in range(depth):
offset = 2 ** i
print(sep * (2 ** (depth – i – 1) – 1), end=”)
line = array[index:index + offset]
for j,x in enumerate(line):
print(“{:>{}}”.format(x, len(sep)), end=””)
interval = 0 if i == 0 else 2 ** (depth – i) – 1
if j < len(line) – 1:
print(sep * interval, end=”)

index += offset
print()

print_tree([0, 1, 2, 4, 10, 20, 32, 40, 600])

origin = [0, 30, 20, 80, 40, 50, 10, 60, 70, 90]

total = len(origin) – 1
# print(origin)
# print_tree(origin)
print(“=”*50)

def heap_adjust(n, i, array: list):
”’
调整当前节点(核心算法)

调整的结点的起点在n // 2, 保证所有调整的结点都有孩子结点
:param n: 待比较数个数
:param i: 当前结点的下标
:param array: 待排序数据
:return: None
”’

while 2 * i <= n:
#孩子结点判断 2i为左孩子 2i + 1为右孩子
lchild_index = 2 * i
max_child_index = lchild_index
if n > lchild_index and array[lchild_index + 1] > array[lchild_index]:# n > 2i 说明还有右孩子
max_child_index = lchild_index + 1

#和子树的根节点比较
if array[max_child_index] > array[i]:
array[i], array[max_child_index]=array[max_child_index], array[i]
i = max_child_index #被交换后,需要判断是否还需要调整
else:
break

# print_tree(array)

heap_adjust(total, total // 2, origin)
print(origin)
# print_tree(origin)

#构建大顶堆、大根堆
def max_heap(total, array:list):
for i in range(total//2, 0, -1):
heap_adjust(total, i, array)
return array

print_tree(max_heap(total, origin))

#排序
def sort(total, array:list):
while total > 1:
array[1], array[total] = array[total], array[1]
total -= 1
if total == 2 and array[total] >= array[total-1]:
break
heap_adjust(total,1,array)
return array

print_tree(sort(total, origin))
print(origin)

本文来自投稿,不代表Linux运维部落立场,如若转载,请注明出处:http://www.178linux.com/98644

(0)
JacoJaco
上一篇 2018-05-16
下一篇 2018-05-16

相关推荐

  • Python第二周小结

    不知不觉已经正式学习接触Python两周了,第二周主要开始了Python内置数据结构的学习,包括从一开始的列表list,元组tuple,字符串string,再到后来的bytes, bytearray, 以及最后的集合set。这些数据结构可以说Python最为基础的几种类型,想要用Python写出漂亮的代码离不开对他们的熟练掌握与深刻理解。这几个结构各有各的特…

    Python笔记 2018-03-31
  • 高阶函数

    高阶函数
    柯里化
    装饰器、文档字符串
    functools 模块 inspect 模块

    2018-04-25
  • 元组与字符串

    元组tuple 一个有序的元素组成的集合,不可变,用()表示,可进行索引,正索引:从左至右,从0开始;负索引:从右至左,从-1开始,正负索引不可超界,否则引发indexerror,tuple[index],index就是索引,使用中括号访问 元组是只读的,所以没有增,改,删的方法 冒泡法:属于交换排序,两两比较大小,交换位置,结果分为升序和降序排列 升序:n…

    Python笔记 2018-04-01
  • python安装失败原因分析(未指定错误0x80072efd)

    python安装时间很长,最终报错未指定错误0x80072efd   原因分析: download dubugging symbols download debug binaries 这两项需要联网(外网),国内安装会超时报错。所以安装时取消这两项就可以安装成功      

    2018-08-09
  • Python高阶函数及装饰器

    First Class Object 函数在Python中是一等公民 函数也是对象,可调用的对象 函数可作为普通变量、参数、返回值等 高阶函数 数学定义:y=g(f(x)) 高阶函数需满足的条件,至少其一 接受一个或多个函数作为参数 输出一个函数 内建函数的高阶函数 排序:sorted(iterable[,key][,reverse]) 返回一个新列表,对一…

    2018-04-22
  • 函数执行过程和递归函数练习题

    函数执行过程和递归函数练习题

    2018-04-16