二叉搜索树递归错误和操作跟踪

Question

我的工作是显示插入随机生成的键（0-14012891）的步骤，例如，当值较小时向左插入，当值较大时向右插入。这就是我到目前为止所拥有的一切，我很卡住，任何类型的帮助/指针将不胜感激，我还有另一个错误，我的根14012891在添加每个新的随机生成的数字后一直以递归方式打印，我如何也摆脱这个？谢谢！

Node root;
public void addNode(int key, String name) {
Node newNode = new Node(key, name);
if(root == null) {
    root = newNode;
} else {
    Node focusNode = root;
    Node parent;
    while(true) {
        parent = focusNode;
        if(key < focusNode.key) {
            focusNode = focusNode.leftChild;
            if(focusNode == null) {
                parent.leftChild = newNode;
                return;
            }
            else {
                focusNode = focusNode.rightChild;
                if (focusNode == null) {
                    parent.rightChild = newNode;
                    return;
                }
            }
        }
    }
}
}
public void preOrderTraverseTree(Node focusNode) {
    if (focusNode!=null) {
        System.out.println(focusNode);
        preOrderTraverseTree(focusNode.leftChild);
        preOrderTraverseTree(focusNode.rightChild);
    }
}
public static void main (String[] args) {
    Random rand = new Random(); 
for (int j = 0; j<10; j++) 
{
int pick = rand.nextInt(100);
    CourseWork2 newTree = new CourseWork2();
    newTree.addNode(14012891," Root ");
    newTree.addNode(pick, "");
    newTree.preOrderTraverseTree(newTree.root);
}
}
public class Node {
int key;
String name;
Node leftChild;
Node rightChild;
Node(int key, String name) {
    this.key = key;
    this.name = name;
}
public String toString () {
    return name + " " + key;
}
}
}

Answer 1

因此，首先，您通过您拥有的 for 循环每次迭代创建一个新树，这样它就不会有节点。 然后添加一个根节点和一个从 0-100 的随机数。因此，这样做的预期结果是它将打印出根节点和随机数 10 次。换句话说，你的树永远不会超过2个节点。

其次，您的 add 方法不是递归的。 您将根设置为范围内的最大值，因此通过 while 循环的第一次迭代将始终以终止（返回）结束，因此 Add 永远无法向下遍历到树的第二级以下。

希望这能帮助你朝着正确的方向前进。