通用BST的java实现

Question

您好，我想知道如何设置一个具有私有节点类的面向对象BST类。（两类都是泛型） 到目前为止，我有这个，但我有一些编译错误。解释一下就好了。我复制了这段代码，但我知道有错误需要修复。另外，您将如何设置bst的构造函数

@SuppressWarnings("unchecked")
//public class BinarySearchTree<T extends Comparable<? super T>> {
public class BST<T extends Comparable<T>> implements Iterable<T>
{
    private Node <T> root;
    //  public BST(){
    //      root=null;
    //  }

    private T search(T target, BST <T> p)
    {

        int comp=target.compareTo(p.data);
        T c=target.compareTo(P.data);
        if(comp==0)
            return c;
    }


    private class Node<T extends Comparable<T>> implements Iterable {
        T data;
        Node<T> left, right;

        public Node(T t)
        {
            data=t; 
        }

        @Override
        public Iterator iterator() {
            // TODO Auto-generated method stub
            return null;
        }

        public T search(T target)
        {
            return search(target, root);
        }
    }

    @Override
    public Iterator<T> iterator() {
        // TODO Auto-generated method stub
        return null;
    }


}

Answer 1

默认构造函数应该可以，您最初注释掉的应该可以。您是否有一个特定的用例不能满足您的需求

像这样的。因为Node类是一个私有的内部类，所以它不必是泛型的，而是可以使用其父类中指定的类型，这就是我假定您想要的类型

node类实际上不需要搜索方法，因为它只包含一个值。如果只有一个值，则无需搜索。这也是它不需要迭代器的原因。实际上不需要只迭代一个值

当设计一个抽象数据类型，如BST时，考虑如何使用它是很好的：它应该支持什么操作，又名AKA。它的API。下面的实现支持两个操作：插入和搜索。可能的扩展可能包括删除和/或包含操作

树上的操作通常是递归的。这是因为从根开始，必须遍历内部节点，这些节点本身可以被视为各自子树的根。试着浏览一些插入和搜索的例子，让自己明白为什么它是这样工作的

import java.util.Iterator;

public class BST<T extends Comparable<T>> implements Iterable<T> {
    private Node root;

    public BST(){
        root=null;
    }

    private void insertInternal(T value, Node parent) {
        int comp=value.compareTo(parent.data);
        if(comp < 0) {
            if(parent.left == null) {
                parent.left = new Node(value);
            }
            else {
                insertInternal(value, parent.left);
            }
        }
        else if(comp > 0) {
            if(parent.right == null) {
                parent.right = new Node(value);
            }
            else {
                insertInternal(value, parent.right);
            }
        }
    }

    public void insert(T value) {
        if(root == null) {
            root = new Node(value);
            return;
        }
        insertInternal(value, root);
    }

    private Node searchInternal(T target, Node node) {
        if(node == null) {
            return null;
        }
        int comp=target.compareTo(node.data);
        if(comp < 0) {
            return searchInternal(target, node.left);
        }
        else if(comp > 0) {
            return searchInternal(target, node.right);
        }
        return node;
    }

    public Node search(T target) {
        return searchInternal(target, root);
    }

    private class Node {
        T data;
        Node left, right;

        public Node(T t) {
            data=t;
        }
    }

    @Override
    public Iterator<T> iterator() {
        // TODO Auto-generated method stub
        return null;
    }

    public static void main(String[] args) {
        BST<Integer> bst = new BST<Integer>();
        bst.insert(2);
        bst.insert(6);
        System.out.println(bst.search(2) != null);
        System.out.println(bst.search(6) != null);
        System.out.println(bst.search(8) == null);
    }
}