正文之前

昨天基本又是玩了。。所以很后悔。。今早就改进下二叉搜索树吧。。。红黑树看得我脑子炸裂！！！

正文

    public String toString() {
        System.out.println("输出树形: ");
        Queue<node> queue = new LinkedList<>();
        String out = "";
        queue.add(this.root);
        int x=-10000;
        while (!queue.isEmpty()) {
            node s = queue.poll();
            if (s.getKey()<x) {
                out += "\n";
            }
            x=s.getKey();
            out += (s.getKey() + " ");
            if (s.leftChild != null)
                queue.add(s.leftChild);
            if (s.rightChild != null)
                queue.add(s.rightChild);
        }
        return out;
    }

采用层序遍历的方式，然后因为层序遍历严格的遵循一层一层的输出的原则，所以很简单的判定分层的条件就是当前节点比上一个节点小，就一定是分层了。毕竟在同一层，从左到右的话肯定是逐个增大，这是由于二叉搜索树的性质决定的。。

    public static void insertToTree(Tree tree,int x){
        System.out.println("\nInsert into the Tree : "+x+"\n");
        tree.size+=1;
        node newnode = new node(x);
        node tmp = tree.getRoot();
        if ( tmp==null)
            tree.root = newnode;
        while(tmp!=null) {
            if (x < 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;
            }
        }
    }


    public static Tree generateTree(int[] arr){
        Tree tree = new Tree();
        insertToTree(tree,arr[arr.length/2]);
        for (int i=0;i<arr.length;++i) {
            if (i!=arr.length/2) {
                insertToTree(tree,arr[i]);
            }
        }
        return tree;
    }

好吧，我前面傻逼了。。。居然插入的时候还想着在树中间插入而不是直接成为叶节点。。我就是一傻逼。。

所以干脆完美的统一了生成和插入了，不过其实生成树不就是多次插入的结果吗？

正文之后

今天吃透红黑树！不解释！！然后看视频又重温了一次并查集，发现数据结构的魅力是真的大啊！！！