正文之前

經(jīng)過幾天下午四點(diǎn)到現(xiàn)在的功夫，然后結(jié)合算法導(dǎo)論和自己的一些小嘗試，總算把Java版本的二叉樹給做的完美了~ emm 不信的話大家伙盡管測試。。。終于?。?！樹形結(jié)構(gòu)！用Java實(shí)現(xiàn)出來確實(shí)很麻煩啊！因?yàn)槭莻鬟f引用，所以要特別注意。。一不小心就出錯(cuò)了。。而且我經(jīng)常犯一些傻逼錯(cuò)誤！真的是想哭?。。?！

有點(diǎn)小改進(jìn)： 【二叉搜索樹-Java】改進(jìn)了toString和gennerateTree

正文

import java.util.Arrays;
import java.util.Random;
import java.util.LinkedList;
import java.util.Queue;

class node{
    private int key;
    node leftChild;
    node rightChild;
    node parent;
    node(int x){
        this.key=x;
    }
    node(){};
    public int getKey(){
        return this.key;
    }
}

class Tree{
    node head;
    int size;
    Tree(){this.size = 0;}

    public node getHead(){
        return this.head;
    }

    private void walk(Queue<String> queue,node par, int level){
        String l = "";
        for (int i =0;i<level;++i) l+=" ---->>>> ";
        if (level == 1) queue.add(""+ par.getKey());
        if(par.leftChild!=null){
            queue.add(l+par.leftChild.getKey());
            walk(queue,par.leftChild,level+1);
        }
        if (par.rightChild!=null){
            queue.add(l+par.rightChild.getKey());
            walk(queue,par.rightChild,level+1);
        }
    }
    public String toString(){
        System.out.println("輸出樹形: ");
        Queue<String> queue = new LinkedList<>();
        String out = "";
        if (this.head!=null){
            String one = "ok";
            walk(queue,this.head,1);
            int count = 0;
            while(one!=null) {
                one = queue.poll();
                count++;
                if(one!=null)
                    out += (count +" : "+ one+"\n");
            }
        }
        return out;
    }
}

public class TestTree{
    private static node __findNode(node par,int z){
        if (par==null || par.getKey() == z)
            return par;
        if (z<par.getKey()) return __findNode(par.leftChild,z);
        else return __findNode(par.rightChild,z);
    }
    public static node  findNode(Tree tree,int z){
        node par = tree.getHead();
        return __findNode(par,z);
    }
    public static void transplant(Tree tree, node u, node r){
        if (u.parent == null) tree.head = r;
        else if (u == u.parent.leftChild){
            u.parent.leftChild = r;
        }
        else {
            u.parent.rightChild = r;
        }
        if (r!=null)
            u.parent = r.parent;
    }

    public static void nodeDelete(Tree tree, node z){
        tree.size-=1;
        if (z.leftChild==null)
            transplant(tree,z,z.rightChild);
        else if (z.rightChild==null)
            transplant(tree,z,z.leftChild);
        else {
            node y = minNode(z.rightChild);
            if (y.parent!=z){
                transplant(tree,y,y.rightChild);
                y.rightChild = z.rightChild;
                y.rightChild.parent = y;
            }
            transplant(tree,z,y);
            y.leftChild = z.leftChild;
            y.leftChild.parent = y;
        }
        System.out.println("Deleted :  "+ z.getKey()+"\n");
    }

    private static node minNode(node no){
        node x = no;
        while (x.leftChild!=null)
            x=x.leftChild;
        return x;
    }
    public static void insertSort(int []arr, int n){
        for (int i = 1; i < n; ++i)
        {
            int e = arr[i];
            int j=i;
            for (; j > 0; --j)
            {
                if (e < arr[j-1])
                    arr[j] = arr[j-1];
                else
                    break;
            }
            arr[j] = e;
        }
    }
    public static void insertToTree(Tree tree,int x){
        System.out.println("Insert into the Tree : "+x+"\n");
        tree.size+=1;
        node newnode = new node(x);
        node tmp = tree.getHead();
        if ( tmp==null)
            tree.head = newnode;
        while(tmp!=null) {
            if (x < tmp.getKey()) {
                if (tmp.leftChild==null || x > tmp.leftChild.getKey()) {
                    newnode.parent = tmp;
                    newnode.leftChild = tmp.leftChild;
                    tmp.leftChild = newnode;
                    return;
                }
                else
                    tmp = tmp.leftChild;
            }
            else {
                if ( tmp.rightChild==null || x < tmp.rightChild.getKey()) {
                    newnode.parent = tmp;
                    newnode.rightChild = tmp.rightChild;
                    tmp.rightChild = newnode;
                    return;
                }
                else
                    tmp = tmp.rightChild;
            }
        }
    }
    public static Tree generateTree(int[] arr){
        Tree tree = new Tree();
//        insertSort(arr,arr.length);
        insertToTree(tree,arr[arr.length/2]);
        for (int i=0;i<arr.length;++i) {
            if (i!=arr.length/2) {
                tree.size+=1;
                node newnode = new node(arr[i]);
                node tmp = tree.getHead();
                while(tmp!=null) {
                    if (arr[i] < tmp.getKey()) {
                        if (tmp.leftChild==null) {
                            newnode.parent = tmp;
                            newnode.leftChild = null;
                            tmp.leftChild = newnode;
                            break;
                        }
                        else
                            tmp = tmp.leftChild;
                    }
                    else {
                        if ( tmp.rightChild==null) {
                            newnode.parent = tmp;
                            newnode.rightChild =null;
                            tmp.rightChild = newnode;
                            break;
                        }
                        else
                            tmp = tmp.rightChild;
                    }
                }
            }
        }
        return tree;
    }
    public static void main(String[] args) {
        double start = System.currentTimeMillis();
        Random rdm = new Random(System.currentTimeMillis());
        int [] randomArr = new int[20];
        for(int i=0;i<20;i++)
            randomArr[i] = Math.abs(rdm.nextInt())%500 +1;
        Tree tree = generateTree(randomArr);
        System.out.println(Arrays.toString(randomArr));
        System.out.println(tree.toString());
        nodeDelete(tree,findNode(tree,randomArr[Math.abs(rdm.nextInt())%tree.size+1]));
        System.out.println(tree.toString());
        insertToTree(tree,Math.abs(rdm.nextInt())%500 +1);
        System.out.println(tree.toString());
        double end  = System.currentTimeMillis();
        System.out.println("Usage of Time: "+(end-start));
    }
}

