二叉树基础知识+Python实现

基础知识

树(Tree)是一种非线性结构,用来模拟具有树状结构性质的数据集合。它是由$n(n>0)$个有限结点组成一个具有层次关系的集合。树是递归结构,在树的定义中又用到了树的概念。

基本术语

  • 树结点:包含一个数据元素及若干指向子树的分支;
  • 孩子结点(子结点):结点的子树的根称为该结点的孩子;
  • 双亲结点(父结点):B结点是A结点的孩子,则A结点是B结点的双亲;
  • 兄弟结点:同一双亲的孩子结点;
  • 堂兄结点:同一层上结点;
  • 结点层次:根结点的层定义为1;根的孩子为第二层结点,依此类推;
  • 树的高(深)度:树中最大的结点层;
  • 结点的度:结点子树的个数;
  • 树的度:树中最大的结点度;
  • 叶子结点:也叫终端结点,是度为0的结点;
  • 分枝结点:度不为0的结点(非终端结点);
  • 森林:互不相交的树集合;
  • 有序树:子树有序的树,如:家族树;
  • 无序树:不考虑子树的顺序。

性质

  • 每个节点有零个或多个子节点;
  • 没有父节点的节点称为根节点;
  • 每一个非根节点有且只有一个父节点;
  • 除了根节点外,每个子节点可以分为多个不相交的子树;
  • 树里面没有环路(cycle)。

二叉树

二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。二叉树可以为空。

性质

  1. 在二叉树的第$i$层上至多有$2^{i-1}$个结点;
  2. 深度为$k(k\geqslant 1)$的二叉树上至多含$2^k-1$个结点(参见1);
  3. 对任何一棵二叉树,若它含有$n_0$个叶子结点、$n_2$个度为2的结点,则必存在关系式:$n_0=n_2+1$(参见2);
  4. 具有$n$个结点的完全二叉树的深度为$⎣\log_2n⎦+1$或$⎡\log_2(n+1)⎤$(参见3);
  5. $n$个结点的二叉树中,完全二叉树具有最小的路径长度;
  6. 如果对一棵有$n$个结点的完全二叉树的结点按层序编号,则对任一结点$i(1\leqslant i\leqslant n)$,有:
    • 如果$i=1$,则结点$i$无双亲,是二叉树的根;如果$i>1$,则其双亲的编号是$⎣\frac{i}{2}⎦$。
    • 如果$2i>n$,无左孩子;否则,其左孩子是结点$2i$。
    • 如果$2i+1>n$,则结点$i$无右孩子;否则,其右孩子是结点$2i+1$。
1. 等比数列前n项和。
2. 设总结点数为$s$,度为0的结点数为$n_0$,度为1的结点数为$n_1$,度为2的结点数为$n_2$。则有:$n_0+n_1+n_2=s$和$0\times n_0+1\times n_1+2\times n_2+1=s$(所有结点的子结点数,再加根结点),可得$n_0=n_2+1$。
3. 设该完全二叉树的高度为$k$,则有$2^{k-1}-1<n\leqslant 2^k-1$,可得$k-1<\log_2(n+1)\leqslant k$,即$k=⎡\log_2(n+1)⎤$。

完全二叉树

若设二叉树的深度为$h$,除第$h$层外,其它各层$(1~h-1)$的结点数都达到最大个数,第$h$层所有的结点都连续集中在最左边,这就是完全二叉树。

  • 完全二叉树的$n_1=0$或$n_1=1$;
  • 完全二叉树的$n_0=⎡\frac{n}{2}⎤$(参见4)。
4. $s=2\times n_0+n_1-1$,而完全二叉树的$n_1=0$或$n_1=1$,所以$n_0=\frac{n}{2}$或$n_0=\frac{n+1}{2}$,即$n_0=⎡\frac{n}{2}⎤$。

二叉树的遍历

  1. 深度优先遍历(Depth First Search,DFS):沿着树的深度遍历树的节点,尽可能深的搜索树的分支。
    1. 前序遍历:NLR,根结点->左子树->右子树;
    2. 中序遍历:LNR,左子树->根结点->右子树;
    3. 后续遍历:LRN,左子树->右子树->根结点。
  2. 广度优先遍历(Breadth First Search,BFS;也叫层次遍历,level order):是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。

