日期:2014-05-20  浏览次数:20716 次

泛型的二叉搜索树,请指点
泛型的二叉搜索树,请指点小弟初学java,写了一个泛型的二叉搜索树(源代码见后)。

IBSTree接口定义一个二叉搜索树的对外接口,这个接口描述了二叉搜索树的所有对外可见的行为。具体的方法描述见源代码的注释。

IBSTree接口中有定义了一个二叉搜索树的节点类型的接口IBSTNode(这个接口也可以在IBSTree接口的外部定义,只是这个接口太小,个人觉得没必要单独定义),

这个接口描述了二叉搜索树的一个节点的对外可以的部分(对外只是可以获取节点的值)。

然后再定义了两个类BSTNode和BSTree,分别实现了这两个接口。

这个设计有点复杂,自己都觉得不够清爽^-^,

定义IBSNode纯粹是考虑到实现的效率,返回一个IBSNode的类可以传达更多的节点信息,尽管这些信息对外不可见,但是内部实现需要这些信息。

二叉搜索树的各个操作的实现没有做注释^-^,是由于这些操作在任何一本数据结构的书上都有详细的说明。

小弟主要关注的是泛型和程序的整个结构。

请各位路过的大虾指点一下,小弟万分感激。^-^

小弟初来,没多少分,^-^

源文件共三个:IBSTree.java、BSTNode.java、BSTree.java。

文件1:IBSTree.java

package   BinarySearchTree;

//二叉搜索树类型
public   interface   IBSTree <Value   extends   Comparable <Value> >   {
       
        public   interface   IBSTNode <Value>   {
               
                Value   getValue();                                                         //获取二叉搜索树结点的键
               
                boolean   isEmpty();                                                         //判断二叉搜索树结点是否为空
               
        }
       
        void   makeEmptyBST();                                                         //创建一棵空的二叉搜索树
       
        boolean   isEmptyBST();                                                         //判断一棵二叉搜索树是否为空
       
        IBSTNode <Value>   search(Value   k);                                 //在二叉树搜索树中查找指定的键
       
        boolean   insert(Value   k);                                                 //向二叉搜索树中插入键
       
        IBSTNode <Value>   getMax();                                                 //获取二叉搜索树中的最大值
       
        IBSTNode <Value>   getMin();                                                 //获取二叉搜索树中的最小值
       
        IBSTNode <Value>   succ(IBSTNode <Value>   n);                 //获取后继