数据结构10-树与二叉树及python实现02

东阳的学习记录，坚持就是胜利！

文章目录

后序遍历单栈法双栈法 层次遍历

后序遍历

单栈法

def post_order(bt): """二叉树的后序遍历""" stack = [] p = bt.root r = None while p or stack: if p: stack.append(p) p = p.lchild else: p = stack[len(stack) - 1] if p.rchild and p.rchild != r: # 如果右结点存在，且未被访问过，转向右结点 p = p.rchild stack.append(p) p = p.lchild else: # 不存在右结点，弹出并访问 p = stack.pop() print(p.elem) r = p p = None

双栈法

def post_order_2(bt): """后序遍历""" s1, s2 = [], [] s1.append(bt.root) while s1: p = s1.pop() s2.append(p) if p.lchild: s1.append(p.lchild) if p.rchild: s1.append(p.rchild) while s2: p = s2.pop() print(p.elem)

层次遍历

def level_order(bt): """层次遍历""" q = [] q.append(bt.root) while q: p = q.pop(0) print(p.elem) if p.lchild: q.append(p.lchild) if p.rchild: q.append(p.rchild)