如何在不使用Node类的情况下添加到二叉搜索树中

Question

对于类，我需要创建自己的二进制搜索树实现，包括search，add，remove和toString方法，但是如果不先添加，就无法尝试这些方法。我不允许编写或使用节点类。我树的每个节点都应该是BinarySearchTree类的实例。我无法弄清楚如何在没有典型节点的情况下遍历树。这是我的第一部分代码：

public class BinarySearchTree<E extends Comparable<E>> implements BinarySearchTreeInterface<E> {
    E value;
    BinarySearchTree<E> parent;
    BinarySearchTree<E> left;
    BinarySearchTree<E> right;
    static String draw;

    public BinarySearchTree() {
        value = null;
        parent = null;
        left = null;
        right = null;
    }

    @Override
    public void add(E item) {
        if (isRoot() && value == null) {
            value = item;

        } else if (value.compareTo(item) > 0) {
            if (right != null) {
                add(right.value);
            } else {
                BinarySearchTree<E> newNode = new BinarySearchTree<E>();
                newNode.value = item;
                newNode.right = newNode;    
            }
        }else if (value.compareTo(item) < 0) {
            if (left != null) {
                add(left.value);
            }
          } else {
            BinarySearchTree<E> newNode = new BinarySearchTree<E>();
            newNode.value = item;
            newNode.left = newNode;
        }
    }

这似乎只增加了5的根值。我认为这与不将新的“节点”连接到父级或构造函数有关。我在不使用节点类的情况下努力遍历树并连接“节点”。

Answer 1

以这种方式看...二叉树的每个节点本身就是一棵二叉树。

[如果您将两者视为等效，则您的BinarySearchTree类实际上是一个Node类...它只是没有命名为“ Node”。

每次使用类Node的对象时，只需将其声明为BinarySearchTree。

而不是具有：

Node left;
Node right;

您将拥有：

BinarySearchTree left;
BinarySearchTree right;

顺便说一下，您所缺少的是这个：

this.left = newNode;

或

this.right = newNode;

这表示BinarySearchTree正在设置自身的left或right变量。这就是this的意思。

事实证明，除了在上下文不明确的某些情况下，甚至this都不是必需的。就您而言，您可以说：

left = newNode;

或

right = newNode;