在java中获取二进制搜索树的根

Question

我用java创建了一个二进制搜索树，允许用户向该树添加节点

这是我在java中实现的二叉树，它在创建时接受根节点，然后自动计算出它应该将子节点添加到树的左侧或右侧。

public class BinarySearchTree {

    Node root = null;
    public BinarySearchTree(Node root){
        this.root =root;
    }
    public void add(int data){
        Node newNode = new Node(data);
        if(this.root ==null){
            newNode =this.root;
        }
        if(data>this.root.data){
            addRight(root,newNode);
        }

        if(data<this.root.data){
            addLeft(root,newNode);
        }
    }

    public Node getRoot(){
       return  this.root;
    }

    private void addLeft(Node root, Node newNode) {
        if(root.leftChild == null){
            root.leftChild = newNode;
        }
        else {
            this.root = this.root.leftChild;
            add(newNode.data);
        }
    }

    private void addRight(Node root,Node newNode) {
        if (root.rightChild == null){
            root.rightChild = newNode;
        }
        else {
            this.root = this.root.rightChild;
            add(newNode.data);
        }
    }

}

但是当我尝试使用getRoot（）方法检索根节点时。它返回根的子节点，而不是我传入的实际根节点。

这是一个使用它的例子

TreeHight treeHight = new TreeHight();
        Node root = new Node(100);
        BinarySearchTree unbalance = new BinarySearchTree(root);
        unbalance.add(200);
        unbalance.add(50);
        unbalance.add(250);
        unbalance.add(350);

当我尝试获取根节点时，它给我250作为第一个节点，而不是100。

如何检索此树的根节点？




Answer 1

您正在编辑这一行的根：

this.root = this.root.rightChild;

我认为您应该像这样递归地将新节点添加到右侧：

    else {
        addRight(this.root.rightChild, newNode);
    }

请注意，我认为您在这个块“add方法”中遇到了问题：

   if(this.root ==null){
        newNode =this.root; // it should be this.root = newNode;
    }

Answer 2

您可以在代码中编写：

 this.root = this.root.leftChild;
 add(newNode.data);

这大概是错误的行为吧？

您应该将其改写为：

add(this.root.leftChild,newNode);

然后定义一个递归方法，该方法查看该项是否应存储在子轨迹的左/右。

类似的东西：

public void add(Node subroot, int data){
    if(data > subroot.data){
        addRight(subroot,data);
    }
    else if(data < subroot.data){
        addLeft(subroot,newNode);
    }
}

private void addLeft(Node subroot, int data) {
    if(subroot.leftChild == null){
        subroot.leftChild = new Node(data);
    }
    else {
        add(subroot.leftChild,data);
    }
}

private void addRight(Node subroot, int data) {
    if(subroot.rightChild == null){
        subroot.rightChild = new Node(data);
    }
    else {
        add(subroot.rightChild,data);
    }
}

然后，add方法是：

public void add(int data){
    if(this.root == null){
        this.root = new Node(data);
    }
    else {
        this.add(this.root,data);
    }
}

我认为二叉树的一个不变量是根保持不变。顺便说一下，addRight也是如此。

最后你还写道：

newNode =this.root;

在您的add方法中，这当然没有多大意义。