java - 这个二叉树的InOrder遍历有什么问题?
问题描述
我使用 java 实现了 BinaryTree 并尝试实现 InOrder Traversal。在这种情况下,我在副本上干运行代码它运行良好,但是当我在我的 IDE 上运行它时,我得到了无限循环。但为什么?请帮忙。
class BinaryTree{
class Node{
private int data;
private Node left, right;
public Node(int data)
{
this.data = data;
left=null;
right=null;}
}
public void inOrderTraversal(Node root)
{
Stack<Node> stack = new Stack<>();
Node temp = root;
stack.push(root);
while(!stack.isEmpty())
{
temp = stack.peek();
if(temp.left!=null)
{
stack.push(temp.left);
}
else
{
temp = stack.pop();
System.out.print(temp.data+" ");
if(temp.right!=null)
{
stack.push(temp.right);
}
}
}
}
public static void main(String[] args) {
Node one = new Node(1);
Node two = new Node (2);
Node three = new Node(3);
Node four = new Node(4);
Node five = new Node(5);
Node six = new Node(6);
one.left = two;
one.right = three;
two.left = four;
two.right = five;
three.left = six
BinaryTrees bn = new BinaryTrees();
bn.inOrderTraversal(one);
}
}
解决方案
您的代码以Node root
等于开头one
。在one
is的左侧,在istwo
的左侧。在条件被采用之前,您的遍历将推入堆栈。然后你,因为右边没有任何东西,你的循环重新开始。但是现在堆栈的顶部是. 在is still的左侧,因此您推入堆栈,从而开始无限循环。two
four
two
four
else
pop
four
four
while
two
two
four
four
您需要一种方法来指示已经访问过的节点。如果您确实必须使用堆栈,则应向 Node 类添加一个新属性,例如private boolean visited
并将其初始化为false
. 在每个之后,temp = stack.pop()
您需要设置temp.visited = True
,并且只将未访问的节点推送到堆栈上。比如这样:
class Node {
private int data;
private Node left, right;
private boolean visited;
public Node(int data) {
this.data = data;
left = null;
right = null;
visited = false;
}
}
public void inOrderTraversal(Node root) {
Stack<Node> stack = new Stack<>();
Node temp = root;
stack.push(root);
while(!stack.isEmpty()) {
temp = stack.peek();
if(temp.left != null && !temp.left.visited) {
stack.push(temp.left);
}
else {
temp = stack.pop();
temp.visited = true;
System.out.print(temp.data + " ");
if(temp.right != null && !temp.right.visited) {
stack.push(temp.right);
}
}
}
}
一个更简单的解决方案是使用递归:
public void inOrderTraveralRecursive(Node node) {
if (node == null) {
return;
}
inOrderTraveralRecursive(node.left);
System.out.print(node.data + " ");
inOrderTraveralRecursive(node.right);
}
推荐阅读
- reactjs - React Hook useEffect :使用 axios 和 async await 获取数据 .api 调用连续相同的 api
- scala - 如何在 Scala SPARK 中的 groupBy 之后在 agg() 函数中找到分位数
- typescript - Typescript - 具有返回类型的方法继承
- java - 出于代码覆盖目的,通过被测公共方法模拟特定的私有方法调用
- git - 将多个 git diff 输出文件合并为一个统一文件
- c++ - cmake add_library 不初始化静态全局变量
- directx - 警告 X3557:循环仅执行 0 次迭代,强制循环展开
- html - 什么是 HTML 模块?
- google-dl-platform - 深度学习 VM 无法通过 UI 部署 - 找不到图像资源 - 图像 url 中的错字
- javascript - 如何在 mouseenter() 之前执行 click()?