10.1二叉树
10.1.1为什么需要树这种数据结构
1)数组存储方式的分析：
优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低
示意图：
2)链式存储方式的分析
优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好)。
缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)
示意图：
3)树存储方式的分析
树存储能提高数据存储，读取的效率,比如利用二叉排序树(BinarySortTree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。
示意图：
树的常用术语(结合示意图理解):
1)节点
2)根节点
3)父节点
4)子节点
5)叶子节点(没有子节点的节点)
6)节点的权(节点值)
7)路径(从root节点找到该节点的路线)
8)层
9)子树
10)树的高度(最大层数)
11)森林:多颗子树构成森林
10.1.2二叉树的概念
1)树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
2)二叉树的子节点分为左节点和右节点
3)示意图：
4)如果该二叉树的所有叶子节点都在最后一层，并且结点总数=2^n-1,n为层数，则我们称为满二叉树。
5)如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树
10.1.3二叉树遍历的说明
1)前序遍历:先输出父节点，再遍历左子树和右子树
2)中序遍历:先遍历左子树，再输出父节点，再遍历右子树
3)后序遍历:先遍历左子树，再遍历右子树，最后输出父节点
10.1.4二叉树遍历应用实例(前序,中序,后序)
应用实例的说明和思路：
10.1.5二叉树-查找指定节点
要求:
1)请编写前序查找，中序查找和后序查找的方法。
2)并分别使用三种查找方式，查找heroNO=5的节点
3)并分析各种查找方式，分别比较了多少次
4)示意图：
10.1.6二叉树-删除节点
要求（规定）：
1)如果删除的节点是叶子节点，则删除该节点
2)如果删除的节点是非叶子节点，则删除该子树.
3)示意图：
10.1.5二叉树的遍历、查找、删除节点的所有代码：
class HeroNode():
def __init__(self,id,name):
self.id = id
self.name = name
self.left = None
self.right = None
def preOrder(self):
#先输出父结点
print(self.id,self.name)
#递归向左子树前序遍历
if self.left != None:
self.left.preOrder()
#递归向右子树前序遍历
if self.right != None:
self.right.preOrder()
def infixOrder(self):
if self.left != None:
self.left.infixOrder()
print(self.id,self.name)
if self.right != None:
self.right.infixOrder()
def postOrder(self):
if self.left != None:
self.left.postOrder()
if self.right != None:
self.right.postOrder()
print(self.id,self.name)
def preOrderSearched(self,id):
# 1.先判断当前结点的no是否等于要查找的
# 2.如果是相等，则返回当前结点
if self.id == id:
return self
print("compare",self.id)
# 3.如果不等，则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找，
# 这里创建一个对象用来接收查找的返回值
self.heronode = HeroNode(None,None)
if self.left != None:
print("left")
self.heronode = self.left.preOrderSearched(id)
# 4.如果左递归前序查找，找到结点，则返回这个对象，注意这里不能直接返回self，因为self是只当前节点，而不是self.heronode这个对象
if self.heronode.id != None:
return self.heronode
# 5.否->继续判断，当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找.
if self.right != None:
print("right")
self.heronode = self.right.preOrderSearched(id)
# 6.不管向右递归前序查找有没有找到直接返回self.heronode对象即可。
return self.heronode
def infixOrderSearched(self,id):
self.heronode = HeroNode(None,None)
if self.left != None:
print("left")
self.heronode = self.left.infixOrderSearched(id)
if self.heronode.id != None:
return self.heronode
if self.id == id:
return self
print("compare",self.id)
if self.right != None:
print("right")
self.heronode = self.right.infixOrderSearched(id)
return self.heronode
def postOrderSearched(self,id):
self.heronode = HeroNode(None,None)
if self.left != None:
print("left")
self.heronode = self.left.postOrderSearched(id)
if self.heronode.id != None:
return self.heronode
if self.right != None:
print("right")
self.heronode = self.right.postOrderSearched(id)
if self.heronode.id != None:
return self.heronode
if self.id == id:
return self
print("compare",self.id)
return self.heronode
def perdelete(self,id):
#说明：
#1.本删除方法，是按照前序查找的形式进行查找删除的
#2.规定
# //1.如果删除的节点是叶子节点，则删除该节点
# //2.如果删除的节点是非叶子节点，则删除该子树
#实现过程：
#1.因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.因此用self.left self.right
#2.如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.left=null;并且就返回(结束递归删除)
if self.left != None and self.left.id == id:
self.left = None
return
#3.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null;并且就返回(结束递归删除)
if self.right != None and self.right.id == id:
self.right = None
return
#4.如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
if self.left != None:
self.left.perdelete(id)
#5.如果第4步也没有删除结点，则应当向右子树进行递归删除.
if self.right != None:
self.right.perdelete(id)
return
class BinaryTree():
def __init__(self,id,name):
self.id = id
self.name = name
self.headnode = HeroNode(self.id,self.name)
def infixOrder(self):
if self.headnode != None:
self.headnode.infixOrder()
else:
print("None")
def postOrder(self):
if self.headnode != None:
self.headnode.postOrder()
else:
print("None")
def preOrder(self):
if self.headnode != None:
self.headnode.preOrder()
else:
print("None")
def preOrderSearched(self,id):
self.id = id
if self.headnode != None:
return self.headnode.preOrderSearched(id)
else:
return None
def infixOrderSearched(self,id):
self.id = id
if self.headnode != None:
return self.headnode.infixOrderSearched(id)
else:
return None
def postOrderSearched(self,id):
self.id = id
if self.headnode != None:
return self.headnode.postOrderSearched(id)
else:
return None
def perdelete(self,id):
#在这里先对root结点进行判断，若是则置空，不是再调用root结点的perdelete方法
self.id = id
if self.headnode != None and self.headnode.id == id:
self.headnode = None
return
self.headnode.perdelete(self.id)
#这里手动创建二叉树并做出相应连接、后续会写代码按照一定规则的形式来创建二叉树
binary = BinaryTree(0,'q')
node1 = HeroNode(1,'w')
node2 = HeroNode(2,'e')
node3 = HeroNode(3,'r')
node4 = HeroNode(4,'t')
node5 = HeroNode(5,'y')
node6 = HeroNode(6,'u')
node7 = HeroNode(7,'I')
binary.headnode.left = node1
binary.headnode.right = node2
node2.left = node3
node2.right = node4
node3.left = node5
node3.right = node6
node4.right = node7
#前序中序后序遍历
binary.preOrder()
binary.infixOrder()
binary.postOrder()
#前序中序后序查找
# persearch = binary.preOrderSearched(6)
# if persearch != None:
# print(persearch.id, persearch.name)
# print("--------------------------------")
# persearch = binary.infixOrderSearched(6)
# if persearch != None:
# print(persearch.id, persearch.name)
# print("--------------------------------")
# persearch = binary.postOrderSearched(6)
# if persearch != None:
# print(persearch.id, persearch.name)
#删除
binary.preOrder()
print("--------------------------------")
binary.perdelete(7)
binary.preOrder()
10.2顺序存储二叉树
10.2.1顺序存储二叉树的概念
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，示意图：
要求:
1)如二叉树的7个节点，要求以数组的方式来存放arr:[1,2,3,4,5,6,6]
2)在遍历数组arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历
顺序存储二叉树的特点:
1)顺序二叉树通常只考虑完全二叉树
温习概念：
完全二叉树示意图
2)第n个元素的左子节点为2n+1
3)第n个元素的右子节点为2n+2
4)第n个元素的父节点为(n-1)/2
5)n:表示二叉树中的第几个元素(从0开始编号如图所示)
10.2.2顺序存储二叉树遍历
需求:
给你一个数组{1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。前序遍历的结果应当为1,2,4,5,3,6,7
代码实现:
class ArrayBinaryTree():
def __init__(self,array):
self.array = array
self.length = len(self.array)
def perOrder(self,index):
if self.length == 0:
return
print(self.array[index])
if 2*index+1<self.length:
self.perOrder(2*index+1)
if 2*index+2<self.length:
self.perOrder(2*index+2)
a = [1,2,3,4,5,6,7]
A = ArrayBinaryTree(a)
A.perOrder(0)
10.3线索化二叉树
10.3.1 问题提出：
将数列{1,3,6,8,10,14}构建成一颗二叉树，如图所示：
问题分析:
1)当我们对上面的二叉树进行中序遍历时，数列为{8,3,10,1,6,14}
2)但是6,8,10,14这几个节点的左右指针，并没有完全的利用上.
3)如果我们希望充分的利用各个节点的左右指针，让各个节点可以指向自己的前后节点,怎么办?
4)解决方案-线索二叉树
10.3.2线索二叉树基本介绍
1)n个结点的二叉链表中含有n+1【公式2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
2)这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(ThreadedBinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
3)一个结点的前一个结点，称为前驱结点
4)一个结点的后一个结点，称为后继结点
10.3.3线索二叉树应用案例
说明：将下面的二叉树，进行中序线索二叉树。中序遍历的数列为{8,3,10,1,14,6}
思路分析:中序遍历的结果：{8,3,10,1,14,6}
说明:
一、中序线索化二叉树如上图所示：
首先第一个叶子结点无前驱结点，最后一个叶子结点无后继结点，
其次如值为10的结点，则其前驱结点值为3，后继结点值为1，如图红线所示
二、当线索化二叉树后，Node节点的属性left和right，有如下情况:
1)left指向的是左子树，也可能是指向的前驱节点.
比如①节点left指向的左子树,而⑩节点的left指向的就是前驱节点.
2)right指向的是右子树，也可能是指向后继节点.
比如①节点right指向的是右子树，而⑩节点的right指向的是后继节点.
10.3.4遍历线索化二叉树
1)说明：对前面的中序线索化的二叉树，进行遍历
2)分析：因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致。
代码实现
class HeroNode():
def __init__(self,id,name):
self.id = id
self.name = name
self.left = None
self.right = None
self.lefttype = 0
self.righttype = 0
class BinaryTree():
def __init__(self):
self.pre = HeroNode(None,None)
self.pre.right = None
def threaded(self,node):
#这一个程序还算好写的，但是有两个地方困扰了我一天，我已经差点要放弃了，已经在简书里用别人的代码，写着我遇到了xxx的问题，想找人帮忙解决
#可是我写着写着的时候，突然想到，嗯？为什么会有这个错误？为什么（我在线索化最左边叶子结点的left结点的时候由于为空所以应该返回到最左边的叶子结点， 可以是我return后，叶子结点丢了，当前结点变为空了）
#然后我就在想return空的原因，那不就是因为我self.node = node 我在self.threaded(node.left) 这里调用的时候，此时的node.left为None，当然你再
#self.node = node，它也就为空了，那么解决办法就是不要这句代码。
# self.node = node
#node: 就是当前需要线索化的结点
if node == None:
return
# 先线索化左子树
self.threaded(node.left)
# 线索化当前结点
# 处理当前结点的前驱结点
if node.left == None:
node.left = self.pre
node.lefttype = 1
# 处理当前结点的后继结点
if self.pre.id != None and self.pre.right == None:
self.pre.right = node
self.pre.righttype = 1
#第二个错误是下面这句代码。所以导致了我整个程序一直有bug，这个问题修复是看别人的代码，才修复好的，惭愧
#node.pre = node
self.pre = node
# 线索化右子树
self.threaded(node.right)
# 中序遍历线索化二叉树
def threaded_in_order(self, node):
#用一个循环去判断，其实这里能获得的node== None: 的话只有两种情况。一种是node3.left 一种是node6.right, 这里很巧妙
#第二个None用于找到结束位置也就是node6
while node != None:
#这里用lefttype ==0: 找到第一个 lefttype ==1 的结点也就是3作为开始结点,并且这个可以找到每个小分支最左边结点这个很重要！要不然有的结点就漏了
while node.lefttype ==0:
node = node.left
#其实从这里开始就是不断的输出当前结点，并 node = node.right 但是不能直接这么两句话写了，不然会造成死循环，因为当运行到最后一句代前
#正常此时 的 node.righttype以及node.lefttype 都为0 因此加上最后一句代码，起了顺水推舟的作用，这样就跳开了上面的while循环
print(node.id)
while(node.righttype == 1):
node = node.right
print(node.id)
node = node.right
#这里手动创建二叉树并做出相应连接、后续会写代码按照一定规则的形式来创建二叉树
node0 = HeroNode(0,'q')
node1 = HeroNode(1,'w')
node2 = HeroNode(2,'e')
node3 = HeroNode(3,'r')
node4 = HeroNode(4,'t')
node5 = HeroNode(5,'y')
node6 = HeroNode(6,'u')
node7 = HeroNode(7,'I')
binary = BinaryTree()
node0.left = node1
node0.right = node2
node1.left = node3
node1.right = node4
node2.left = node5
node2.right = node6
binary.threaded(node0)
binary.threaded_in_order(node0)
10.4树结构的实际应用
11.1 堆排序
详见：
https://www.jianshu.com/p/ff61c524f5cf
11.2 赫夫曼树
11.2.1基本介绍
1)给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(HuffmanTree),还有的书翻译为霍夫曼树。
2)赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近
11.2.2赫夫曼树几个重要概念和举例说明
1)路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1
2)结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积
3)树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weightedpathlength),权值越大的结点离根结点越近的二叉树才是最优二叉树。
4)WPL最小的就是霍夫曼树
霍夫曼树
11.2.3霍夫曼树创建思路
首先，我们给定任一字符串如“Hello world，i love python”
然后会生成这样一些数据：
sourceData = [('H', 1), ('e', 2), ('l', 4), ('o', 4), (' ', 3), ('w', 1), ('r', 1), ('d', 1), ('，', 1), ('i', 1), ('v', 1), ('p', 1), ('y', 1), ('t', 1), ('h', 1), ('n', 1)]
每一个数据项是一个元组，元组的第一项是数据内容，第二项是该数据的权重。也就是说，用于构建霍夫曼树的数据是带权重的。假设这些数据里面的字母a-f的权重是根据这些字母在一个文本出出现的概率计算得出的，字母出现的概率越高，则该字母的权重越大。例如字母 a 的权重为 8 .
拿到数据我们就可以来构建霍夫曼树了。
1)找出所有元素中权重最小的两个元素，即g(2)和c(3)，
2)以g和c为子节点构建二叉树，则构建的二叉树的父节点的权重为 2+3 = 5.
3)从除g和c以外剩下的元素和新构建的权重为5的节点中选出权重最小的两个节点，
4)进行第 2 步操作。
以此类推，直至最后合成一个二叉树就是霍夫曼树。
11.2.4代码实现
代码参考：https://www.cnblogs.com/dongyangblog/p/11228930.html
class Node ():
def __init__(self,data,value):
self.value = value
self.data = data
self.left = None
self.right = None
# 定义获取列表中权重最大的两个节点的方法：
#1.定义 result 列表 带有两个value为正无穷的 Node 对象
#2.将权重最小的两个结点放入 result 中
#3.将其他结点扔到list2中，包括从result淘汰的结点
def getmin2(list):
result = [Node (None,float('inf')), Node (None,float('inf'))]
list2 = []
for i in range(len(list)):
if list[i].value < result[0].value:
if result[1].value != float('inf'):
list2.append(result[1])
result[0] , result[1] = list[i] , result[0]
elif list[i].value < result[1].value:
if result[1].value != float('inf'):
list2.append(result[1])
result[1] = list[i]
else:
list2.append(list[i])
# for i in range(len(result)):
# print("result",result[i].value)
# for i in range(len(list2)):
# print("list2",list2[i].value)
return result , list2
#定义生成哈夫曼树的方法：
#1.调用getmin2方法 获得 min2，分别为left、right结点，data 为剩下的结点
#2.创建一个father结点，并将left、right分别赋给 father.left father.right
#3.如果data里空了 说明没有剩余结点了 就可以返回 father了就是哈夫曼树
#4.如果data不是空的，那么就还得继续构造father结点， 并且记得把father结点扔到 data里面
#5.递归调用makeHuffman函数，也就继续调用getmin2函数，继续获得最小权重的两个结点
def makeHuffman(list):
min2, data = getmin2(list)
left = min2[0]
right = min2[1]
value = left.value + right.value
father = Node(None, value)
father.left = left
father.right = right
if data == []:
return father
data.append(father)
return makeHuffman(data)
# 递归方式实现广度优先遍历
#1.先将Node对象的list转为列表,只是把类型改了，list 的属性都还在
#2.将值一个一个扔到result里面，先扔根结点，
# 3.然后判断当前跟结点有没有左右子结点，有的话将根结点的左子结点，右子结点分别扔到nextlist里去
#4.没有的话判断当前根结点是是其父结点的右子结点吗，若是则判断nextlist是否为空，
# 4.1 若为空说明以当前结点为根结点的树遍历完了（没有叶子结点），可以返回了
# 4.2 若不为空，说明还没有遍历完，调整下参数以便继续遍历
#5.若不是右子结点，则将index + 1 使当前指向右子结点继续遍历
#6 全遍历完，返回result
def traverse(list,index= 0 ,nextlist = [] ,result = []):
if type(list) == Node:
list = [list]
result.append((list[index].data,list[index].value))
if list[index].left != None:
nextlist.append((list[index].left))
if list[index].right != None:
nextlist.append((list[index].right))
if index == len(list)-1:
if nextlist == []:
return
else:
list = nextlist
nextlist = []
index = 0
else:
index +=1
traverse(list,index,nextlist,result)
return result
# 直接用前序遍历将其输出
# def traverse(list):
# # if type(list) == Node:
# # list = [list]
# print(list.data,list.value)
# if list.left != None:
# traverse(list.left)
# if list.right != None:
# traverse(list.right)
#文章中部分字母根据出现的概率规定权重，并让其生成Node对象
#将字符串转为携带自身字符及次数（权重）组成的元组的列表，再实例化Node对象
str = "Hello world，i love python"
#统计字符串出现字符的次数，并与字符组成字典
sourceData = {x:str.count(x) for x in str }
print("1",sourceData)
#sourceData.items() ： 以列表形式返回可遍历的(键, 值) 元组数组。
#sourceData = sourceData.items() 也可以
sourceData = [(key,val) for key,val in sourceData.items()]
print("2",sourceData)
#将每个元组中的第0个元素与第一个元素作为参数实例化Node对象
sourceData = [Node(x[0], x[1]) for x in sourceData]
print("3",sourceData)
huffman = makeHuffman(sourceData)
# print(huffman.value)
# print(huffman.left.value)
# print(huffman.right.value)
# # print(huffman.left.left.value)
# # print(huffman.left.right.value)
# print(huffman.right.right.value)
# print(huffman.right.left.value)
huff = traverse(huffman)
print(huff)
