红黑树是在二叉树的基础上加了红、黑两种颜色。
树：
有序树
无序树
二叉树：所有结点的度都小于等于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，从任何一个节点出发到达下游叶子节点经过的黑色节点数量一样。
