python数据结构之二叉树的统计与转换实例
发布时间:2023-08-11 07:35:48
标签:python,数据结构,二叉树,统计,转换
一、获取二叉树的深度
就是二叉树最后的层次,如下图:
实现代码:
def getheight(self):
''' 获取二叉树深度 '''
return self.__get_tree_height(self.root)
def __get_tree_height(self, root):
if root is 0:
return 0
if root.left is 0 and root.right is 0:
return 1
else:
left = self.__get_tree_height(root.left)
right = self.__get_tree_height(root.right)
if left < right:
return right + 1
else:
return left + 1
二、叶子的统计
叶子就是二叉树的节点的 left 指针和 right 指针分别指向空的节点
def getleafcount(self):
''' 获取二叉树叶子数 '''
return self.__count_leaf_node(self.root)
def __count_leaf_node(self, root):
res = 0
if root is 0:
return res
if root.left is 0 and root.right is 0:
res += 1
return res
if root.left is not 0:
res += self.__count_leaf_node(root.left)
if root.right is not 0:
res += self.__count_leaf_node(root.right)
return res
三、统计叶子的分支节点
与叶子节点相对的其他节点 left 和 right 的指针指向其他节点
def getbranchcount(self):
''' 获取二叉树分支节点数 '''
return self.__get_branch_node(self.root)
def __get_branch_node(self, root):
if root is 0:
return 0
if root.left is 0 and root.right is 0:
return 0
else:
return 1 + self.__get_branch_node(root.left) + self.__get_branch_node(root.right)
四、二叉树左右树互换
def replacelem(self):
''' 二叉树所有结点的左右子树相互交换 '''
self.__replace_element(self.root)
def __replace_element(self, root):
if root is 0:
return
root.left, root.right = root.right, root.left
self.__replace_element(root.left)
self.__replace_element(root.right)
这些方法和操作,都是运用递归。其实二叉树的定义也是一种递归。附上最后的完整代码:
# -*- coding: utf - 8 - *-
class TreeNode(object):
def __init__(self, left=0, right=0, data=0):
self.left = left
self.right = right
self.data = data
class BinaryTree(object):
def __init__(self, root=0):
self.root = root
def is_empty(self):
if self.root is 0:
return True
else:
return False
def create(self):
temp = input('enter a value:')
if temp is '#':
return 0
treenode = TreeNode(data=temp)
if self.root is 0:
self.root = treenode
treenode.left = self.create()
treenode.right = self.create()
def preorder(self, treenode):
'前序(pre-order,NLR)遍历'
if treenode is 0:
return
print treenode.data
self.preorder(treenode.left)
self.preorder(treenode.right)
def inorder(self, treenode):
'中序(in-order,LNR'
if treenode is 0:
return
self.inorder(treenode.left)
print treenode.data
self.inorder(treenode.right)
def postorder(self, treenode):
'后序(post-order,LRN)遍历'
if treenode is 0:
return
self.postorder(treenode.left)
self.postorder(treenode.right)
print treenode.data
def preorders(self, treenode):
'前序(pre-order,NLR)非递归遍历'
stack = []
while treenode or stack:
if treenode is not 0:
print treenode.data
stack.append(treenode)
treenode = treenode.left
else:
treenode = stack.pop()
treenode = treenode.right
def inorders(self, treenode):
'中序(in-order,LNR) 非递归遍历'
stack = []
while treenode or stack:
if treenode:
stack.append(treenode)
treenode = treenode.left
else:
treenode = stack.pop()
print treenode.data
treenode = treenode.right
def postorders(self, treenode):
'后序(post-order,LRN)非递归遍历'
stack = []
pre = 0
while treenode or stack:
if treenode:
stack.append(treenode)
treenode = treenode.left
elif stack[-1].right != pre:
treenode = stack[-1].right
pre = 0
else:
pre = stack.pop()
print pre.data
# def postorders(self, treenode):
# '后序(post-order,LRN)非递归遍历'
# stack = []
# queue = []
# queue.append(treenode)
# while queue:
# treenode = queue.pop()
# if treenode.left:
# queue.append(treenode.left)
# if treenode.right:
# queue.append(treenode.right)
# stack.append(treenode)
# while stack:
# print stack.pop().data
def levelorders(self, treenode):
'层序(post-order,LRN)非递归遍历'
from collections import deque
if not treenode:
return
q = deque([treenode])
while q:
treenode = q.popleft()
print treenode.data
if treenode.left:
q.append(treenode.left)
if treenode.right:
q.append(treenode.right)
def getheight(self):
''' 获取二叉树深度 '''
return self.__get_tree_height(self.root)
def __get_tree_height(self, root):
if root is 0:
return 0
if root.left is 0 and root.right is 0:
return 1
else:
left = self.__get_tree_height(root.left)
right = self.__get_tree_height(root.right)
if left < right:
return right + 1
else:
return left + 1
def getleafcount(self):
''' 获取二叉树叶子数 '''
return self.__count_leaf_node(self.root)
def __count_leaf_node(self, root):
res = 0
if root is 0:
return res
if root.left is 0 and root.right is 0:
res += 1
return res
if root.left is not 0:
res += self.__count_leaf_node(root.left)
if root.right is not 0:
res += self.__count_leaf_node(root.right)
return res
def getbranchcount(self):
''' 获取二叉树分支节点数 '''
return self.__get_branch_node(self.root)
def __get_branch_node(self, root):
if root is 0:
return 0
if root.left is 0 and root.right is 0:
return 0
else:
return 1 + self.__get_branch_node(root.left) + self.__get_branch_node(root.right)
def replacelem(self):
''' 二叉树所有结点的左右子树相互交换 '''
self.__replace_element(self.root)
def __replace_element(self, root):
if root is 0:
return
root.left, root.right = root.right, root.left
self.__replace_element(root.left)
self.__replace_element(root.right)
node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 'root')
bt = BinaryTree(root)
print u'''
生成的二叉树
------------------------
root
7 8
6
2 5
1 3 4
-------------------------
'''
0
投稿
猜你喜欢
- 可以在Mac OS X 10.2.x(“Jaguar”)和以上版本上Mac OS X使用二进制安装软
- 大家平时见到google的广告太多了,但有没有兴趣知道一下它的运行过程呢?下面我们一起来看看这个广告代码的执行过程,以及其中的一些精彩内容。
- 注:IE8以前的版本均不支持该特性为了向文档中插入生成内容,可以使用:before与:after伪元素。如,我想在所有链接的后面加上&quo
- 本文实例讲述了Python开发的实用计算器。分享给大家供大家参考,具体如下:实现功能:图形界面PyQt,输入框,+,—,*,/ ;乘方 ,开
- 本文介绍了在js和asp中使用FileSystemObject(fso)来: 创建、添加或删除数据,以及读取文件; 移动、复制和删除文件;创
- 工厂模式(Factory Pattern)是什么工厂模式是一种创建型模式,它提供了一种创建对象的最佳方式。在工厂模式中,我们在创建对象时不会
- 在上一篇博客中,已经将环境搭建好了。现在,我们利用搭建的环境来运行一条测试脚本,脚本中启动一个计算器的应用,并实现加法的运算。创建模拟器在运
- 双屏不是什么新鲜事,不过相信国内前端工程师还是用单屏的多,前端开发需要同时开启的屏幕太多了…你有没有迷失windows任务栏下n个窗口和AL
- 从BbsXp提出来的生肖函数Zodiac(birthday)。使用方法:birthday为把要判断的出生时间,如2008-3-24 20:0
- 有一编文章是用JavaScript对XML文件操作来实现无限级联动菜单的,我们可结合ASP来完成对数据库值的读取,然后写入XML文件,再用J
- 在Google Reader上看到网友分享的一个链接,真的发现自己已经out了。上面的这张图,是纯CSS实现的,没有背景图、没有Javasc
- <script language="JScript" Runat="Server&q
- 一.背景在现在的网站中,接入的渠道是越来越多了,技术也是越来越先进,WAP, SMS,EMAIL, 传统的Web, Socket等等,如果连
- 1、root函数格式root()功能描述返回一个路径串变量应用代码'sample string = c:\intels\jingca
- 阅读上一章:Chapter 13 为文字指定样式Chapter 14 图片替换随着更多设计师与开发者开始使用标准(特别是CSS),每天都会有
- 感谢 Dawn CSS Reset 的尝试和建议。针对字体的写法,觉得需要说明一下:body,button, input, select,
- by yemoo有时在编写网页代码时发现,img底部莫名奇妙多出大约3px的空白,无论怎么调节css都不可以,今天再次遇到此问题,网上看了一
- 大家都知道select的优先权比较高,CSS不宜控制,而且还能遮挡层的正常显示!那么我们就来模拟一个!这样样式就可以随心所欲了(若您看不到效
- 我们平日办公时用得最多的软件是Execl、Word或WPS Office等,你的计算机中一定储存着大量的XLS、DOC、WPS文件吧!网页制
- 如何让页面超时并指定一个超时时间?下面就是利用缓冲的程序页面事例: <%@ OutputCache Du