谁能帖个java实现二进制树的例子？

zonzi

多谢！！！！！！

小劲鸭

你要什么样的， 是普通而又基本的binary tree， 还是heap, 还是普通的binary search tree, 还是AVL tree, 还是4-2 tree, 还是black-red tree? 别叫我贴全部， 我可没那么多时间哦。。。。

zonzi

当然是普通的啊

小劲鸭

我现在正在写一个程序， 包括三个主class, 分别用binarytree来implement 2-4tree, 同样用binarytree来implement red-black tree， 第三个是一个convertor class, 用来将RB tree 转换成相应的 2－4 tree. 等写完后我在post出来给你参考一下啊。

hantsy

Data Structure and Algorithms in Java
到你书上找一段。。。

zonzi

其实Data Structure and Algorithms用lisp来表达最清楚

小劲鸭

最初由 hantsy 发表
Data Structure and Algorithms in Java
到你书上找一段。。。

很可惜， 那本书上就是没有post怎样implement 2－4 tree和red-black tree的源码，只有讲理论。 所以还得自己写

hantsy

最初由 zonzi 发表
其实Data Structure and Algorithms用lisp来表达最清楚

还没有看到过。。。。
我在学校的时候基本是都是pascale的。。。
后来见到一两本c写的。。。

最近才在书店看到java的。。。

小劲鸭

还在写， 先贴个2-4node的class源码吧， 等我把2-4Tree based on 2－4 node写完了再post 一次。

[PHP]class item{
        private Object key, element;

        item(Object k, Object e){
                key = k;
                element = e;
        }

        item(Object k){
                key = k;
        }

        public Object element { return element;}

        public Object key { return key;}

        public void setelement (Object e){ element = e; }

        public void setkey (Object k) { key = k; }
}


class twofourNode{
        private item itemArray[];
        private twofourNode linkArray[];   // children link array
        private twofourNode parent;
        private int itemlength;           // length for itemArray
        private int linklength;          //  length for linklength
        private Comparator comp;
        private linkadded, linkremoved;  // the lastest index that link inserted and removed

        // constructor
        twofourNode(){
                itemlength = 0;
                linklength = 1;
                itemArray = new item[4];
                linkArray = new twofourNode[1];
                parent = null;
                linkadded = -1;
                linkremoved = -1;
        }

        twofourNode(int noItem){
                itemlength = noItem;
                linklength = itemlength + 1;
                itemArray = new item[4];
                linkArray = new twofourNode[linklength];
                parent = null;
                linkadded = -1;
                linkremoved = -1;
        }

        // Query methods
        public int size(){ return itemlength; }
        public boolean overflow(){ return (itemlength == 4); }
        public boolean underflow(){ return (itemlength == 0); }
        public int nolink(){ return linklength; }
        public int getlinkadded() { return linkadded; }
        public int getlinkremoved() { return linkremoved; }

        // Access methods
        public Object[] getkeys(){
                Object keys[] = new Object[itemlength];
                for (int i = 0; i <= itemlength - 1; i++)
                        keys = itemArray.key();
                return keys;
        }

        public int searchkey(Object k){
                int i = 0;
                while (i < itemlength && !comp.isEqualTo(k,itemArray.key())
                        i++
                if (i == itemlength - 1)
                        return (i = -1);
                return i;
        }


        public Object getelement(Object k){
                int i = searchkey(k);
                return itemArray.element();
        }

        public Object[] getelements(){
                Object elements[] = new Object[itemlength];
                for (int i = 0; i <= itemlength - 1; i++)
                        elements = itemArray.element();
                return elements;
        }

        public item[] getItems(){
                item temp[];
                temp = itemArray;
                return temp;
        }

        public item getItem(Object k){
                int i = searchkey(k);
                return itemArray;
        }

        public twofourNode[] getchildren(){
                twofourNode info[];
                info = linkArray;
                return info;
        }


        public twofourNode getparent(){ return parent; }

        public twofourNode getrightchild(Object k){
                int i;
                i = searchkey(k);
                return linkArray[i + 1];
        }

        public twofourNode getleftchild(Object k){
                int i;
                i = searchkey(k);
                return linkArray;
        }

        public twofourNode getleftmost(){ return linkArray[0]; }

        public twofourNode getrightmost() { return linkArray[linklength - 1]; }

        // supportive methods for update methods
        public int insertindex(Object k){
                int i;
                for (i = 0; i < itemlength; i++){
                        if (comp.isLessThan(k, itemArray.key())
                                return i;
                        i++;
                }
                return i;

        }


        public void copylink(int volume){                                  // for addlinks && removelinks
                twofourNode temp[] = new twofourNode[linklength];
                for (int i = 0; i <= volume - 1; i++)                  // copy the old child links
                        temp = linkArray;
                linkArray = temp;
        }



        // There is a relationship between index of item inserted(i) or removed and that of child link added(j) or deleted: j = i + 1;
        // update methods
        public void insertItem(item input){
                Object k = input.key();
                int i;

                if (!comp.isComparable(k){
                        System.out.print("The key of the input is not valid!\n");
                        return;
                }

                else if(underflow()){
                        itemArray[0] = input;
                        itemlength++;
                        linkadded == 1;
                }
                else if(comp.isGreaterThan(k, itemArray[itemlength - 1].key()){
                        itemArray[itemlength] = input;
                        itemlength++;
                        linkadded == itemlength;
                }

                else{
                        i = insertindex(k);
                        for (int j = itemlength - 1; j >= i; j--)
                                itemArray[j + 1] = itemArray[j];
                        itemArray = input;
                        itemlength++;
                        linkadded == i + 1;
                }

        }

        public item removeItem(item input){
                Object k = input.key();
                int i;
                item temp = input;

                i = searchkey(k);

                for (int j = i; j <= itemlength - 2; j++)
                        itemArray[j] = itemArray[j + 1];
                itemlength--;
                linkremoved = k;
                return temp;

        }

        public void addchild(twofourNode p, int linkadded){
                int volume = linklength;
                linklength++;
                copylink(volume);
                if (linkadded == linklength - 1)
                        linkArray[linkadded] = p;
                else{
                        for (int i = linklength - 1; i >= linkadded; i--)
                                linkArray[i + 1] = linkArray;
                        linkArray[linkadded] = p;
                }
        }


        public twofourNode removechild(int linkremoved){
                twofourNode temp = linkArray[linkremoved];
                for (i = linkremoved; i <= linklength - 2; i++)
                        linkArray = linkArray[i + 1];
                linklength--;
                copylink(linklength);
                return temp;
        }

        public void setparent(twofourNode p){ parent = p; }

        public void setchild(twofourNode p, int index) { linkArray[index] = p; }

}[/PHP]

acdy

有没有.B+ 树的? 一直都想看一下 B+ 树的实现代码