java - 通用 BST 的实现

Question

您好，我想知道如何设置一个具有私有(private) Node 类的面向对象的 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 类是一个私有(private)内部类，所以它不必是泛型的，而是可以使用其父类中指定的类型，我认为这正是您想要的。

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

在设计 BST 等抽象数据类型时，最好考虑一下如何使用它:它应该支持哪些操作，又名。它的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);
    }
}