在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()方法检索根节点时.它返回root的子而不是我传入的实际根节点.

这是使用它的一个例子

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.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方法中,这当然没有多大意义.