二叉树遍历方式分为深度优先搜索和宽度优先搜索
- 下面先写一个先根序访问，也就是深度优先搜索
def preorder(t, proc)
if t is None:
return
proc(t.data)
preorder(t.left)
preorder(t.right)
很简单，递归调用，先处理根数据再处理左子树，右子树。中根序和后根序与此类似，调换一下数据处理顺序就可以了
- 宽度优先搜索需要一个队列，是水平访问，要每一层访问完了再访问下一层，下面是实现：
from SQueue import *
def levelorder(t,proc):
qu = SQueue()
qu.enqueue(t)
while not qu.is_empty():
n = qu.dequeue()
if t is None:
continue
qu.enqueue(t.left)
qu.enqueue(t.right)
proc(t.data)
后面还要分析非递归的遍历，分析算法复杂度
网友评论