非递归实现中、后序遍历

来源：1-11 二分搜索树前序遍历的非递归实现

慕UI4021841

2020-09-18 16:48:05

根据bobo老师上一节课的分析，通过栈完全可以实现非递归的中、后序遍历

// 二叉树的中序遍历   通过栈的非递归实现
public void inOrder() {
   Stack<Node> stack = new Stack<>();
   stack.push(root);
   Node left = root.left;
   while (left!= null){
       stack.push(left);
       left = left.left;
   }

   // 先把左边全部节点压入栈
   while (!stack.isEmpty()){
       Node inCul = stack.pop();
       System.out.print(inCul.e+"\t");
       if (inCul.right!=null){
           stack.push(inCul.right);
           Node temp = inCul.right.left;
           while (temp!= null){
               stack.push(temp);
               temp = temp.left;
           }
       }
   }

}

// 二叉树的后序遍历   通过栈的非递归实现
public void postOrder() {
   Stack<Node> stack = new Stack<>();
   stack.push(root);
   Node left = root.left;
   // 先把左边全部节点压入栈
   while (left!= null){
       stack.push(left);
       left = left.left;
   }
   while (!stack.isEmpty()){
       Node inCul = stack.pop();
       if (inCul.right!=null){
           stack.push(new Node(inCul.e));//和中序遍历不同的是，这里再把当前incul压入栈
           stack.push(inCul.right);
           Node temp = inCul.right.left;
           while (temp!= null){
               stack.push(temp);
               temp = temp.left;
           }
       }else {
           System.out.print(inCul.e+"\t");
       }
   }

}

写回答

1回答

慕UI4021841

提问者

2020-09-18

结合bobo老师的分析，感觉算法真的好简单，感谢！@bobo老师

h04_

hpre class="brush:bash;toolbar:false">func postorderFor(node *Node) { // 初始化一个栈 stack := list.New() stack.PushBack(node) // 拿到根节点的左孩子节点 leftChild := node.left // 根节点以及它左子树的最左边的左孩子全部入栈 for leftChild != nil { stack.PushBack(leftChild) leftChild = leftChild.left } var prev *Node for stack.Len() != 0 { // 拿到栈顶的元素 top := stack.Back() node := top.Value.(*Node) // 类型断言，相当于是拿到了栈顶的这个node stack.Remove(top) // 出栈 // 当node没有右孩子或者 node的右孩子已经被处理过了 if node.right == nil || node.right == prev { fmt.Println(node.e) prev = node } else { stack.PushBack(node) stack.PushBack(node.right) // 拿到node.right的左孩子 tmpLeftChild := node.right.left for tmpLeftChild != nil { stack.PushBack(tmpLeftChild) tmpLeftChild = tmpLeftChild.left } } } }

解决了，得有一个变量要记录这个node的右孩子是否已经被处理过

h023-07-30

共4条回复

算法与数据结构

波波老师5年集大成之作，算法与数据结构系统学习，考试、面试、竞赛通用

2627 学习 · 1090 问题

查看课程

相似问题

老师您好，请问层序遍历的递归写法是怎样的？

回答 1

二分搜索树的中序和后序是否也算深度优先遍历

回答 1

关于非递归的疑问

回答 1

中序遍历

回答 1

层序遍历的应用

回答 1

打开慕课网App查看更多内容