将值插入二叉搜索树时出现问题

Question

我想创建一个二叉搜索树，但我遇到一条错误消息。

这是我的代码的相关部分：

1类（插入部分）：

public class Tree{
    
    public insert(Item item) {
        if (look != null) {
            System.out.println("Number already exists");
            System.exit(0);
        } else {
            root = insertAsRoot(item, root);
        }
    }
    
    private Node insertAsRoot(Itemitem, TreeNode h) {
        if (h == null) {
            Node node = new Node (item);
            return node;
        } 
        if (Math.random()*(h.N+1) < 1.0) {
            h = insertT(item, h);
        }
            
        if (item.key() < h.item.key()) {
            h.setLeft(insertAsRoot(item, h.getLeft()));
        } else {
            h.setRight(insertAsRoot(item, h.getRight()));
        }
        h.N++;
        return h;
    }
    
    private Node  insertT(Item item, Node h) {
        if (item.key() < h.item.key()) {
            h.setLeft(insertT(item, h.getLeft())); 
            h = rotR(h);
            } 
        else {
            h.setRight(insertT(item, h.getRight()));
            h = rotL(h); 
        }
        return h;
    }
    
    private Node rotR(Node h) {      
        Node x = h.getLeft();
        h.setLeft(x.getRight()); 
        x.setRight(h); 
        return x;
    }
    
    private Node rotL(Node h) {      
        Node x = h.getRight();
        h.right = x.left;
        x.left = h;
        return x;
    }

我可以在树中插入第一个节点（成为根节点），但是在尝试插入第二个节点后，会出现此消息：

“无法读取文件项，因为“h”为空”

如果有人能想到这个问题，请告诉我，我被困住了！

Answer 1

错误的直接原因是您的

insertT

函数执行递归而不检查基本情况，即当

h

为

null

时。在这种情况下，您应该实际创建节点并返回它。

    private TreeNode insertT(int item, TreeNode h) {
        if (h == null) { // Base case!
            return new TreeNode(item);  // Must create the node for the item
        }
        if (item.key() < h.item.key()) {
            h.setLeft(insertT(item, h.getLeft()));
            h = rotR(h);
        }
        else {
            h.setRight(insertT(item, h.getRight()));
            h = rotL(h); 
        }
        return h;
    }

与错误无关，但

insertAsRoot

似乎随机选择使用

insertT

算法插入新节点，以便新节点最终位于根，OR插入节点在其他地方，使用

insertAsRoot

的递归调用。但你的代码可能会同时做两者，而这并不是有意的。

所以将第二个选项放在

else

块中：

        if (Math.random()*(h.N+1) < 1.0) {
            h = insertT(item, h);
        } else if (item.key() < h.item.key()) {
//        ^^^^
            h.setLeft(insertAsRoot(item, h.getLeft()));
        } else {
            h.setRight(insertAsRoot(item, h.getRight()));
        }

N

字段的维护需要更多关注。我认为您还没有关注这一点，因为该字段在轮换期间需要更新，并从

insertT

回溯，...等。我将把它留给您进一步检查。