前言
继昨天的链表，今天又复习了一下二叉树，发现之前很熟练的东西，现在确实是很生疏了。看来知识真的是不学就忘啊。
方法声明
在开始介绍之前，依然先来罗列一下实现了哪些方法：
['getsize(self)']
['print(self)']
['qianxuDG(self, root)']
['zhongxuDG(self, root)']
['height(self, root)']
['deepth(self, root)']
['houxuDG(self, root)']
['xianxu(self)']
['zhongxu(self)']
['houxu(self)']
['width(self, root)']所用的匹配代码如下：
# coding: utf8
# @Author: 郭 璞
# @File: getmethods.py
# @Time: 2017/4/5
# @Contact: 1064319632@qq.com
# @blog: http://blog.csdn.net/marksinoberg
# @Description: 获取一个模块或者类中的所有方法及参数列表
import re
def parse(filepath, repattern):
with open(filepath, 'rb') as f:
lines = f.readlines()
# 预解析正则
rep = re.compile(repattern)
# 创建保存方法和参数列表的结果集列表
result = []
# 开始正式的匹配实现
for line in lines:
res = re.findall(rep, str(line))
print("{}的匹配结果{}".format(str(line), res))
if len(res)!=0 or res is not None:
result.append(res)
else:
continue
return [item for item in result if item !=[]]
if __name__ == '__main__':
repattern = "def (.[^_0-9]+\(.*?\)):"
filepath = './TwoBranchTree.py'
result = parse(filepath, repattern)
for item in result:
print(str(item))
二叉树相关
因为思路都比较简单，所以下面就直接贴出代码了。该做注释的地方已经注释过了。
# coding: utf8
# @Author: 郭 璞
# @File: TwoBranchTree.py
# @Time: 2017/4/6
# @Contact: 1064319632@qq.com
# @blog: http://blog.csdn.net/marksinoberg
# @Description: 二叉树相关所有内容
# 创建二叉树节点
class Node(object):
def __init__(self, data, left, right):
self.data = data
self.left = None
self.right = None
# 创建二叉树
class Tree(object):
# 创建一棵树，默认会有一个根节点
def __init__(self, data):
self.root = Node(data, None, None)
self.size = 1
##########################################################为了计算二叉树的宽度而用
# 存放各层节点数目
self.n = []
# 初始化层，否则列表访问无效
for item in range(pow(2, 5)):
self.n.append(0)
# 索引标识
self.maxwidth = 0
self.i = 0
# 求二叉树包含的节点数目
def getsize(self):
stack = [self.root]
# 为了正确获取数目，这里需要先初始化一下
self.size = 0
while stack:
temp = stack.pop(0)
self.size += 1
if temp.left:
stack.append(temp.left)
if temp.right:
stack.append(temp.right)
return self.size
# 默认以层次遍历打印出该二叉树
def print(self):
stack = [self.root]
while stack:
temp = stack.pop(0)
print(str(temp.data)+"\t", end='\t')
if temp.left:
stack.append(temp.left)
if temp.right:
stack.append(temp.right)
# 递归实现前序遍历
def qianxuDG(self, root):
if root:
print(root.data)
self.qianxuDG(root.left)
self.qianxuDG(root.right)
# 递归实现中序遍历
def zhongxuDG(self, root):
if root:
self.zhongxuDG(root.left)
print(root.data)
self.zhongxuDG(root.right)
# 求得二叉树的最大高度
def height(self, root):
if not root:
return 0
ldeepth = self.height(root.left)
rdeepth = self.height(root.right)
return max(ldeepth+1, rdeepth+1)
# 求得二叉树的最大深度
def deepth(self, root):
return self.height(root)-1
# 递归实现后序遍历
def houxuDG(self, root):
if root:
self.houxuDG(root.left)
self.houxuDG(root.right)
print(root.data)
# 二叉树的先序遍历非递归实现
def xianxu(self):
"""
进栈向左走， 如果当前节点有右子树， 则先把右子树入栈，再把左子树入栈。来实现先根遍历效果
:return:
"""
if self.root is None:
return
else:
stack = [self.root]
while stack:
current = stack.pop()
print(current.data)
if current.right:
stack.append(current.right)
if current.left:
stack.append(current.left)
# 二叉树的中序非递归实现
def zhongxu(self):
if self.root is None:
return
else:
# stack = [self.root]
# current = stack[-1]
stack = []
current = self.root
while len(stack)!=0 or current:
if current:
stack.append(current)
current = current.left
else:
temp = stack.pop()
print(temp.data)
current = temp.right
# 二叉树的后序非递归实现
def houxu(self):
if self.root is None:
return
else:
stack1 = []
stack2 = []
stack1.append(self.root)
# 对每一个头结点进行判断，先将该头结点放到栈2中，如果该节点有左子树则放入栈1， 有右子树也放到栈1
while stack1:
current = stack1.pop()
stack2.append(current)
if current.left:
stack1.append(current.left)
if current.right:
stack1.append(current.right)
# 直接遍历输出stack2即可
while stack2:
print(stack2.pop().data)
# 求一颗二叉树的最大宽度
def width(self, root):
if root is None:
return
else:
# 如果是访问根节点
if self.i == 0:
# 第一层加一
self.n[0] =1
# 到达第二层
self.i += 1
if root.left:
self.n[self.i] += 1
if root.right:
self.n[self.i] += 1
# print('临时数据：', self.n)
else:
# 访问子树
self.i += 1
# print('二叉树所在层数：', self.i)
if root.left:
self.n[self.i] += 1
if root.right:
self.n[self.i] += 1
# 开始判断, 取出最大值
# maxwidth = max(maxwidth, n[i])
# maxwidth.append(max(max(maxwidth), n[i]))
self.maxwidth= max(self.maxwidth, self.n[self.i])
# 遍历左子树
self.width(root.left)
# 往上退一层
self.i -= 1
# 遍历右子树
self.width(root.right)
return self.maxwidth
if __name__ == '__main__':
# 手动创建一课二叉树
print('手动创建一课二叉树')
tree = Tree(1)
tree.root.left = Node(2, None, None)
tree.root.right = Node(3, None, None)
tree.root.left.left = Node(4, None, None)
tree.root.left.right = Node(5, None, None)
tree.root.right.left = Node(6, None, None)
tree.root.right.right = Node(7, None, None)
tree.root.left.left.left = Node(8, None, None)
tree.root.left.left.right = Node(9, None, None)
tree.root.left.right.left = Node(10, None, None)
tree.root.left.right.left = Node(11, None, None)
# 测试一下是否创建成功
print('测试一下是否创建成功')
print(tree.root.data)
print(tree.root.left.data)
print(tree.root.right.data)
print(tree.root.left.left.data)
print(tree.root.left.right.data)
# 调用方法打印一下效果：以层次遍历实现
print('调用方法打印一下效果：以层次遍历实现')
tree.print()
print('前序遍历递归实现')
# 前序遍历递归实现
tree.qianxuDG(tree.root)
# 中序遍历递归实现
print('中序遍历递归实现')
tree.zhongxuDG(tree.root)
# 后序遍历递归实现
print('后序遍历递归实现')
tree.houxuDG(tree.root)
# 求取二叉树的高度
print('求取二叉树的高度')
print(tree.height(tree.root))
# 求取二叉树的深度
print('求取二叉树的深度')
print(tree.deepth(tree.root))
# 二叉树的非递归先序遍历实现
print('二叉树的非递归先序遍历实现')
tree.xianxu()
print('中序非递归遍历测试')
tree.zhongxu()
print('后序非递归遍历测试')
tree.houxu()
print('二叉树的最大宽度为： {}'.format(tree.width(tree.root)))
print('二叉树的节点数目为： {}'.format(tree.getsize()))运行的效果如下：
D:\Software\Python3\python.exe E:/Code/Python/Python3/CommonTest/datastructor/TwoBranchTree.py
手动创建一课二叉树
测试一下是否创建成功
1
2
3
4
5
调用方法打印一下效果：以层次遍历实现
1 2 3 4 5 6 7 8 9 11 前序遍历递归实现
1
2
4
8
9
5
11
3
6
7
中序遍历递归实现
8
4
9
2
11
5
1
6
3
7
后序遍历递归实现
8
9
4
11
5
2
6
7
3
1
求取二叉树的高度
4
求取二叉树的深度
3
二叉树的非递归先序遍历实现
1
2
4
8
9
5
11
3
6
7
中序非递归遍历测试
8
4
9
2
11
5
1
6
3
7
后序非递归遍历测试
8
9
4
11
5
2
6
7
3
1
二叉树的最大宽度为： 4
二叉树的节点数目为： 10
Process finished with exit code 0
霍夫曼树实现
原理
霍夫曼在编码上有很大的用途，虽然还需要很多地方的改进。其目标就是尽可能使用最少的编码集来最大限度的进行编码，以此来节省空间。
算法也很简单，我们不妨先看一个小例子。
有这么一个序列 1，2，3，4，5。现在要用它来实现霍夫曼
-----------------------------------------------------------
/**
* 武功秘籍： 先对序列进行排序，然后永远找到序列中最小的两个值，然后在序列中去掉这俩。加和之后放到原来的序列中，再次进行排序。进行下一次循环的执行，直到序列中只剩下一个元素就可以停止了。
**/
-----------------------------------------------------------
所以第一次要找到两个最小的元素：1， 2。
此时序列内容为3，4，5
对1，2求和之后得到结果3，然后把这个3放到原来的序列中，此时序列变成了3，3，4，5
-----------------------------------------------------------
第二次：还是找最小的俩元素：3，3
求和得到6，放到原序列中，变成了4,5,6
-----------------------------------------------------------
第三次： 找最小4，5
求和得9，放到原序列：6，9
-----------------------------------------------------------
第四次：最小6，9
求和得到15，放到原序列15
-----------------------------------------------------------
第五次： 序列长度为1，不满足运算条件，执行完毕。
所以最终可以得到如下的一颗二叉树：
15
/ \
9 6
/ \ / \
4 5 3 3
/ \
1 2代码实现一
以面向对象的方式实现：
class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = None
self.right = None
class Huffman(object):
def __init__(self, items=[]):
while len(items)!=1:
a, b = items[0], items[1]
newvalue = a.value + b.value
newnode = Node(value=newvalue)
newnode.left, newnode.right = a, b
items.remove(a)
items.remove(b)
items.append(newnode)
items = sorted(items, key=lambda node: int(node.value))
# 每次都要记得更新新的霍夫曼树的根节点
self.root = newnode
def print(self):
queue = [self.root]
while queue:
current = queue.pop(0)
print(current.value, end='\t')
if(current.left):
queue.append(current.left)
if current.right:
queue.append(current.right)
print()实现方式2
以面向过程的方式实现：
def sortlists(lists):
return sorted(lists, key=lambda node: int(node.value))
def create_huffman_tree(lists):
while len(lists)>1:
a, b = lists[0], lists[1]
node = Node(value=int(a.value+b.value))
node.left, node.right = a, b
lists.remove(a)
lists.remove(b)
lists.append(node)
lists = sorted(lists, key=lambda node: node.value)
return lists
def scan(root):
if root:
queue = [root]
while queue:
current = queue.pop(0)
print(current.value, end='\t')
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
最终效果
if __name__ == '__main__':
ls = [Node(i) for i in range(1, 5)]
huffman = Huffman(items=ls)
huffman.print()
print('===================================, ')
lssl = [Node(i) for i in range(1, 5)]
root = create_huffman_tree(lssl)[0]
scan(root)运行结果：
D:\Software\Python3\python.exe E:/Code/Python/Python3/CommonTest/datastructor/霍夫曼树创建.py
10 4 6 3 3 1 2
===================================, 下面的方式不正确的原因是ls已经被上面代码修改过了，需要重新设置一下！
10 4 6 3 3 1 2
Process finished with exit code 0总结
“好记性，不如烂笔头”。与君共勉。