树结构之红黑树

红黑树是在二叉树的基础上加了红、黑两种颜色。

树：

有序树
无序树

二叉树：所有结点的度都小于等于2
前序遍历，中序遍历，后序遍历，根据先访问根的操作顺序区分

翻转：

public TreeNode reverseBinaryTree(TreeNode root){
    //先处理base case，当root ==null 时，什么都不需要做,返回空指针
    if(root == null){
        return null;
    }
    else{
        //把左子树翻转
        TreeNode left = reverseBinaryTree(root.left);
        //把右子树翻转
        TreeNode right = reverseBinaryTree(root.right);
        //把左右子树分别赋值给root节点，但是是翻转过来的顺序
        root.left = right;
        root.right = left;
        //返回根节点
        return root;
    }
}

深度优先搜索：

/**
** 二叉树节点
**/
public class TreeNode{
    TreeNode left;
    TreeNode Right;
    int value;
}
//中序
public void printInoderTree(TreeNode root){
    //base case
    if(root == null){
        return;
    }
    //递归调用printTree
    printInoderTree(root.left);
    System.out.println(root.val);
    printInoderTree(root.right);
}
//中序
public void printPreoderTree(TreeNode root){
    //base case
    if(root == null){
        return;
    }
    //递归调用printTree
    System.out.println(root.val);
    printPreoderTree(root.left);
    printPreoderTree(root.right);
}

平铺：

public TreeNode flatten(TreeNode root){  
    //base case
    if(root == null){
        return null;
    }
    else{
        //用递归的思想，把左右先铺平
        TreeNode left = flatten(root.left);
        TreeNode right = flatten(root.right);
        //把左指针和右指针先指向空。
        root.left = null;
        root.right = null;
        //假如左子树生成的链表为空，那么忽略它，把右子树生成的链表指向根节点的右指针
        if(left == null){
            root.right = right;
            return root;
        }
        //如果左子树生成链表不为空，那么用while循环获取最后一个节点，并且它的右指针要指向右子树生成的链表的头节点
        root.right = left;
        TreeNode lastLeft = left;
        while(lastLeft != null && lastLeft.right != null){
            lastLeft = lastLeft.right;
        }
        lastLeft.right = right;
        return root;
    }
}

广度优先搜索：

用队列
public void printTree(TreeNode root){
    if(root == null){
        return;
    }
    Queue queue = new LinkedList();
    queue.add(root);
    while(!queue.isEmpty()){
        TreeNode current = queue.poll();
        System.out.println(current.toString());
        if(current.left != null){
            queue.add(current.left);
        }
        if(current.right != null){
            queue.add(current.right);
        }
    }
}

小知识：集合和队列相关：
arraylist以数组实现，但数组有容量限制，超出限制会在增加50%的容量，并用System.arraycopy（）复制到新的数组
LinkedList以双向链表实现，链表无容量限制。但双向链表使用了更多空间，也需要额外的链表指针操作。【双向链表实现的linkedList是list也是queue，他是唯一一个允许放入null的queue】
线程安全队列：
ConcurrentLinkedQueue/ConcurrentLinkedDeque无界的并发优化的Queue，基于链表，实现了依赖于CAS的无锁算法。

二叉树的next结点：

public void nextSibiling(TreeNode node){
    if(node == null){
        return;
    }
    Queue queue = new LinkedList();
    queue.add(node);
    //这个level没有实际用处，但是可以告诉大家怎么判断当前node是第几层。
    int level = 0;
    while(!queue.isEmpty()){
        int size = queue.size();
        //用这个for循环，可以保证for循环里面对queue不管加多少个子节点，我只处理当前层里面的节点
        for(int i = 0;i<size;i++){
                //把当前第一个节点拿出来
                TreeNode current = queue.poll();
                //把子节点加到queue里面
                if(current.left != null){
                    queue.add(current.left);
                }
                if(current.right != null){
                    queue.add(current.right);
                }
                if(i != size -1){
                    //peek只是获取当前队列中第一个节点，但是并不把它从队列中拿出来
                    current.next = queue.peek();
                }
            }
        }
        level++;
    }
}

红黑树

特点：
1，根节点必须黑色
2，父子不能同为红色
3，从任何一个节点出发到达下游叶子节点经过的黑色节点数量一样。