一、获取二叉树的深度
就是二叉树最后的层次,如下图:
实现代码:
代码如下:
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 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 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
-------------------------
'''

Python在web开发、数据科学、机器学习、自动化和脚本编写等领域有广泛应用。1)在web开发中,Django和Flask框架简化了开发过程。2)数据科学和机器学习领域,NumPy、Pandas、Scikit-learn和TensorFlow库提供了强大支持。3)自动化和脚本编写方面,Python适用于自动化测试和系统管理等任务。

两小时内可以学到Python的基础知识。1.学习变量和数据类型,2.掌握控制结构如if语句和循环,3.了解函数的定义和使用。这些将帮助你开始编写简单的Python程序。

如何在10小时内教计算机小白编程基础?如果你只有10个小时来教计算机小白一些编程知识,你会选择教些什么�...

使用FiddlerEverywhere进行中间人读取时如何避免被检测到当你使用FiddlerEverywhere...

Python3.6环境下加载Pickle文件报错:ModuleNotFoundError:Nomodulenamed...

如何解决jieba分词在景区评论分析中的问题?当我们在进行景区评论分析时,往往会使用jieba分词工具来处理文�...

如何使用正则表达式匹配到第一个闭合标签就停止?在处理HTML或其他标记语言时,常常需要使用正则表达式来�...

攻克Investing.com的反爬虫策略许多人尝试爬取Investing.com(https://cn.investing.com/news/latest-news)的新闻数据时,常常�...


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

mPDF
mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

SublimeText3 Linux新版
SublimeText3 Linux最新版

螳螂BT
Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

SublimeText3汉化版
中文版,非常好用

安全考试浏览器
Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。