二进制搜索树,inorder方法迭代不起作用

Question

我目前正在大学学习数据结构课程,我们正在学习使用链接列表的二叉搜索树.我们已经递归地检查了inOrder方法,但我想尝试迭代地执行该方法.经过一些研究,我意识到我必须使用堆栈,因为我遍历树.我能够到达树的最左侧的尽头,但是在树上移动是我遇到麻烦的地方.我已经尝试了我的代码的各种版本,但我最后得到一个nil指针异常或它打印失序.

public void inOrder(){                
    // implement this method using non-recursive solution
   if(m_root==null){
      return;
   }
   Stack<BSTNode> myStack= new Stack<BSTNode>();
   BSTNode current=m_root;
   while (current!= null){
      myStack.push(current);
      current=current.getLeft();
   }
   while (current!=null&& !myStack.isEmpty()){
      current=myStack.peek();
      System.out.print(current.getInfo()+" ");
      myStack.pop();
      if(current.getRight()!=null){
          myStack.push(current);
      }

   }

}

Answer 1

从我所看到的,你的代码在第二个while循环中存在一些问题.你的想法是正确的方向,但有一些逻辑错误.你拥有的条件是正确的,但不应该在一起,它们应该是分开的.下面的代码实现了您的目标.

public void inOrder(){                
    // implement this method using non-recursive solution
   if(m_root==null){
      return;
   }
   Stack<BSTNode> myStack= new Stack<BSTNode>();
   BSTNode current=m_root;
   while (current!= null){
      myStack.push(current);
      current=current.getLeft();
   }
   while (!myStack.isEmpty()){
      current=(BSTNode)myStack.pop();
      System.out.print(current.getInfo()+" ");
      if(current.getRight() != null){
         current=current.getRight();
         while (current!= null){
            myStack.push(current);
            current=current.getLeft();
         }
      }
   }

}