我目前正在大学学习数据结构课程,我们正在学习使用链接列表的二叉搜索树.我们已经递归地检查了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);
}
}
}