注釋什么的就不寫了。都是很簡單的部分，大概也就幾個(gè)遞歸搞得我比較煩惱。。emm 然后就是刪除我是直接借鑒了《算法導(dǎo)論》的偽代碼實(shí)現(xiàn)的Java版本，真的厲害啊。。照著做就OK了。。。完全沒想太多。。不過好歹還是吃透了。而且輔助函數(shù)都是自己寫的好伐~

emm 下面看看使用過程的output：

Insert into the Tree : 241

[340, 286, 171, 462, 20, 262, 436, 184, 30, 50, 241, 373, 301, 461, 329, 120, 91, 375, 98, 105]
輸出樹形: 
1 : 241
2 :  ---->>>> 171
3 :  ---->>>>  ---->>>> 20
4 :  ---->>>>  ---->>>>  ---->>>> 30
5 :  ---->>>>  ---->>>>  ---->>>>  ---->>>> 50
6 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 120
7 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 91
8 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 98
9 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 105
10 :  ---->>>>  ---->>>> 184
11 :  ---->>>> 340
12 :  ---->>>>  ---->>>> 286
13 :  ---->>>>  ---->>>>  ---->>>> 262
14 :  ---->>>>  ---->>>>  ---->>>> 301
15 :  ---->>>>  ---->>>>  ---->>>>  ---->>>> 329
16 :  ---->>>>  ---->>>> 462
17 :  ---->>>>  ---->>>>  ---->>>> 436
18 :  ---->>>>  ---->>>>  ---->>>>  ---->>>> 373
19 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 375
20 :  ---->>>>  ---->>>>  ---->>>>  ---->>>> 461

Deleted :  120

輸出樹形: 
1 : 241
2 :  ---->>>> 171
3 :  ---->>>>  ---->>>> 20
4 :  ---->>>>  ---->>>>  ---->>>> 30
5 :  ---->>>>  ---->>>>  ---->>>>  ---->>>> 50
6 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 91
7 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 98
8 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 105
9 :  ---->>>>  ---->>>> 184
10 :  ---->>>> 340
11 :  ---->>>>  ---->>>> 286
12 :  ---->>>>  ---->>>>  ---->>>> 262
13 :  ---->>>>  ---->>>>  ---->>>> 301
14 :  ---->>>>  ---->>>>  ---->>>>  ---->>>> 329
15 :  ---->>>>  ---->>>> 462
16 :  ---->>>>  ---->>>>  ---->>>> 436
17 :  ---->>>>  ---->>>>  ---->>>>  ---->>>> 373
18 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 375
19 :  ---->>>>  ---->>>>  ---->>>>  ---->>>> 461

Insert into the Tree : 47

輸出樹形: 
1 : 241
2 :  ---->>>> 171
3 :  ---->>>>  ---->>>> 47
4 :  ---->>>>  ---->>>>  ---->>>> 20
5 :  ---->>>>  ---->>>>  ---->>>>  ---->>>> 30
6 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 50
7 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 91
8 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 98
9 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 105
10 :  ---->>>>  ---->>>> 184
11 :  ---->>>> 340
12 :  ---->>>>  ---->>>> 286
13 :  ---->>>>  ---->>>>  ---->>>> 262
14 :  ---->>>>  ---->>>>  ---->>>> 301
15 :  ---->>>>  ---->>>>  ---->>>>  ---->>>> 329
16 :  ---->>>>  ---->>>> 462
17 :  ---->>>>  ---->>>>  ---->>>> 436
18 :  ---->>>>  ---->>>>  ---->>>>  ---->>>> 373
19 :  ---->>>>  ---->>>>  ---->>>>  ---->>>>  ---->>>> 375
20 :  ---->>>>  ---->>>>  ---->>>>  ---->>>> 461

Usage of Time: 3.0

Process finished with exit code 0

正文之后

我是實(shí)在懶得去toString搞得盡善盡美了，現(xiàn)在這個(gè)樣子大概也能看吧。。就一個(gè)先序遍歷，，emm 愛看不看。。反正我是覺得基本沒bug了。。。哈哈哈~

背景插圖，自己下載哈！