Python实现二叉树及其遍历
树结构多种多样，不过最常用的还是二叉树。顾名思义，二叉树每个节点最多有两个叉，也就是两个子节点，分别是左子节点和右子节点。
树的组成及相关概念
树的组成
- 根节点
- 父节点
- 子节点
- 兄弟结点
- 叶子节点或叶节点
树的概念
- 节点的高度：节点到叶子节点最长路径(边数)
- 节点的深度：根节点到这个节点所经历的边的个数
- 节点的层数：节点的深度 + 1
- 树的高度：根节点的高度
树的构建
1 | class Node(): |
树的遍历
递归方式实现深度优先遍历
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
66class Node():
'''
结点类
'''
def __init__(self, value=None, lft=None, rgt = None):
self.value = value
self.lft = lft
self.rgt = rgt
def __str__(self):
return str(self.value)
class Tree():
'''
树类
'''
def __init__(self):
self.root = Node()
self.myqueue = [] # 用来存放子树的三个节点，依次为root, left, right
def add(self, elem):
node = Node(elem)
if self.root.value == None: # 树为空，进行赋值
self.root = node
self.myqueue.append(self.root)
else: # 此树不为空，但子节点还没补齐
treeNode = self.myqueue[0]
if treeNode.lft == None:
treeNode.lft = node
self.myqueue.append(treeNode.lft)
else:
treeNode.rgt = node
self.myqueue.append(treeNode.rgt)
self.myqueue.pop(0) # 该节点如果存在右子树，将此结点丢弃
# 递归方式前中后序遍历
def preOrder(self, root):
'''
前序遍历
'''
if root == None:
return
else:
print(root.value)
self.preOrder(root.lft)
self.preOrder(root.rgt)
def inOrder(self, root):
'''
中序遍历
'''
if root == None:
return
self.inOrder(root.lft)
print(root.value)
self.inOrder(root.rgt)
def postOrder(self, root):
'''
后序遍历
'''
if root == None:
return
self.postOrder(root.lft)
self.postOrder(root.rgt)
print(root.value)利用栈实现非递归方式深度优先遍历
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
91class Node():
'''
结点类
'''
def __init__(self, value=None, lft=None, rgt = None):
self.value = value
self.lft = lft
self.rgt = rgt
def __str__(self):
return str(self.value)
class Tree():
'''
树类
'''
def __init__(self):
self.root = Node()
self.myqueue = [] # 用来存放子树的三个节点，依次为root, left, right
def add(self, elem):
node = Node(elem)
if self.root.value == None: # 树为空，进行赋值
self.root = node
self.myqueue.append(self.root)
else: # 此树不为空，但子节点还没补齐
treeNode = self.myqueue[0]
if treeNode.lft == None:
treeNode.lft = node
self.myqueue.append(treeNode.lft)
else:
treeNode.rgt = node
self.myqueue.append(treeNode.rgt)
self.myqueue.pop(0) # 该节点如果存在右子树，将此结点丢弃
# 非递归方式前中后序遍历，利用栈实现
def preOrder_stack(self, root):
'''
利用栈实现前序遍历
'''
if root == None:
return
node = root
mystack = [] # 保存遍历的节点
while node or mystack:
while node: # 从根节点开始，先遍历左子树
print(node.value) # 先打印再入栈
mystack.append(node)
node = node.lft
node = mystack.pop() # 弹出栈顶元素，开始遍历右子树
node = node.rgt # 每弹出一个结点，紧接着就访问其右子树
def inOrder_stack(self, root):
'''
利用栈实现中序遍历
'''
if root == None:
return
node = root
mystack = []
while node or mystack:
while node: # 从根节点开始，一直找到左子树到最后一个节点
mystack.append(node) # 先入栈后打印
node = node.lft
node = mystack.pop() # pop顺序: left, root, right
print(node.value)
node = node.rgt
def postOrder_stack(self, root):
'''
利用栈实现后序遍历
'''
if root == None:
return
node = root
mystack1 = [] # 存放正在访问的节点
mystack2 = [] # 存放后序遍历的逆序
mystack1.append(node)
while mystack1:
node = mystack1.pop()
if node.lft:
mystack1.append(node.lft)
if node.rgt:
mystack1.append(node.rgt)
mystack2.append(node)
while mystack2:
print(mystack2.pop().value)广度优先遍历
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
51class Node():
'''
结点类
'''
def __init__(self, value=None, lft=None, rgt = None):
self.value = value
self.lft = lft
self.rgt = rgt
def __str__(self):
return str(self.value)
class Tree():
'''
树类
'''
def __init__(self):
self.root = Node()
self.myqueue = [] # 用来存放子树的三个节点，依次为root, left, right
def add(self, elem):
node = Node(elem)
if self.root.value == None: # 树为空，进行赋值
self.root = node
self.myqueue.append(self.root)
else: # 此树不为空，但子节点还没补齐
treeNode = self.myqueue[0]
if treeNode.lft == None:
treeNode.lft = node
self.myqueue.append(treeNode.lft)
else:
treeNode.rgt = node
self.myqueue.append(treeNode.rgt)
self.myqueue.pop(0) # 该节点如果存在右子树，将此结点丢弃
def levelOrder(self, root):
'''
层次遍历
'''
if root == None:
return
myqueue = []
node = root
myqueue.append(node)
while myqueue:
node = myqueue.pop(0)
print(node.value)
if node.lft != None:
myqueue.append(node.lft)
if node.rgt != None:
myqueue.append(node.rgt)
总结:
- 二叉树的遍历可以分为两种，即广度优先遍历和深度优先遍历。
- 广度优先遍历如层次遍历，按照一度优先、二度优先…的顺序进行逐层遍历。
- 深度优先遍历如前序、中序、后序遍历。
- 广度优先一般使用队列来实现，而深度优先则使用递归或栈来实现，因为大部分情况下栈可以实现递归。