二叉树
1. 树的概念
在数据结构中,树可以看作是一种通过递归生成的数据结构,每棵树只有一个根结点(下图中的A)而其他的结点可以有很多个,树的结构如下图所示:
2. 树的术语
在树结构中,有很多专业的术语,常见的术语及解释如下:
- 根结点:A
- 祖先结点:B和K
- 子孙结点:K和B
- 父结点:E和K
- 子结点:K和E
- 兄弟结点:K和L
- 叶子结点:度等于0的节点,F、G等
- 结点的度:树中一个结点的子结点个数,A有3个子结点
- 树的度:结点最大度数
3. 二叉树的定义
对于每个结点来说最多有两棵子树的树叫做二叉树,二叉树有左右之分,次序不能颠倒。
4. 常见的特殊二叉树
- 满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。
- 完全二叉树:对于一棵二叉树,假设其深度为d(d>1)。除了第d层外,其他各层的结点数目均已达最大值,且第d层所有结点从左到右的紧密排列。
满二叉树和完全二叉树的结构如下图所示(A为满二叉树,B为完全二叉树,满二叉树也是一种完全二叉树)
二叉树的遍历
1. 常见的二叉树遍历形式
现有如下的一颗二叉树:
常见的二叉树遍历形式可以分为下列四种:
前序遍历:先访问根节点,然后前序遍历左子树,再前序遍历右子树。
- 结果:ABDECFG
中序遍历:中序遍历根节点的左子树,然后是访问根节点,最后遍历右子树。
- 结果:DBEAFCG
后序遍历:从左到右先叶子后节点的方式遍历访问左右子树,最后访问根节点。
- 结果:DEBFGCA
层次遍历:从根节点从上往下逐层遍历,在同一层,按从左到右的顺序对节点逐个访问。
- 结果:ABCDEFG
2. 二叉树的实现
二叉树的构建及一些功能函数的实现方法如下:
# 二叉树类
class BTree(object):
# 初始化
def __init__(self, data=None, left=None, right=None):
self.data = data # 数据域
self.left = left # 左子树
self.right = right # 右子树
# 前序遍历
def preorder(self):
# 根左右
if self.data is not None:
print(self.data, end=' ')
if self.left is not None:
self.left.preorder()
if self.right is not None:
self.right.preorder()
# 中序遍历
def inorder(self):
# 左根右
if self.left is not None:
self.left.inorder()
if self.data is not None:
print(self.data, end=' ')
if self.right is not None:
self.right.inorder()
# 后序遍历
def postorder(self):
# 左右根
if self.left is not None:
self.left.postorder()
if self.right is not None:
self.right.postorder()
if self.data is not None:
print(self.data, end=' ')
# 层序遍历
def levelorder(self):
# 返回某个节点的左孩子
def LChild_Of_Node(node):
return node.left if node.left is not None else None
# 返回某个节点的右孩子
def RChild_Of_Node(node):
return node.right if node.right is not None else None
# 层序遍历列表
level_order = []
# 是否添加根节点中的数据
if self.data is not None:
level_order.append([self])
# level_order[[0],[1,2]]
# 二叉树的高度
height = self.height()
if height >= 1:
# 对第二层及其以后的层数进行操作, 在level_order中添加节点而不是数据
for _ in range(2, height + 1): # (0,5) 1,2,3,4,5
level = [] # 该层的节点
for node in level_order[-1]:
# 如果左孩子非空,则添加左孩子
if LChild_Of_Node(node):
level.append(LChild_Of_Node(node))
# 如果右孩子非空,则添加右孩子
if RChild_Of_Node(node):
level.append(RChild_Of_Node(node))
# 如果该层非空,则添加该层
if level:
level_order.append(level)
# 取出每层中的数据
for i in range(0, height): # 层数
for index in range(len(level_order[i])):
level_order[i][index] = level_order[i][index].data
return level_order
# 二叉树的高度
def height(self):
# 空的树高度为0, 只有root节点的树高度为1
if self.data is None:
return 0
elif self.left is None and self.right is None:
return 1
elif self.left is None and self.right is not None:
return 1 + self.right.height()
elif self.left is not None and self.right is None:
return 1 + self.left.height()
else:
return 1 + max(self.left.height(), self.right.height())
# 二叉树的叶子节点
def leaves(self):
if self.data is None:
return None
elif self.left is None and self.right is None:
print(self.data, end=' ')
elif self.left is None and self.right is not None:
self.right.leaves()
elif self.right is None and self.left is not None:
self.left.leaves()
else:
self.left.leaves()
self.right.leaves()
AI 代码解读
测试代码如下:
right_tree = BTree(6)
right_tree.left = BTree(2)
right_tree.right = BTree(4)
left_tree = BTree(5)
left_tree.left = BTree(1)
left_tree.right = BTree(3)
tree = BTree(11)
tree.left = left_tree
tree.right = right_tree
left_tree = BTree(7)
left_tree.left = BTree(3)
left_tree.right = BTree(4)
right_tree = tree # 增加新的变量
tree = BTree(18)
tree.left = left_tree
tree.right = right_tree
print('先序遍历为:')
tree.preorder()
print()
print('中序遍历为:')
tree.inorder()
print()
print('后序遍历为:')
tree.postorder()
print()
print('层序遍历为:')
level_order = tree.levelorder()
print(level_order)
print()
height = tree.height()
print('树的高度为%s.' % height)
print()
print('叶子节点为:')
tree.leaves()
# 输出如下
'''
先序遍历为:
18 7 3 4 11 5 1 3 6 2 4
中序遍历为:
3 7 4 18 1 5 3 11 2 6 4
后序遍历为:
3 4 7 1 3 5 2 4 6 11 18
层序遍历为:
[[18], [7, 11], [3, 4, 5, 6], [1, 3, 2, 4]]
树的高度为4.
叶子节点为:
3 4 1 3 2 4
'''
AI 代码解读