java - 创建不带数组的二叉搜索树

Question

所以我已经成功地用 Java 使用数组创建了 BST，但是一位 friend 告诉我他已经在不使用数组的情况下完成了它。我大致知道他是如何做到的，这里是一个例子(我省略了构造函数、getter 和 setter):

class TreeNode implements Comparable<TreeNode>
{
    private int value;
    private TreeNode leftChild;
    private TreeNode rightChild;
    private TreeNode parent;

正如您所看到的，您可以仅链接左侧和右侧节点，但这让我了解了添加方法的工作原理。到目前为止，我刚刚初始化了一个新对象，如下所示:

public void add(Comparable c)
{
    TreeNode node = new TreeNode(c);
}

但是这让我想知道如果我无法像在数组中一样访问它，我如何链接到前一个对象？每次我去链接一个对象时，我最终都会添加一个新对象。我对如何实现这个方法有点困惑，你会怎么做？

Answer 1

我很确定你必须做的事情与此类似:

class TreeNode<T extends Comparable<T>> {
    private T value;
    private TreeNode<T> left;
    private TreeNode<T> right;
    private TreeNode<T> parent;

    public TreeNode(TreeNode parent, T value) {
        this.parent = parent;
        this.value = value;
    }

    public TreeNode<T> add(T t) {
        if(t.compareTo(value) < 0) {
            if(left == null) {
                left = new TreeNode(this, t);
                return left;
            } else {
                return left.add(t);
            }
        } else {
            if(right == null) {
                right = new TreeNode(this, t);
                return right;
            } else {
                return right.add(t);
            }
        }
    }

    public boolean find(T t) {
        if(t.equals(value)) {
            return true;
        } else {
            if(t.compareTo(value) < 0) {
                if(left == null) {
                    return false;
                } else {
                    return left.find(t);
                }
            } else {
                if(right == null) {
                    return false;
                } else {
                    return right.find(t);
                }
            }
        }
    }
}

class Tree<T extends Comparable<T>> {
    private TreeNode<T> topElement;

    public TreeNode<T> add(T t) {
        if(topElement == null) {
            topElement = new TreeNode(null, t);
            return topElement;
        } else {
            return topElement.add(t);
        }
    }

    public boolean find(T t) {
        if(topElement == null) {
            return false;
        } else {
            return topElement.find(t);
        }
    }
}