我如何在 java 中的二叉搜索树的根部插入一个项目？

Question

我想在二叉搜索树的根中插入一个新项。下面，我介绍了这个方法和左右的帮助方法 rotation.I 认为这是一个错误，因为当（使用下面的方法）尝试用中序遍历打印树时，它就停在了新根，因此它不会打印新根和根右侧的项目。在以正常方式将项目插入树后，我检查了打印方法并且它有效，所以我认为那里没有问题。

public class ST {

    private TreeNode root;

    public ST() {
        this.size = 0;
        this.root = null;
    }

    public void insert_at_root(Suspect item) {
        insert_at_rootRec(item, this.root);
    }

    private TreeNode insert_at_rootRec(Suspect item, TreeNode head) {
        if (head == null)
            return new TreeNode(item);
        if (item.key() < head.item.key()) {
            head.left = insert_at_rootRec(item, head.left);
            head = rotateRight(head);
        } else {
            head.right = insert_at_rootRec(item, head.right);
            head = rotateLeft(head);
        }
        return head;

    }

    private TreeNode rotateRight(TreeNode h) {
        TreeNode x = h.left;
        h.left = x.right;
        x.right = h;
        return x;
    }

    private TreeNode rotateLeft(TreeNode h) {
        TreeNode x = h.right;
        h.right = x.left;
        x.left = h;
        return x;
    }



    public void printTreeByAFM(PrintStream stream) {
        printTreeByAFMRec(this.root, stream);
    }

    private void printTreeByAFMRec(TreeNode root, PrintStream stream) {
        if (root == null)
            return;
        printTreeByAFMRec(root.left, stream);
        stream.println(root.item);
        printTreeByAFMRec(root.right, stream);
    }

}

Answer 1

您应该将计算出的新树保存在 insert_at_root:

public void insert_at_root(Suspect item) {
    root = insert_at_rootRec(item, this.root);
}

您没有对 insert_at_rootRec() 的 return 做任何事情，所以在您计算出新树后，它就进入垃圾收集器。

我如何在 java 中的二叉搜索树的根部插入一个项目？

How can i insert an item at root in a binary search tree in java?

java

binary-search-tree