Python实现二叉树的递归非递归遍历

Contents
  1. 先序遍历
    1. 递归写法
    2. 非递归写法
  2. 中序遍历
    1. 递归写法
    2. 非递归写法
  3. 后序遍历
    1. 递归写法
    2. 非递归写法
  4. 层序遍历

说起二叉树的遍历,大学里讲的是递归算法,大多数人首先想到也是递归算法。但也应该学学非递归算法实现二叉树遍历。二叉树的非递归算法需要用到辅助栈,算法着实巧妙,令人脑洞大开。

本文定义的二叉树结构如下:

1
2
3
4
5
class BinNode():
def __init__( self, val ):
self.lchild = None
self.rchild = None
self.val = val

先序遍历

递归写法

1
2
3
4
5
6
def preOrder(self, root):
if root == None:
return
print root.val
self.preOrder(root.lchild)
self.preOrder(root.rchild)

非递归写法

preOrder每次都将遇到的节点压入栈,当左子树遍历完毕后才从栈中弹出最后一个访问的节点,访问其右子树。在同一层中,不可能同时有两个节点压入栈,因此栈的大小空间为O(h),h为二叉树高度。时间方面,每个节点都被压入栈一次,弹出栈一次,访问一次,复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def preOrder(self, root):
if root == None:
return
myStack = []
node = root
while node or myStack:
while node:
# 从根节点开始,一直找它的左子树
print node.val
myStack.append(node)
node = node.lchild
# while结束表示当前节点node为空,即前一个节点没有左子树了
node = myStack.pop()
# 开始查看它的右子树
node = node.rchild

中序遍历

递归写法

1
2
3
4
5
6
def inOrder(self, root):
if root == None:
return
self.inOrder(root.lchild)
print root.val
self.inOrder(root.rchild)

非递归写法

根据上面的先序遍历,可以类似的构造出中序遍历。仔细想一下,只有第一种方法改过来时最方便的。需要的改动仅仅调换一下节点访问的次序,先序是先访问,再入栈;而中序则是先入栈,弹栈后再访问。代码如下。时间复杂度与空间复杂度同先序一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def inOrder(self, root):
if root == None:
return
myStack = []
node = root
while node or myStack:
while node:
# 从根节点开始,一直找它的左子树
myStack.append(node)
node = node.lchild
# while结束表示当前节点node为空,即前一个节点没有左子树了
node = myStack.pop()
print node.val
# 开始查看它的右子树
node = node.rchild

后序遍历

递归写法

1
2
3
4
5
6
def postOrder(self, root):
if root == None:
return
self.postOrder(root.lchild)
self.postOrder(root.rchild)
print root.val

非递归写法

从直觉上来说,后序遍历对比中序遍历难度要增大很多。因为中序遍历节点序列有一点的连续性,而后续遍历则感觉有一定的跳跃性。先左,再右,最后才中间节点;访问左子树后,需要跳转到右子树,右子树访问完毕了再回溯至根节点并访问之,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def later_stack(self, root):
if root == None:
return
myStack1 = []
myStack2 = []
node = root
myStack1.append(node)
while myStack1:
# 这个while循环的功能是找出后序遍历的逆序,存在myStack2里面
node = myStack1.pop()
if node.lchild:
myStack1.append(node.lchild)
if node.rchild:
myStack1.append(node.rchild)
myStack2.append(node)
while myStack2:
# 将myStack2中的元素出栈,即为后序遍历次序
print myStack2.pop().val

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
def levelOrder(self, root):
if root == None:
return
myQueue = []
node = root
myQueue.append(node)
while myQueue:
node = myQueue.pop(0)
print node.val
if node.lchild != None:
myQueue.append(node.lchild)
if node.rchild != None:
myQueue.append(node.rchild)