首先是三種遍歷的遞歸實現(xiàn)蟀给，思路簡單礼殊，重要的是要清楚每種遍歷的順序：
- 先序遍歷： 根 --》 左子樹 --》右子樹
- 中序遍歷： 左子樹 --》根--》右子樹
- 后序遍歷： 左子樹 --》右子樹 --》根
首先是樹的創(chuàng)建：
image.png
class binaryTree:
def __init__(self, root):
self.key = root
self.left_child = None
self.right_child = None
def insert_left(self, new_node):
if self.left_child == None:
self.left_child = binaryTree(new_node)
else:
t = binaryTree(new_node)
t.left_child = self.left_child
self.left_child = t
def insert_right(self, new_code):
if self.right_child == None:
self.right_child = binaryTree(new_code)
else:
t = binaryTree(new_code)
t.right_child = self.right_child
self.right_child = t
def get_right_child(self):
return self.right_child
def get_left_child(self):
return self.left_child
def set_root_val(self, obj):
self.key = obj
def get_root_val(self):
return self.key
遞歸方法：
def preOrder(root):
if root == None:
return
print root.key,
preOrder(root.left_child)
preOrder(root.right_child)
def inOrder(root):
if root == None:
return
inOrder(root.left_child)
print root.key,
inOrder(root.right_child)
def postOrder(root):
if root == None:
return
postOrder(root.left_child)
postOrder(root.right_child)
print root.key,
層次遍歷：
def cengci(root):
if root == None:
return
stack = []
stack.append(root)
while len(stack):
p = stack[0]
print p.key ,
del stack[0]
if p.left_child:
stack.append(p.left_child)
if p.right_child:
stack.append(p.right_child)
測試：
if __name__ == "__main__":
r = binaryTree('a')
r.insert_left('b')
r.insert_right('c')
l = r.left_child
l.insert_left("d")
l.insert_right("e")
ri = r.right_child
ri.insert_left("f")
ri.insert_right("g")
print "pre: "
preOrder(r)
print "\n"
print "in: "
inOrder(r)
print "\n"
print "post: "
postOrder(r)
image.png
非遞歸方法：
- 先序遍歷：
當p或者棧不為空時循環(huán)，為什么是這個條件（p很可能為None,但如果此時還能回溯的時候语婴，程序就可以繼續(xù)）牍白，首先一直壓入左節(jié)點首有，（對應(yīng)根節(jié)點）并且輸出當前節(jié)點，當直到最左的時候俏橘，回溯（對應(yīng)pop操作）允华，考慮右節(jié)點
def preOrder1(root):
if root == None:
return
p = root
stack = []
while p != None or len(stack):
while p != None:
print p.key,
stack.append(p)
p = p.left_child
if len(stack):
p = stack[-1]
del stack[-1]
p = p.right_child
- 中序遍歷，和前序遍歷有點像寥掐，但是因為根是在中間遍歷靴寂，所以要在出棧時候輸出（相當于根節(jié)點被壓棧了），最后考慮右節(jié)點
def inOrder1(root):
if root == None:
return
p = root
stack = []
while p != None or len(stack):
while p != None:
stack.append(p)
p = p.left_child
if len(stack):
p = stack[-1]
print p.key,
del stack[-1]
p = p.right_child
- 后序遍歷：
左--》右--》根
當左節(jié)點和右節(jié)點不存在時召耘，可以訪問根節(jié)點百炬，或者左節(jié)點或者右節(jié)點已經(jīng)訪問過的時候。
然后先壓棧右節(jié)點污它，然后左節(jié)點剖踊，這樣輸出的時候先左節(jié)點，后右節(jié)點
def postOrder1(root):
if root == None:
return
p = root
stack = []
stack.append(p)
pre = None
while len(stack):
cur = stack[-1]
if (cur.left_child == None and cur.right_child == None) or (pre!=None and (pre == cur.left_child or pre == cur.right_child)):
print cur.key,
del stack[-1]
pre = cur
else:
if cur.right_child != None:
stack.append(cur.right_child)
if cur.left_child != None:
stack.append(cur.left_child)
image.png
