1. 二叉树的节点类的实现

1.1 二叉树的节点类

由于二叉树由一组节点组成,所需需要先定义一组表示二叉树节点的类。节点通过链接直接引用其子节点,没有子节点时使用None表示,空二叉树也是用None表示。

1
2
3
4
5
class BinTNode:
def __init__(self, dat, left=None, right= None):
self.data = dat
self.left = left
self.right = right

下图所示的二叉树用节点类实例化表示为:

1
2
3
binary_tree = BinTNode('A', 
BinTNode('B', BinTNode('D'), BinTNode('E')),
BinTNode('C', BinTNode('F'), BinTNode('G')))

二叉树

基于BinTNode类实现的二叉树具有递归的结构。很容易采用递归的方式处理,下面代码展示使用递归方式进行二叉树的节点的计数和节点数据的求和操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
def count_node(t):
"""统计树中的节点的个数"""
if t is None:
return 0
else:
return 1 + count_node(t.left) + count_node(t.right)

def sum_node(t):
"""假设节点中存储数据,求这个树中所有节点的数值和"""
if t is None:
return 0
else:
return t.data + sum_node(t.left) + sum_node(t.right)

1.2 二叉树的遍历

二叉树的遍历可以采用深度优先遍历(DFS)广度优先遍历(BFS)

1.2.1 深度优先遍历

先根序(DLR)遍历

1
2
3
4
5
6
7
def DLR(t):
"""先根序递归遍历二叉树"""
if t is None:
return
print(t.data, end=' ')
DLR(t.left)
DLR(t.right)

中根序(LDR)遍历

1
2
3
4
5
6
7
def LDR(t):
"""中根序递归遍历二叉树"""
if t is None:
return
LDR(t.left)
print(t.data, end=' ')
LDR(t.right)

后根序(LRD)遍历

1
2
3
4
5
6
7
def LRD(t):
"""后根序递归遍历二叉树"""
if t is None:
return
LRD(t.left)
LRD(t.right)
print(t.data, end=' ')

1.2.2 广度优先遍历

要实现使用广度优先搜索的方式遍历二叉树,同样需要使用一个队列,这里使用了Python内置的数据结构模块queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from queue import Queue

def breadth_first_search(t):
"""BFS算法对二叉树进行搜索"""
q = Queue()
q.put(t)
while not q.empty():
t = q.get()
if t is None:
continue
q.put(t.left)
q.put(t.right)
print(t.data, end=' ')

test_tree = BinTNode(1, BinTNode(2, BinTNode(4)), BinTNode(3))
breadth_first_search(test_tree)

# out: 1 2 3 4

1.2.3 非递归深度优先遍历

非递归先根序DLR遍历
在三中深度优先遍历中,DLR这种非递归遍历方式简单。在遍历的开始需要使用一个栈结构,保存树尚未访问过的节点信息,先关步骤如下:

  • 采取先根序,右节点就需要进行访问,下一步沿着树的左枝下行
  • 节点的右分支没有访问,因此需要进行记录,将其入栈
  • 遇到空树时进行回溯,取出栈中保存的一个右分支,重复上面的步骤

循环条件:变量t一直取为当前待遍历的根节点,栈中保存的是当前遇到但是尚未遍历的右子树,只要当前树非空或者栈不空就需要继续循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def NonReDLR(t):
"""非递归先根序遍历二叉树"""
stack = [] # 使用一个list来模拟栈结构
while t is not None or len(stack) > 0:
while t is not None:
print(t.data, end=' ')
stack.append(t.right)
t = t.left
t = stack.pop()

test_tree = BinTNode(1, BinTNode(2, BinTNode(4)), BinTNode(3))
NonReELR(test_tree)

# out: 1 2 4 3

非递归中根序LDR遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def NonReLDR(t):
"""非递归的中根序遍历二叉树"""
stack = []
while t is not None or len(stack) > 0:
if t is not None:
stack.append(t)
t = t.left
else:
t = stack.pop()
print(t.data, end=' ')
t = t.right

test_tree = BinTNode(1, BinTNode(2, BinTNode(4)), BinTNode(3))
NonReLDR(test_tree)

# out: 4 2 1 3

非递归后根序LRD遍历

二叉树非递归三种深度优先搜索中,后根序最麻烦。在这种遍历中,每个根节点都要经过三次,第一次遇到时应该立即转向它的左子树,从左子树回到根节点应该转向右子树,从右子树回来后再处理根节点,然后返回上一层。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def NonReLRD(t):
"""非递归后根序遍历二叉树"""
stack = []
while t is not None or len(stack) > 0:
while t is not None:
stack.append(t)
t = t.left if t.left is not None else t.right
t = stack.pop()
print(t.data, end=' ')
if len(stack) > 0 and stack.pop().left == t:
# 栈不为空且当前节点是栈顶的左子树
t = stack.pop().right
else:
# 没有左子树或者右子树遍历完毕,强行退栈
t = None

test_tree = BinTNode(1, BinTNode(2, BinTNode(4)), BinTNode(3))
NonReLRD(test_tree)

# out: 4 2 3 1