树的遍历和排序

树的遍历和排序

python的树的遍历和堆排序:
二叉树的遍历:
遍历:迭代所有元素一遍
树的遍历:对树中所有元素不重复地访问一遍,也称作扫描

广度优先遍历:
层序遍历

深度优先遍历:
前序遍历
中序遍历
后序遍历

遍历序列:
将树中所有元素遍历一遍后,得到的元素的序列。将层次结构转换成了线性结构

层序遍历:
按照树的层次,从第一层开始,自左向右遍历元素

遍历序列:
ABCDEFGHI

二叉树的遍历:
深度优先遍历:
1、设树的根结点为D,左子树为L,右子树为R,且要求L一定在R之前,则有下面几种遍历方式

2、前序编列,也叫先序遍历,也叫先根遍历,DLR

3、中序遍历,也叫中根遍历,LDR

4、后序遍历,也叫后根遍历,LRD

前序遍历DLR:
1、从根结点开始,先左子树后右子树
2、每个子树内部依然是先根结点,再左子树后右子树,递归遍历
3、遍历序列:
A BDGH CEIF

中序遍历:LDR
1、从根结点的左子树开始遍历,然后是根结点,再右子树
2、每个子树内部,也是先左子树,后根结点,再右子树,递归遍历

遍历序列:
这个一定要分清楚是左子树还是右子树,因为中间遍历的时候会有差别

后序遍历LRD:
1、先左子树,后右子树,再根结点
2、每个子树内部依然是先左子树,后右子树,再根结点,递归遍历

遍历序列:GHDB IEFC

堆Heap:
1、堆是一个完全二叉树
2、每个非叶子结点都要大于或者等于其左右孩子结点的值称为大顶堆
3、每个非叶子结点都要小于或者等于其左右孩子结点的值称为小顶堆
4、根结点一定是大顶堆中的最大值,一定是小顶堆中的最小值

堆排序Heap Sort:
大顶堆:
1、完全二叉树的每个非叶子结点都要大于或者等于其左右孩子结点的值称为大顶堆
2、根结点一定是大顶堆中的最大值

小顶堆:
1、完全二叉树的每个非叶子结点都要小于或者等于其左右孩子结点的值称为小顶堆
2、根结点一定是小顶堆中的最小值

构建完全二叉树:
1、待排序数字为,30,20,80,40,50,10,60,70,90
2、构建一个完全二叉树存放数据,并根据性质5对元素编号,放入顺序的结构中
3、构建一个列表为[0,30,20,80,40,50,10,60,70,90]

构建大顶堆的核心算法:
1、度数为2的结点A,如果它的左右孩子结点的最大值比它大的,将这个最大值和该结点交换
2、度数为1的结点A,如果它的左孩子的值大于它,则交换
3、如果结点A被交换到新的位置,还需要和其孩子结点重复上面的过程

构建大顶堆–起点结点的选择:
1、完全二叉树的最后一个结点的双亲结点开始,即最后一层的最右边叶子结点的父结点开始

2、结点树为n,则起始结点的编号为n//2(性质5)

构建大顶堆–下一个结点的选择:
从起始结点开始向左找其同层结点,到头后再从上一层的最右边结点开始继续向左逐个查找,直至根结点

大顶堆的目标:
确保每个结点的都比左右(指的是孩子)结点的值大

排序:
1、将大顶堆根结点这个最大值和最后一个叶子结点交换,那么最后一个叶子结点就是最大值,将这个叶子结点排除在待排序结点之外
2、从根结点开始(新的根结点),重新调整为大顶堆后,重复上一步

总结:
1、是利用堆性质的一种选择排序,在堆顶选出最大值或者最小值
2、时间复杂度
堆排序的时间复杂度为O(nlogn)
由于堆排序对原始记录的排序状态并不敏感,因此无论是最好、最坏和平均时间复杂度均为O(nlogn)
空间复杂度:
只是使用了一个交换用的空间,空间复杂度就是O(1)

稳定性:
不稳定的排序算法

#思路,第一行取一个,第二行取2个,第三行取3个,以此类推,投影来思考一个栅格系统
#代码实现

 

import math

#居中对齐方案
def print_tree(array,unit_width=2):
length = len(array) #9
depth = math.ceil(math.log2(length + 1)) #4

 

index = 0
width = 2**depth – 1 #行宽15
for i in range(depth): # 0 1 2 3
for j in range(2**i): #0:0 1:0,1 2:0,1,2,3 3:0~7
#居中打印,后面追加一个空格
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(29)])

 

import math

 

#投影格实现
def print_tree(array):
”’
前空格 元素间
1 7 0
2 3 7
3 1 3
4 0 1

”’
index = 1
depth = math.ceil(math.log2(len(array))) #因为补0了,不然应该是math.ceil(math.log2(len(array)+1))
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([x +1 for x in range(100)])

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

(2)
上一篇 2017-10-23 16:23
下一篇 2017-10-24 09:13

相关推荐

  • 操作系统文件管理

      在现代计算机系统中,要用到大量的程序和数据,因内存容量有限,且不能长期保存,故而平时总是把它们以文件的形式存放在外存中,需要时再随时将它们调入内存。如果由用户直接管理外存上的文件,不仅要求用户熟悉外存特性,了解各种文件的属性,以及它们在外存上的位置,而且在多用户环境下,还必须能保持数据的安全性和一致性。显然,这是用户所不能胜任、也不愿…

    Linux干货 2015-04-13
  • 8.5文本处理工具及正则表达式

    一、各种文本工具     文件查看     命令:cat,tac,rev         cat optiong file       &n…

    Linux干货 2016-08-10
  • 运维工程师技能需求排行

    这是我今天在拉勾网搜索运维,翻完了4四页也招聘信息之后得到的,我的目的是想要看看之后的学习,哪个更应该成为重点,有些在我意料之中,有些还真的没想到,算是努力了一个小时的收获吧,分享给大家。
    注意:其中的看法仅代表个人观点,很多都是依靠我自己的学习经验和工作经验累积的

    Linux干货 2017-12-12
  • 推荐-MySQL存储日志并使用Loganalyzer作为前端展示

    MySQL存储日志并使用Loganalyzer作为前端展示 MySQL存储日志并使用Loganalyzer作为前端展示 为什么要使用日志 本文目标 实验拓扑图 实验环境 实验步骤 syslog主机上rsyslog设置 Server1主机上rsyslog设置 Web服务器配置 总结 为什么要使用日志 在生产环境中我们可能需要一个较为完整的日志系统来查看运行中主…

    Linux干货 2016-03-30
  • DNS高级应用

        DNS高级应用     1、主从复制      应用场景: (1)、当主DNS服务器压力过大,无法正常处理过多的DNS解析请求时,从DNS服务器可以起到负载均衡的作用。 (2)、当主DNS服务器出现故障时,从DNS服务器可以为其提供冗余备份功能。     实验环…

    Linux干货 2015-06-18
  • 马哥教育网络21期+第九周练习博客

    马哥教育网络21期+第九周练习博客 1、写一个脚本,判断当前系统上所有用户的shell是否为可登录shell(即用户的shell不是/sbin/nologin);分别这两类用户的个数;通过字符串比较来实现; [root@localhost bin]# cat 1.sh  #!/bin/bash # while&nbsp…

    Linux干货 2016-09-05