紅黑樹是在二叉樹的基礎(chǔ)上加了紅、黑兩種顏色。

樹：

有序樹
無序樹

二叉樹：所有結(jié)點(diǎn)的度都小于等于2
前序遍歷，中序遍歷，后序遍歷，根據(jù)先訪問根的操作順序區(qū)分

翻轉(zhuǎn)：

public TreeNode reverseBinaryTree(TreeNode root){
    //先處理base case，當(dāng)root ==null 時(shí)，什么都不需要做,返回空指針
    if(root == null){
        return null;
    }
    else{
        //把左子樹翻轉(zhuǎn)
        TreeNode left = reverseBinaryTree(root.left);
        //把右子樹翻轉(zhuǎn)
        TreeNode right = reverseBinaryTree(root.right);
        //把左右子樹分別賦值給root節(jié)點(diǎn)，但是是翻轉(zhuǎn)過來的順序
        root.left = right;
        root.right = left;
        //返回根節(jié)點(diǎn)
        return root;
    }
}

深度優(yōu)先搜索：

/**
** 二叉樹節(jié)點(diǎn)
**/
public class TreeNode{
    TreeNode left;
    TreeNode Right;
    int value;
}
//中序
public void printInoderTree(TreeNode root){
    //base case
    if(root == null){
        return;
    }
    //遞歸調(diào)用printTree
    printInoderTree(root.left);
    System.out.println(root.val);
    printInoderTree(root.right);
}
//中序
public void printPreoderTree(TreeNode root){
    //base case
    if(root == null){
        return;
    }
    //遞歸調(diào)用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;
        //假如左子樹生成的鏈表為空，那么忽略它，把右子樹生成的鏈表指向根節(jié)點(diǎn)的右指針
        if(left == null){
            root.right = right;
            return root;
        }
        //如果左子樹生成鏈表不為空，那么用while循環(huán)獲取最后一個(gè)節(jié)點(diǎn)，并且它的右指針要指向右子樹生成的鏈表的頭節(jié)點(diǎn)
        root.right = left;
        TreeNode lastLeft = left;
        while(lastLeft != null && lastLeft.right != null){
            lastLeft = lastLeft.right;
        }
        lastLeft.right = right;
        return root;
    }
}

廣度優(yōu)先搜索：

用隊(duì)列
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);
        }
    }
}

小知識(shí)：集合和隊(duì)列相關(guān)：
arraylist以數(shù)組實(shí)現(xiàn)，但數(shù)組有容量限制，超出限制會(huì)在增加50%的容量，并用System.arraycopy（）復(fù)制到新的數(shù)組
LinkedList以雙向鏈表實(shí)現(xiàn)，鏈表無容量限制。但雙向鏈表使用了更多空間，也需要額外的鏈表指針操作?！倦p向鏈表實(shí)現(xiàn)的linkedList是list也是queue，他是唯一一個(gè)允許放入null的queue】
線程安全隊(duì)列：
ConcurrentLinkedQueue/ConcurrentLinkedDeque無界的并發(fā)優(yōu)化的Queue，基于鏈表，實(shí)現(xiàn)了依賴于CAS的無鎖算法。

二叉樹的next結(jié)點(diǎn)：

public void nextSibiling(TreeNode node){
    if(node == null){
        return;
    }
    Queue queue = new LinkedList();
    queue.add(node);
    //這個(gè)level沒有實(shí)際用處，但是可以告訴大家怎么判斷當(dāng)前node是第幾層。
    int level = 0;
    while(!queue.isEmpty()){
        int size = queue.size();
        //用這個(gè)for循環(huán)，可以保證for循環(huán)里面對(duì)queue不管加多少個(gè)子節(jié)點(diǎn)，我只處理當(dāng)前層里面的節(jié)點(diǎn)
        for(int i = 0;i<size;i++){
                //把當(dāng)前第一個(gè)節(jié)點(diǎn)拿出來
                TreeNode current = queue.poll();
                //把子節(jié)點(diǎn)加到queue里面
                if(current.left != null){
                    queue.add(current.left);
                }
                if(current.right != null){
                    queue.add(current.right);
                }
                if(i != size -1){
                    //peek只是獲取當(dāng)前隊(duì)列中第一個(gè)節(jié)點(diǎn)，但是并不把它從隊(duì)列中拿出來
                    current.next = queue.peek();
                }
            }
        }
        level++;
    }
}

紅黑樹

特點(diǎn)：
1，根節(jié)點(diǎn)必須黑色
2，父子不能同為紅色
3，從任何一個(gè)節(jié)點(diǎn)出發(fā)到達(dá)下游葉子節(jié)點(diǎn)經(jīng)過的黑色節(jié)點(diǎn)數(shù)量一樣。