0%

二叉树

二叉树的概念和实现

  • 根节点:树中上部的节点

  • 左叶子节点

  • 右叶子节点

  • 子树

    • 完整的子树

      • 一个根节点,左右叶子节点组成
    • 不完整的子树

      • 根节点,左叶子节点

      • 根节点,右叶子节点

      • 根节点

        • 特点:每一个节点都可以作为某一颗子树的根节点

使用 Python 实现一个二叉树:

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
class Node:
def __init__(self, item):
self.item = item
self.left = None # 指向该节点的左叶子节点
self.right = None # 指向该节点的右叶子节点

class Tree:
def __init__(self): # 构建一颗空树
self.root = None # 永远指向二叉树中的根节点
# 自上到下从左到右的准则插入新的节点
def insert(self, item): # 向树种插入一个节点
node = Node(item)
# 如果树为空
if self.root == None:
self.root = node
return
# 如果树为非空
cur = self.root
q = [cur]
while True:
n = q.pop(0)
if n.left == None:
n.left = node
break
else:
q.append(n.left)
if n.right == None:
n.right = node
break
else:
q.append(n.right)

def travel(self):
q = [self.root]
while q:
n = q.pop(0)
print(n.item)
if n.left != None:
q.append(n.left)
if n.right != None:
q.append(n.right)

tree = Tree()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
tree.travel() # 1 2 3 4 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
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
class Node:
def __init__(self, item):
self.item = item
self.left = None
self.right = None

class Tree:
def __init__(self):
self.root = None

def insert(self, item):
node = Node(item)
if self.root == None:
self.root = node
return
q = [self.root]
while True:
n = q.pop(0)
if n.left == None:
n.left = node
break
else:
q.append(n.left)
if n.right == None:
n.right = node
break
else:
q.append(n.right)
# 前序遍历
# 参数root表示的是子树的根节点,需要给递归调用的forward传入不同子树的根节点
def forward(self, root): # 根左右
if root == None:
return
print(root.item)
self.forward(root.left)
self.forward(root.right)
# 中序遍历
def middle(self, root): # 左根右
if root == None:
return
self.middle(root.left)
print(root.item)
self.middle(root.right)
# 后序遍历
def back(self, root): # 左右根
if root == None:
return
self.back(root.left)
self.back(root.right)
print(root.item)

tree = Tree()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
tree.insert(6)
tree.insert(7)
tree.forward(tree.root) # 1 2 4 5 3 6 7
tree.middle(tree.root) # 4 2 5 1 6 3 7
tree.back(tree.root) # 4 5 2 6 7 3 1

排序二叉树

二叉树的优势在于查询速度快。但是查询速度快是要建立在有序的基础上的。对于无序二叉树,还是需要遍历才能找到数据。给二叉树排序,创建有序二叉树,是一个很重要的事情。

接下来,我们就实现要给排序二叉树。

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
class Node:
def __init__(self, item):
self.item = item
self.left = None
self.right = None

class SortTree:
def __init__(self):
self.root = None

def add(self, item): # 将节点插入到排序二叉树中
node = Node(item)
if self.root == None: # 树为空的情况
self.root = node
return
# 树为非空
cur = self.root
while True:
if cur.item > item: # 插入的节点值小于根节点,该节点需要插入到根节点的左侧
if cur.left == None: # 如果左节点为空,则直接插入
cur.left = node
break
cur = cur.left # 左节点为非空,继续查找
else: # 插入节点的值大等于于根节点,该节点需要插入到根节点的右侧
if cur.right == None:
cur.right = node
break
cur = cur.right
# 中序遍历
def middle(self, root):
if root == None:
return
self.middle(root.left)
print(root.item)
self.middle(root.right)

stree = SortTree()
lst = [3, 5, 2, 4, 6, 1, 7]
for i in lst:
stree.add(i)
stree.middle(stree.root) # 1 2 3 4 5 6 7