java - 二叉搜索树递归错误及运算轨迹

Question

我的工作是展示插入随机生成的 key (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 个节点。

其次，您的添加方法不是递归的。您将根设置为范围内的最大值，因此 while 循环的第一次迭代将始终以终止(返回)结束，因此添加永远不会向下遍历到树的第二层以下。

希望这可以帮助您找到正确的方向。