python常用算法（5）——树，二叉树与AVL树
1，树
树是一种非常重要的非线性数据结构，直观的看，它是数据元素（在树中称为节点）按分支关系组织起来的结构，很像自然界中树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到了广泛应用，如在编译源程序时，可用树表示源程序的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可以用树来描述。
树（Tree）是元素的集合。树的定义是递归的，树是一种递归的数据结构。比如：目录结构。树是由n个结点组成的集合：如果n=0，那这就是一颗空树；如果 n>0，那么存在1个结点作为树的根节点，其他结点可以分为m个集合，每个集合本身又是一棵树。
1，树的根结点没有前驱结点，除根结点之外所有结点有且只有一个前驱结点。
2，树中所有结点可以有零个或者多个后继结点。
1.1 树的术语
根节点：树的第一个节点，没有父节点的节点
叶子节点：不带分叉的节点
树的深度（高度）：就是分了多少层
孩子节点，父节点：节点与节点之间的关系
如下图，我们分别解释：
1）B是K的祖先结点，K是B的子孙节点，E是K的双亲节点，K是E的孩子节点，K是L的兄弟节点。
2）树中一个结点的子节点个数为该节点的度，树中结点最大度数为树的度。
3）度大于0为节点结点，度等于0为叶子结点。
4）结点层次如图，结点深度时从根结点从顶往下累加，结点高度从低往上累加，树的高度（深度）是树的最大层数。
5）有序树：从左到右有次序，有关联。反之为无序树。
6）两结点之间的路径是两个结点之间所经过的结点序列构成的，路径长度是路径上所经过的边的个数。
7）森林是 m （m >=0）棵互不相交的集合。
上面观察实际上给了我们一种严格的定义树的方法：
1，树是元素的集合
2，该集合可以为空，这时树中没有元素，我们称树为空树（empty tree）
3，如果该集合不为空，那么该集合有一个根节点，以及0个或者多个子树。根节点与他的子树的根节点用一个边（edge）相连。
1.2 树的实现
树的示意图已经给出了树的一种内存实现方法：每个节点存储元素和多个指向子节点的指针。然而，子节点数目的是不确定的。一个父节点可能有大量的子节点，而另一个父节点可能只有一个子节点，而树的增删节点操作会让子节点的数目发生进一步的变换。这种不确定性就可能就可能带来大量的内存相关操作，并且容易造成内存的浪费。
一种经典的实现方法如下：
树的内存实现：拥有同一父节点的两个结点互为兄弟节点（sibling）。上图的实现方式中，每个节点包含一个指针指向第一个子节点，并且有另一个指针指向他的下一个兄弟节点。这样，我们就可以用统一的，确定的结构来表示每个节点。
1.3 树的实例——模拟文件系统
代码如下：
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
#_*_coding:utf-8_*_
class Node:
def __init__(self, name, type='dir'):
self.name = name
self.type = type # 'dir' or ; 'file'
self.children = []
self.parent = None
# 链式存储
def __repr__(self):
return self.name
class FileSystemTree:
def __init__(self):
self.root = Node("/") # 首先我们创建一个根目录
self.now = self.root
def mkdir(self, name):
# 创建一个文件目录，所以我们必须保证name是以 /结尾，如果没有，我们就加
if name[-1] != '/':
name += '/'
node = Node(name)
# 创建一个文件目录
self.now.children.append(node)
node.parent = self.now
def ls(self):
# 展示当前文件夹下的文件
return self.now.children
def cd(self, name):
# 切换到指定目录 注意：支持绝对路径和相对路径
# 相对路径是从now的路径下开始，而绝对路径是从root路径下开始找
if name[-1] != '/':
name += '/'
if name == '../':
self.now = self.now.parent
return
for child in self.now.children:
if child.name == name:
# 如果传入的目录名等于孩子的目录名，我们直接切换
self.now = child
return
raise ValueError("invalid dir")
tree = FileSystemTree()
tree.mkdir('var/')
tree.mkdir('bin/')
tree.mkdir('usr/')
print(tree.ls()) # [var/, bin/, usr/]
tree.cd('bin/')
print(tree.ls()) # []
print(tree.root.children) # [var/, bin/, usr/]
2，二叉树
2.1 二叉树的定义
二叉树的链式存储：将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接。
二叉树是一种特殊的树，它具有以下特点：
1）至多只有两棵子树，二叉树有左右之分，次序不能颠倒，也是递归形式定义。
2）或者为空二叉树，即 n=0
3）或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。
4）每个节点至多有两个节点，即每个节点的度最多为2
5）二叉树中所有节点的形态有5种：空节点，无左右子树的节点，只有左子树的节点，只有右子树的节点和具有左右子树的节点
二叉树的定义如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class BiTreeNode:
def __init__(self, data):
self.data = data
self.lchild = None # 左孩子
self.rchild = None # 右孩子
a = BiTreeNode("A")
b = BiTreeNode("B")
c = BiTreeNode("C")
d = BiTreeNode("D")
e = BiTreeNode("E")
f = BiTreeNode("F")
g = BiTreeNode("G")
e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f
root = e
print(root.lchild.rchild.data)
二叉树的节点定义：
1
2
3
4
5
class BiTreeNode:
def __init__(self, data):
self.data = data
self.lchild = None # 左孩子
self.rchild = None # 右孩子
2.2 二叉树与度为2的有序树的区别：
1）度为2的树至少有3个结点，而二叉树可以为空。
2）左右次数。
2.3 二叉树的存储方式
二叉树的存储结构分为链式存储结构和顺序存储结构（列表）
二叉树的顺序存储方式
思考：父节点和左孩子节点的编号下标有什么关系？
0-1 1-3 2-5 3-7 4-9 i ----> 2i+1
父节点和右孩子节点的编号下标有有什么关系？
0-2 1-4 2-6 3-8 4-10 i -----> 2i+2
二叉树的链式存储
结构采用链式存储二叉树中的数据元素，用链建立二叉树中结点之间的关系。二叉树最常用的链式存储结构是二叉链，每个节点包含三个域，分别是数据元素域 data，左孩子链域 LChild 和 右孩子链域 rChild。与单链表带头结点和不带头节点的两种情况相似，二叉链存储结构的二叉树也有带头结点和不带头节点两种。
2.4 二叉树的遍历
那么如何遍历一颗二叉树呢？其实有两种通用的遍历树策略：
深度优先搜索（DFS）
在这个策略中，我们采用深度作为优先级，以便从根开始一直到达某个确定的叶子，然后再返回根到达另一个分支。
深度优先搜索策略又可以根据根节点，左孩子和右孩子的相对顺序被细分为先序遍历，中序遍历和后序遍历。
宽度优先搜索（BFS）
我们按照高度顺序一层一层的访问整棵树，高层次的节点将会被低层次的节点先被访问到。
下图中的顶点按照访问的顺序编号，按照1-2-3-4-5 的顺序来比较不同的策略：
下面学习二叉树的遍历方式，以下图的二叉树为例，我们分别学习前序遍历，中序遍历，后序遍历，层次遍历。
前序遍历
思想：先访问根节点，再先序遍历左子树，然后再序遍历右子树。总的来说是 根——左——右
前序遍历如图所示：
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 二叉树的前序遍历
def pre_order(root):
if root:
print(root.data) # 先打印根节点
pre_order(root.lchild)
pre_order(root.rchild)
# pre_order(root)
'''
E
A
C
B
D
G
F
'''
中序遍历
思想：先中序访问左子树，再序访问根节点，最后中序遍历右子树。总的来说是 左——根——右
中序遍历如图所示：
代码如图所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 中序遍历
def in_order(root):
if root:
in_order(root.lchild)
print(root.data)
in_order(root.rchild)
# in_order(root)
'''
A
B
C
D
E
G
F
'''
后序遍历
思想：先后续访问左子树，然后后续访问右子树，最后访问根，总的来说是 左——右——根
后序遍历如图所示：
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 后序遍历
def post_order(root):
if root:
post_order(root.lchild)
post_order(root.rchild)
print(root.data)
post_order(root)
'''
B
D
C
A
F
G
E
'''
层次遍历（宽度优先遍历）
思想：利用队列，依次将根，左子树，右子树存入队列，按照队列的先进先出规则来实现层次遍历。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import deque
def level_order(root):
queue = deque()
queue.append(root)
while len(queue) > 0: # 只要队不空
node = queue.popleft()
print(node.data)
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
level_order(root)
'''
E
A
G
C
F
B
D
'''
3 几个特殊的二叉树
3.1 满二叉树
满二叉树作为一种特殊的二叉树，它是指：除了叶子节点，所有节点都有两个孩子（左子树和右子树），并且所有叶子节点深度都一样。
其特点有：
1）叶子节点只能出现在最下面一层
2）非叶子节点度一定是2
3）在同样深度的二叉树中，满二叉树的节点个数最多，节点个数为：2h-1，其h为树的深度。
3.2 完全二叉树
完全二叉树是由满二叉树引申而来，假设二叉树深度为 h，那么除了第h层外，之前的每一层（1~h-1）的节点数都达到最大，即没有空的位置，而且第K层的子节点也都集中在左子树上（顺序）。
其具有以下特点：
1）叶子节点可以出现在最后一层或倒数第二层
2）最后一层的叶子节点一定集中在左部连续位置
3）完全二叉树严格按层序编号（可利用数组或列表实现，满二叉树同理）
4）若一个节点为叶子节点，那么编号比其大的节点均为叶子节点
3.3 二叉排序树
一颗二叉树或者空二叉树，如：左子树上所有关键字均小于根结点的关键字，右子树上的所有结点的关键字均大于根结点的关键字，左子树和右子树各是一颗二叉排序树。
3.4 平衡二叉树
树上任何一结点的左子树和右子树的深度只差不超过1 。
4， 二叉搜索树（BST）
4.1 二叉搜索树的定义
二叉搜索树(Binary Search Tree)，又名二叉排序树(Binary Sort Tree)。
由于二叉树的子节点数目确定，所以可以直接采用下图方式在内存中实现。每个节点有一个左子节点（left children）和右子节点（right children）。左子节点是左子树的根节点，右子节点是右子树的根节点。
如果我们给二叉树加一个额外的条件，就可以得到一种被称为二叉搜索树（binary search tree）的特殊二叉树。二叉搜索树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。
二叉搜索树是一颗二叉树且满足性质：设x是二叉树的一个节点。如果 y 是 x 左子树的一个节点，那么 y.key <= x.key；如果y 是x 的右子树的一个节点，那么 y.key >= x.key。
4.2 二叉搜索树的性质
1）若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值
2）若右子树不为空，则右子树上所有节点的值均大于或等于它的跟节点的值
3）左右子树也分别为二叉搜索树
二叉搜索树，注意树中元素的大小。二叉搜索树可以方便的实现搜索算法。在搜索元素 x 的时候，我们可以将 x 和根节点比较：
1，如果 x 等于根节点，那么找到 x ,停止搜索（终止条件）
2，如果 x 小于根节点，那么搜索左子树
3，如果 x 大于根节点，那么搜索右子树
二叉搜索树所需要进行的操作次数最多与树的深度相等。n个结点的二叉搜索树的深度最多为 n ，最少为 log(n).
4.3 二叉搜索树的插入操作
从根节点开始，若插入的值比根节点的值小，则将其插入根节点的左子树；若比根节点的值大，则将其插入根节点的右子树。该操作可以使用递归进行实现。
代码如下：
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
class BiTreeNode:
def __init__(self, data):
self.data = data
self.lchild = None # 左孩子
self.rchild = None # 右孩子
self.parent = None
class BST:
def __init__(self, li=None):
self.root = None
if li:
for val in li:
self.insert_no_rec(val)
def insert(self, node, val):
if not node:
node = BiTreeNode(val)
elif val < node.data:
node.lchild = self.insert(node.lchild, val)
node.lchild.parent = node
elif val > node.data:
node.rchild = self.insert(node.rchild, val)
node.rchild.parent = node
return node
def insert_no_rec(self, val):
p = self.root
if not p: # 空树
self.root = BiTreeNode(val)
return
while True:
if val < p.data:
if p.lchild:
p = p.lchild
else: # 左孩子不存在
p.lchild = BiTreeNode(val)
p.lchild.parent = p
return
elif val > p.data:
if p.rchild:
p = p.rchild
else:
p.rchild = BiTreeNode(val)
p.rchild.parent = p
return
else:
return
4.4 二叉搜索树的查询操作
从根节点开始查找，待查找的值是否与根节点的值相同，若相同则返回True；否则，判断待寻找的值是否比根节点的值小，若是则进入根节点左子树进行查找，否则进入右子树进行查找。该操作使用递归实现。
代码如下：
1
2
3
4
5
6
7
8
9
def query(self, node, val):
if not node:
return None
if node.data < val:
return self.query(node.rchild, val)
elif node.data > val:
return self.query(node.lchild, val)
else:
return node
4.5 二叉树的查询操作——找最大值（最小值）
查找最小值：从根节点开始，沿着左子树一直往下，直到找到最后一个左子树节点，按照定义可知，该节点一定是该二叉搜索树中的最小值节点。
程序代码如下：
1
2
3
4
5
6
def findMin(self, root):
'''查找二叉搜索树中最小值点'''
if root.left:
return self.findMin(root.left)
else:
return root
查找最大值：从根节点开始，沿着右子树一直往下，知道找到最后一个右子树节点，按照定义可知，该节点一定是该二叉搜索树中的最大值节点。
程序代码如下：
1
2
3
4
5
6
def findMax(self, root):
'''查找二叉搜索树中最大值点'''
if root.right:
return self.findMax(root.right)
else:
return root
4.6 二叉搜索树的删除操作
对二叉搜索树节点的删除操作分为以下三种情况
1，如果要删除的节点是叶子节点：直接删除
2，如果要删除的节点只有一个孩子：将此节点的父亲与孩子连接，然后删除该节点（注意：该待删节点可能只有左子树或者右子树）
3，如果要删除的节点有两个孩子：将其右子树的最小节点（该节点最多有一个右孩子）删除，并替换当前节点
代码如下：
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
# _*_coding:utf-8_*_
import random
class BiTreeNode:
def __init__(self, data):
self.data = data
self.lchild = None # 左孩子
self.rchild = None # 右孩子
self.parent = None
class BST:
def __init__(self, li=None):
self.root = None
if li:
for val in li:
self.insert_no_rec(val)
def __remove_node_1(self, node):
# 第一种情况：node是叶子节点
if not node.parent:
self.root = None
if node == node.parent.lchild: # node是他父亲的左孩子
node.parent.lchild = None
node.parent = None # 可以不写
else: # node是他父亲的右孩子
node.parent.rchild = None
def __remove_node_21(self, node):
# 情况2.1:node只有一个孩子，且为左孩子
if not node.parent: # 根节点
self.root = node.lchild
node.lchild.parent = None
elif node == node.parent.lchild: # node是它父亲的左孩子
node.parent.lchild = node.lchild
node.lchild.parent = node.parent
else: # node 是它父亲的右孩子
node.parent.rchild = node.lchild
node.lchild.parent = node.parent
def __remove_node_22(self, node):
# 情况2.2：node只有一个孩子，且为右孩子
if not node.parent:
self.root = node.rchild
elif node == node.parent.lchild:
node.parent.lchild = node.rchild
node.rchild.parent = node.parent
else:
node.parent.rchild = node.rchild
node.rchild.parent = node.parent
def delete(self, val):
if self.root: # 不是空树
node = self.query_no_rec(val)
if not node: # 不存在
return False
if not node.lchild and not node.rchild: # 1，叶子节点
self.__remove_node_1(node)
elif not node.rchild: # 2.1 只有一个左孩子
self.__remove_node_21(node)
elif not node.lchild: # 2.2 只有一个右孩子
self.__remove_node_22(node)
else:
# 3,两个孩纸都有
min_node = node.rchild
while min_node.lchild: # 有左孩子
min_node = min_node.lchild
node.data = min_node.data
# 删除min_node
if min_node.rchild:
self.__remove_node_22(min_node)
else:
self.__remove_node_1(min_node)
4.7 二叉搜索树的打印操作
实现二叉搜索树的前序遍历，中序遍历，后序遍历，并打印出来。其中中序遍历打印出来的数列是按照递增顺序排列。
程序的代码如下：
1
2
3
4
5
6
7
def printTree(self, root):
# 打印二叉搜索树（中序打印，有序数列—）
if root == None:
return
self.printTree(root.left)
print(root.val, end=',')
self.printTree(root.right)
4.8 二叉树的插入，查询，删除，打印完整代码
代码如下：
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