java - 作业: Java BST without nodes (BST of BSTs)

Question

注意:BST - 二叉搜索树(缩写)

正如标题所说， 这是一项家庭作业，所以我不是在寻找答案。 相反，我只需要一个正确方向的点。

对于作业， 我应该创建一个 BST 类，它直接定义为最多包含 2 个 BST 子级的数据 (即不使用辅助节点类)。

我得到了一个用 JavaDocs 注释的类，并且应该填写 TODOS。

至少在开始时让我困惑的是在类(class)进行到一半时实现插入方法。

import java.util.Comparator;
import java.util.ArrayList;
import java.util.List;

/**
 * A class to implement the Binary Search Tree data structure.
 * The structure is generic in the type of Objects it contains.
 * @param <T> the type of the contained elements this structure is to hold
 */
public class BinarySearchTree<T> {
private Comparator<T> comparator;
private T data;
private BinarySearchTree<T> left;
private BinarySearchTree<T> right;

/**
 * Constructs an empty BST with a Comparator
 * @param comp the Comparator to use to impose an ordering on instances of T
 */
public BinarySearchTree(Comparator<T> comp) {
    this.comparator = comp;
}

/**
 * Constructs a BST with data and a Comparator
 * @param data the data this BST should hold
 * @param comp the Comparator to use to impose an ordering on instances of T
 */
public BinarySearchTree(T data, Comparator<T> comp) {
    this.data = data;
    this.comparator = comp;
}

/**
 * Inserts an element into this BST
 * @param element the element to insert into this BST
 */
public void insert(T element) {
    //TODO
    if(left == null && right == null){
        left = new BinarySearchTree(element, comparator);
    }else{
        /**
         *Do something with the comparator to figure out if the element goes         
         *to left or right?
         */
    }
}

/**
 * Searchs for a given element in this BST
 * @param element the element to search this BST for
 * @return the element in this BST matching the given element, if found,
 *         otherwise null if the given element is not in this BST
 */
public T find(T element) {
    // TODO
}

/**
 * Gathers all the elements of this BST in order
 * @return a List holding the elements in this BST in order
 */
public List<T> getElements() {
    List<T> list = new ArrayList<>();
    // TODO
    return list;
}

/**
 * Pretty prints the contents of this BST in a horizontal tree-like fashion
 */
public void prettyPrint() {
    prettyPrint(0);
}

private void prettyPrint(int indentLevel) {
    // TODO
    // similar to printInOrder from assignment09,
    // but print `indentLevel` amount of spaces before printing data on its own line
    // you may use a for loop to print `indentLevel` amount of spaces
    // each time you recurse, you add to indentLevel
}

/**
 * A main method supplied for any debugging needs
 */
public static void main(String[] args) {
    // Up to you how you use this main method, feel free to change it
    Comparator<Integer> intComp = (i, j) -> i - j; // lambda expression
    BinarySearchTree<Integer> tree = new BinarySearchTree<>(intComp);
    tree.insert(3);
    tree.insert(8);
    tree.insert(1);
    tree.insert(0);
    tree.insert(3);
    tree.insert(9);
    tree.insert(4);
    tree.prettyPrint();
}

}

我觉得我理解它是如何工作的概念，但我不知道如何实现代码。

如果格式不可读或者信息太多而无法分享以获取一点帮助，我对此表示歉意。

Answer 1

BST 类是节点。 首先，确定空元素是否小于或大于非空元素。 要实现插入，您需要执行以下操作:

1) 验证元素参数不为空。如果为空，则不执行任何操作。

2)未完成的代码必须决定在哪里插入元素。

a) 如果其中一个子级为 null，则插入后最终结果是两个子级都不为 null。将新元素与非空元素进行比较；两者中较大的一个是右 child 。

b) 如果两个子元素都不为 null，则确定新元素的放置位置(小于左，使用左。大于左，使用右)并调用该元素的插入。

注意:如果您还没有注意到，这个作业是关于递归的。