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