二叉树的遍历和堆排序

二叉树的遍历和堆排序

## 二叉树的遍历

### 广度优先遍历

层序遍历 上到下 左到右 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)
上一篇 2018-05-16 12:19
下一篇 2018-05-16 15:42

相关推荐

  • Python内置数据结构——列表

    知识框架图 学习笔记 数据结构分类 数值 int、float、complex、bool都是class int:长整型,没有上限,取决于内存区域大小 float:支持十进制和科学计数法,仅支持双精度 complex:复数,有实数和虚数部分 bool:int的子类,True、False对应1、0,可以和整数直接运算 序列对象 字符串str 列表list 元组tu…

    2018-03-26
  • functools模块,偏函数partial、缓存LRU

    functools模块,偏函数partial、缓存LRU

    2018-04-23
  • 第一周作业

    linux基础

    Python笔记 2018-05-12
  • 解析式

    列表解析式和字典解析式 datetime模块 对日期,时间,时间戳的处理 datetime类 today()返回本地时区当前的datetime对象 now(tz=None)返回当前时间的datetime对象,时间到微秒,如果tz为None,返回和today()一样 utcnow()没有时区的当前时间 fromtimestamp(timestamp,tz=Zo…

    2018-04-09
  • Python学习第十三周总结

    网络协议和管理、http服务和Apache

    2018-06-03
  • 函数与生成器

    函数 由若干语句组成的语句块,函数名,参数列表构成,是组织代码的最小单元,完成一定的功能,结构化编程对代码的最基本的封装,封装的目的是为了复用 函数中没有return,隐式会返回一个none值 定义中的参数列表成为形式参数,只是一种形式表达,简称形参 调用时写的参数是实际参数,是实实在在传入的值,简称实参 函数的定义,只是声明了参数,不会执行,可以进行调用,…

    2018-04-16