如何在不使用节点的情况下添加到二叉搜索树 class

Question

对于 class，我需要创建自己的二叉搜索树实现，包括搜索、添加、删除和 toString 方法，但如果不先添加，我将无法尝试这些方法。我不允许编写或使用节点 class。我的树的每个节点都应该是 BinarySearchTree class 的一个实例。我不知道如何在没有典型节点的情况下遍历树。这是我的第一部分代码：

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 的根值。我相信这与未将新 "node" 连接到父级或我的构造函数有关。我正在努力遍历树并在不使用节点 class 的情况下连接 "nodes"。

Answer 1

这样看...二叉树的每个节点本身就是一棵二叉树。

如果你认为两者是等价的，那么你的BinarySearchTreeclass实际上是一个Nodeclass...只是没有命名"Node" .

任何时候你想使用 class 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;

如何在不使用节点的情况下添加到二叉搜索树 class

How to add to a Binary Search Tree without using a Node class

java

generics

add

binary-search-tree