0

I was trying to write a simple piece of code to traverse a binary search tree with inorder traversal.I was able to right the insertion code perfectly as the debugger showed a tree exactly like I wanted.But my recursive traversal isnt giving out the correct results.Here's a screenshot of my debugger:

Left Subtree followed by Right subtree

Left

Right Subtree

which corresponds to the following visualized tree:

Binary Tree

Instead of printing out all nodes,it just prints the first element(39) in an infinite loop. Here's my code: Main.java

public class Main {

public static void main(String[] args) {
   BinaryTree binaryTree = new BinaryTree();
    binaryTree.add(50);
    binaryTree.add(40);
    binaryTree.add(39);
    binaryTree.add(42);
    binaryTree.add(41);
    binaryTree.add(43);
    binaryTree.add(55);
    binaryTree.add(65);
    binaryTree.add(60);
    binaryTree.inOrderTraversal(binaryTree.root);
}
}

Node.java

public class Node {
int data;
Node left;
Node right;
Node parent;


public Node(int d)
 {
   data = d;
   left = null;
   right = null;
 }
}

BinaryTree.java

public class BinaryTree {
Node root = null;
public void add(int d)
{
    Node newNode =  new Node(d);
    if(root!=null)
    {


        Node futureParent = root;
        while(true)
        {
        if(newNode.data < futureParent.data)      //going left
        {
            if(futureParent.left == null)
            {
                futureParent.left = newNode;
                newNode.parent = futureParent;
                break;
            }
            futureParent = futureParent.left;

        }
        else
        {
            if(futureParent.right == null)
            {
                futureParent.right = newNode;
                newNode.parent = futureParent;
                break;
            }
            futureParent = futureParent.right;
        }

        }

    }
    else
    {
        root = newNode;
    }
}
public void inOrderTraversal(Node node)
{
    while(node!=null)
    {
    inOrderTraversal(node.left);
    System.out.println(node.data);
    inOrderTraversal(node.right);
    }
}
}
4

2 回答 2

2

您不需要 inOrderTraversal() 中的 while() 循环。这是一个递归调用。它导致了无限循环。

但是，您确实需要一些东西来停止递归。仅当节点不为空时才递归。

public void inOrderTraversal(Node node) {
    if(node==null) return;

    inOrderTraversal(node.left);
    System.out.println(node.value);
    inOrderTraversal(node.right);
}
于 2014-02-27T05:02:20.777 回答
0

当你使用递归时，你应该记住基本情况、简化问题和一般解决方案。

这里的基本情况是：如果 node == null，则停止递归。减少的问题是：应该能够访问任何单个左/父/右节点一般解决方案是：访问左，访问节点，访问右。

所以，你的代码应该是：

public void lnrTraverse(Node node) {
    //if (node == null) return; //This is not needed. Valid only if it an empty tree
    if (node.left != null) {
        lnrTraversal(node.left);
    }
    System.out.println(node);
    if (node.right != null) {
        lnrTraversal(node.right);
    }
}
于 2014-02-27T05:22:04.920 回答