class
Node(
object
):
def
__init__
(
self
, data
=
None
, left
=
None
, right
=
None
):
self
.data
=
data
self
.left
=
left
self
.right
=
right
class
BTree(
object
):
def
__init__
(
self
, root
=
None
):
self
.root
=
root
def
is_empty(
self
):
if
self
.root
is
None
:
return
True
else
:
return
False
# 先序遍历(递归,recursion)
def
pre_order(
self
, node):
if
node
is
None
:
return
print
(node.data)
self
.pre_order(node.left)
self
.pre_order(node.right)
# 中序遍历(递归)
def
in_order(
self
, node):
if
node
is
None
:
return
self
.in_order(node.left)
print
(node.data)
self
.in_order(node.right)
# 后序遍历(递归)
def
post_order(
self
, node):
if
node
is
None
:
return
self
.post_order(node.left)
self
.post_order(node.right)
print
(node.data)
# 先序遍历(非递归)
def
preorder(
self
, node):
stack
=
[]
while
node
or
stack:
if
node
is
not
None
:
print
(node.data) stack.append(node) node
=
node.left
else
: node
=
stack.pop() node
=
node.right
# 中序遍历(非递归)
def
inorder(
self
, node):
stack
=
[]
while
node
or
stack:
if
node: stack.append(node) node
=
node.left
else
: node
=
stack.pop()
print
(node.data) node
=
node.right
# 后序遍历(非递归)
def
postorder(
self
, node):
stack
=
[] queue
=
[] queue.append(node)
while
queue: node
=
queue.pop()
if
node.left: queue.append(node.left)
if
node.right: queue.append(node.right) stack.append(node)
while
stack:
print
(stack.pop().data)
# 水平遍历
def
levelorder(
self
, node):
if
node
is
None
:
return
queue
=
[node]
while
queue: node
=
queue.pop(
0
)
print
(node.data)
if
node.left: queue.append(node.left)
if
node.right: queue.append(node.right)
# 根据前序遍历和中序遍历,求后序遍历
def
findTree(
self
, preList, midList, afterList):
'''
preList = list('DBACEGF')
midList = list('ABCDEFG')
afterList = ['A', 'C', 'B', 'F', 'G', 'E', 'D']
'''
if
len
(preList)
==
0
:
return
if
len
(preList)
==
1
: afterList.append(preList[
0
])
return
root
=
preList[
0
] n
=
midList.index(root)
self
.findTree(preList[
1
:n
+1
], midList[:n], afterList)
self
.findTree(preList[n
+1
:], midList[n
+1
:], afterList) afterList.append(root)
#return afterList
'''
n1 = Node(data=1)
n2 = Node(2,n1,None)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5,n3,n4)
n6 = Node(6,n2,n5)
n7 = Node(7,n6,None)
n8 = Node(8)
root = Node(0,n7,n8)
'''
root
=
Node(
0
, Node(
7
, Node(
6
, Node(
2
, Node(
1
)), Node(
5
, Node(
3
), Node(
4
)))), Node(
8
)) bt
=
BTree(root)
print
(
'pre_order......'
)
print
(bt.pre_order(bt.root))
print
(
'in_order......'
)
print
(bt.in_order(bt.root))
print
(
'post_order.....'
)
print
(bt.post_order(bt.root)) preList
=
list
(
'DBACEGF'
) midList
=
list
(
'ABCDEFG'
) afterList
=
[] bt.findTree(preList, midList, afterList)
print(afterList)
本文转自罗兵博客园博客,原文链接:http://www.cnblogs.com/hhh5460/p/5887332.html,如需转载请自行联系原作者