首页 > 代码库 > 【二叉树】二叉树的非递归遍历
【二叉树】二叉树的非递归遍历
【题目】不使用递归，对二叉树进行先序、中序和后序遍历
【思路】利用栈
先序：
1. 输出当前结点
2. 把右孩子放到栈中
3. 当前指针指向左孩子
4. 重复1-3，直到叶子结点
5. 如果栈不空，则从栈里POP出一个结点，赋值给当前节点
6. 重复1-5
中序：
1. 如果当前节点不为空，把当前节点PUSH
2. 当前节点指向左孩子
3. 如果当前节点为空，POP，并打印，把右节点设为当前节点
后序
用2个栈
1. 如果当前节点不为空，把当前节点PUSH左栈，并把当前节点指向其左孩子
2. 如果当前节点为空，左栈顶和右栈顶相同，则输出栈顶元素
不相同，则当前节点为左栈的右节点，右栈PUSH左栈顶的元素
【代码】
基本数据结构：
1 class G:2 def evaluate(self, l, r, v):3 self.left = l4 self.right =r5 self.val = v
构建测试数据：
1 tree = [G() for i in xrange(9)] 2 tree[8].evaluate(None, None, 8) 3 tree[7].evaluate(None, None, 7) 4 tree[6].evaluate(None, None, 6) 5 tree[5].evaluate(None, None, 5) 6 tree[4].evaluate(tree[7], tree[8], 4) 7 tree[3].evaluate(None, None, 3) 8 tree[2].evaluate(tree[5], tree[6], 2) 9 tree[1].evaluate(tree[3], tree[4], 1)10 tree[0].evaluate(tree[1], tree[2], 0)
先序遍历：
1 def preOrder(t): 2 p = t 3 stack = [] 4 rslt = [] 5 while p or stack: 6 if p: 7 rslt.append(p.val) 8 stack.append(p.right) 9 p = p.left10 else:11 p = stack.pop()12 print rslt
中序遍历：
1 def inOrder(t): 2 p = t 3 stack = [] 4 rslt = [] 5 while p or stack: 6 if p: 7 stack.append(p) 8 p = p.left 9 else:10 s = stack.pop()11 rslt.append(s.val)12 p = s.right13 print rslt
后序遍历：
1 def postOrder(t): 2 p = t 3 leftStack = [] 4 rightStack = [] 5 rslt = [] 6 while (p or leftStack or rightStack): 7 if p: 8 leftStack.append(p) 9 p = p.left10 elif leftStack and rightStack and leftStack[-1] == rightStack[-1]:11 leftStack.pop().val12 rslt.append(rightStack.pop().val)13 else:14 rightStack.append(leftStack[-1])15 p = leftStack[-1].right16 print rslt
【二叉树】二叉树的非递归遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。