英文:
What is the problem with this InOrder Traversal of Binary Tree?
问题
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;
BinaryTree bn = new BinaryTree();
bn.inOrderTraversal(one);
}
}
英文:
I implemented BinaryTree using java and tried to implement InOrder Traversal. I dry run the code on the copy in that case it works well but when I am running it on my IDE I am getting Infinite Loop. But why?
Please help.
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);
}
}
答案1
得分: 1
你的代码以Node root等于one开始。在one的左侧是two，在two的左侧是four。在进入else条件之前，你的遍历将two然后four推入堆栈。然后你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);
}
英文:
Your code starts with Node root equal to one. To the left of one is two, and to the left of two is four. Your traversal pushes two then four to the stack before the else condition is taken. Then you pop four, and since four has nothing on the right your while loop starts over. But the top of the stack is now two. To the left of two is still four, so you push four on the stack and thus your infinite loop starts.
You need a way to indicate Nodes that have already been visited. If you truly must use a stack, you should add a new attribute to your Node class such as private boolean visited and initialize it to false. After each temp = stack.pop() you would then need to set temp.visited = True, and only push onto the stack Nodes that have not been visited. Such as this:
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);
}
}
}
}
A much simpler solution is to use recursion:
public void inOrderTraveralRecursive(Node node) {
if (node == null) {
return;
}
inOrderTraveralRecursive(node.left);
System.out.print(node.data + " ");
inOrderTraveralRecursive(node.right);
}
答案2
得分: 0
为了解决上述问题，我们可以在这里使用队列和栈来进行实现。
public void 中序遍历(Node 根节点) {
栈<Node> 栈 = new 栈<>();
队列<Node> 输出 = new 队列<>();
Node 临时 = 根节点;
栈.push(根节点);
while (!栈.isEmpty()) {
临时 = 栈.peek();
if (临时.left != null && !临时.left.visited) {
栈.push(临时.left);
} else {
临时 = 栈.pop();
临时.visited = true;
输出.offer(临时);
if (临时.right != null && !临时.right.visited) {
栈.push(临时.right);
}
}
}
while(!输出.isEmpty())
{
Node 临时节点 = 输出.poll();
System.out.print(临时节点.data+" ");
临时节点.visited=false;
}
}
这是正确的解决方案。
英文:
To solve the above-mentioned problems we can do the implementation using a queue and a stack here.
public void inOrderTraversal(Node root) {
Stack<Node> stack = new Stack<>();
Queue<Node> out = new LinkedList<>();
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;
out.offer(temp);
if (temp.right != null && !temp.right.visited) {
stack.push(temp.right);
}
}
}
while(!out.isEmpty())
{
Node tempo = out.poll();
System.out.print(tempo.data+" ");
tempo.visited=false;
}
}
This is the proper solution.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论