一、获取二叉树的深度
就是二叉树最后的层次，如下图：
实现代码：
代码如下:
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之Seaborn（数据可视化）Apr 21, 2022 pm 06:08 PM本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于Seaborn的相关问题，包括了数据可视化处理的散点图、折线图、条形图等等内容，下面一起来看一下，希望对大家有帮助。
详细了解Python进程池与进程锁May 10, 2022 pm 06:11 PM本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于进程池与进程锁的相关问题，包括进程池的创建模块，进程池函数等等内容，下面一起来看一下，希望对大家有帮助。
Python自动化实践之筛选简历Jun 07, 2022 pm 06:59 PM本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于简历筛选的相关问题，包括了定义 ReadDoc 类用以读取 word 文件以及定义 search_word 函数用以筛选的相关内容，下面一起来看一下，希望对大家有帮助。
Python数据类型详解之字符串、数字Apr 27, 2022 pm 07:27 PM本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于数据类型之字符串、数字的相关问题，下面一起来看一下，希望对大家有帮助。
分享10款高效的VSCode插件，总有一款能够惊艳到你！！Mar 09, 2021 am 10:15 AMVS Code的确是一款非常热门、有强大用户基础的一款开发工具。本文给大家介绍一下10款高效、好用的插件，能够让原本单薄的VS Code如虎添翼，开发效率顿时提升到一个新的阶段。
详细介绍python的numpy模块May 19, 2022 am 11:43 AM本篇文章给大家带来了关于Python的相关知识，其中主要介绍了关于numpy模块的相关问题，Numpy是Numerical Python extensions的缩写，字面意思是Python数值计算扩展，下面一起来看一下，希望对大家有帮助。
python中文是什么意思Jun 24, 2019 pm 02:22 PMpythn的中文意思是巨蟒、蟒蛇。1989年圣诞节期间，Guido van Rossum在家闲的没事干，为了跟朋友庆祝圣诞节，决定发明一种全新的脚本语言。他很喜欢一个肥皂剧叫Monty Python，所以便把这门语言叫做python。
热AI工具
Undresser.AI Undress
人工智能驱动的应用程序，用于创建逼真的裸体照片
AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。
Undress AI Tool
免费脱衣服图片
Clothoff.io
AI脱衣机
AI Hentai Generator
免费生成ai无尽的。
热门文章
热工具
SublimeText3汉化版
中文版，非常好用
MinGW - 适用于 Windows 的极简 GNU
这个项目正在迁移到osdn.net/projects/mingw的过程中，你可以继续在那里关注我们。MinGW：GNU编译器集合（GCC）的本地Windows移植版本，可自由分发的导入库和用于构建本地Windows应用程序的头文件；包括对MSVC运行时的扩展，以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。
Atom编辑器mac版下载
最流行的的开源编辑器
记事本++7.3.1
好用且免费的代码编辑器
mPDF
mPDF是一个PHP库，可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件，并处理不同的语言。与原始脚本如HTML2FPDF相比，它的速度较慢，并且在使用Unicode字体时生成的文件较大，但支持CSS样式等，并进行了大量增强。支持几乎所有语言，包括RTL（阿拉伯语和希伯来语）和CJK（中日韩）。支持嵌套的块级元素（如P、DIV），
