二叉树
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()
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
测试代码如下：
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
'''
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59