Python建立二叉树及实现各种遍历方法

二叉树结点类

1
2
3
4
5
6
class BinaryNode(object):
"""二叉树节点类"""
def __init__(self, item, left=None, right=None):
self.item = item
self.left = left
self.right = right

二叉树类

其中包含二叉树的常用操作和七种遍历方法。不做要求的情况下,使用递归的方式实现遍历最简单。

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
111
112
113
114
115
116
117
118
119
120
class BinaryTree(object):
"""二叉树及几种遍历方法"""
def __init__(self):
self.root = None
self.bi_list = [] # 使用队列存放二叉树的层次节点信息

def is_empty(self):
return self.root is None

def add(self, item):
"""依次为二叉树添加节点(从上至下,从左至右)"""
node = BinaryNode(item)
if self.is_empty():
self.root = node
self.bi_list.append(node)
else:
tmp_node = self.bi_list[0]
if tmp_node.left is None:
tmp_node.left = node
self.bi_list.append(node)
else:
tmp_node.right = node
self.bi_list.append(node)
self.bi_list.pop(0)

def pre_order(self, root):
if root is None:
return
print(root.item)
self.pre_order(root.left)
self.pre_order(root.right)

def in_order(self, root):
if root is None:
return
self.in_order(root.left)
print(root.item)
self.in_order(root.right)

def post_order(self, root):
if root is None:
return
self.post_order(root.left)
self.post_order(root.right)
print(root.item)

def level_order(self, root):
"""层次遍历,也叫广度优先搜索(Breadth-first search)。
采用队列实现。"""
if root is None:
return
queue = []
queue.append(root)
while queue:
node = queue.pop(0)
print(node.item)
# 如果孩子节点不为空,那么从左至右添加进来
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)

def pre_order_stack(self, root):
"""先序遍历的非递归实现。
使用栈"""
if root is None:
return
stack = []
node = root
while node or stack:
while node:
print(node.item)
stack.append(node)
node = node.left
node = stack.pop()
node = node.right

def in_order_stack(self, root):
"""中序遍历的非递归实现。
使用栈"""
if root is None:
return
stack = []
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
print(node.item)
node = node.right

def post_order_stack(self, root):
"""后序遍历的非递归实现。
使用栈"""
if root is None:
return
stack1, stack2 = [], []
stack1.append(root)
while stack1:
# 此循环为了找出后续遍历的逆序,存入stack2中
# 先将当前节点拿出来存入stack2中
node = stack1.pop()
stack2.append(node)
if node.left is not None:
# 若左孩子非空,先入栈stack1(先入后出,所以是逆序)
stack1.append(node.left)
if node.right is not None:
# 若右孩子非空,入栈stack1
stack1.append(node.right)
for i in stack2[::-1]:
print(i.item)

def height(self, root):
"""递归的求二叉树的最大高度。从叶子结点为‘0层’依次往上数"""
if root is None:
return 0
lheight = self.height(root.left)
rheight = self.height(root.right)
return max(lheight + 1, rheight + 1)

测试函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def test():
BT = BinaryTree()
print('二叉树是否为空:', BT.is_empty())
print('依次为二叉树添加10个节点...')
for i in range(10):
BT.add(i + 1)
print('前序遍历')
BT.pre_order(BT.root)
print('中序遍历')
BT.in_order(BT.root)
print('后序遍历')
BT.post_order(BT.root)
print('前序遍历,非递归方式')
BT.pre_order_stack(BT.root)
print('中序遍历,非递归方式')
BT.in_order_stack(BT.root)
print('后序遍历,非递归方式')
BT.post_order_stack(BT.root)
print('层次遍历')
BT.level_order(BT.root)
print('二叉树的最大高度:', BT.height(BT.root))

参考

数据结构:树和二叉树
完全二叉树
https://blog.csdn.net/Bone_ACE/article/details/46718683
https://blog.csdn.net/Marksinoberg/article/details/69482397