数据结构面试中经常会被问到篇二叉树相关的问题,那么这篇文章会研究下怎么用python来进行二叉树的构建和遍历。

注意:py2中

1
print root.elem,

在py3中要换成

1
print (root.elem,end="  ")

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
# coding:utf-8

# 定义节点类
class Node:
def __init__(self,elem = -1,):
self.elem = elem
self.left = None
self.right = None

# 定义二叉树
class Tree:
def __init__(self):
self.root = Node()
self.myqu = []

# 添加节点
def add(self,elem):
node = Node(elem)
if self.root.elem == -1: # 判断如果是根节点
self.root = node
self.myqu.append(self.root)
else:
treenode = self.myqu[0]
if treenode.left == None:
treenode.left = node
self.myqu.append(treenode.left)
else:
treenode.right = node
self.myqu.append(treenode.right)
self.myqu.pop(0)

# 利用递归实现树的先序遍历
def xianxu(self,root):
if root == None:
return
print root.elem,
self.xianxu(root.left)
self.xianxu(root.right)

# 利用递归实现树的中序遍历
def zhongxu(self,root):
if root == None:
return
self.zhongxu(root.left)
print root.elem,
self.zhongxu(root.right)

# 利用递归实现树的后序遍历
def houxu(self,root):
if root == None:
return
self.houxu(root.left)
self.houxu(root.right)
print root.elem,

# 利用队列实现层次遍历
def cengci(self,root):
if root == None:
return
myq = []
node = root
myq.append(node)
while myq:
node = myq.pop(0)
print node.elem,
if node.left != None:
myq.append(node.left)
if node.right != None:
myq.append(node.right)

# 求树的叶子节点
def getYeJiedian(self,root):
if root == None:
return 0
if root.left == None and root.right == None:
return 1

return self.getYeJiedian(root.left) + self.getYeJiedian(root.right)

# 由先序和中序,还原二叉树
def preMidToHou(self,pre,mid):
if len(pre)==0:
return None
if len(pre)==1:
Node(mid[0])
root = Node(pre[0])
root_index = mid.index(pre[0])
root.left = self.preMidToHou(pre[1:root_index + 1],mid[:root_index])
root.right = self.preMidToHou(pre[root_index + 1:],mid[root_index + 1:])
return root

# 由后序和中序,还原二叉树
def preMidToHou(self,mid,hou):
if len(hou)==0:
return None
if len(hou)==1:
Node(mid[0])
root = Node(hou[-1])
root_index = mid.index(hou[-1])
root.left = self.preMidToHou(mid[:root_index],hou[:root_index])
root.right = self.preMidToHou(mid[root_index + 1:],mid[root_index + 1:])
return root

# 创建一个树,添加节点
tree = Tree()
for i in range(10):
tree.add(i)

print("二叉树的先序遍历:")
print(tree.xianxu(tree.root))

print("二叉树的中序遍历:")
print(tree.zhongxu(tree.root))

print("二叉树的后序遍历:")
print(tree.houxu(tree.root))

print("二叉树的层次遍历")
print(tree.cengci(tree.root))

print("\n二叉树的叶子节点为:")
print(tree.getYeJiedian(tree.root))

print("\n已知二叉树先序遍历和中序遍历,求后序:")
print("先序:")
print(tree.xianxu(tree.root))
print("中序:")
print(tree.zhongxu(tree.root))
print("后序:")
root = tree.preMidToHou([0,1,3,7,8,4,9,2,5,6],[7,3,8,1,9,4,0,5,2,6])
print(tree.houxu(root))

print("\n已知二叉树后序遍历和中序遍历,求前序:")
print("后序:")
print(tree.houxu(tree.root))
print("中序:")
print(tree.zhongxu(tree.root))
print("前序:")
root = tree.preMidToHou([7,3,8,1,9,4,0,5,2,6],[7,8,3,9,4,1,5,6,2,0])
print(tree.xianxu(root))

运行结果为:

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
二叉树的先序遍历:
0 1 3 7 8 4 9 2 5 6 None

二叉树的中序遍历:
7 3 8 1 9 4 0 5 2 6 None

二叉树的后序遍历:
7 8 3 9 4 1 5 6 2 0 None

二叉树的层次遍历
0 1 2 3 4 5 6 7 8 9 None

二叉树的叶子节点为:
5

已知二叉树先序遍历和中序遍历,求后序:
先序:
0 1 3 7 8 4 9 2 5 6 None
中序:
7 3 8 1 9 4 0 5 2 6 None
后序:
1 3 7 8 4 9 0 5 2 6 None

已知二叉树后序遍历和中序遍历,求前序:
后序:
7 8 3 9 4 1 5 6 2 0 None
中序:
7 3 8 1 9 4 0 5 2 6 None
前序:
0 1 3 7 8 4 9 6 2 5 None


打开微信扫一扫,关注微信公众号【搜索与推荐Wiki】