樹

二叉樹的遍歷

//二叉樹結(jié)點定義
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val=x;
    }
    @Override
    public String toString(){
        return "val: "+val;
    }
}

//訪問結(jié)點方法方法
 public void visit(TreeNode node){
        System.out.print(node.val+" ");
    }

  1. 前序遍歷

    • 遞歸實現(xiàn)

       /**
     * 遞歸先序遍歷
     * */
    public void preOrderRecursion(TreeNode node){
        if(node==null) //如果結(jié)點為空則返回
            return;
        visit(node);//訪問根節(jié)點
        preOrderRecursion(node.left);//訪問左孩子
        preOrderRecursion(node.right);//訪問右孩子
    }

    • 非遞歸

      /**
     * 非遞歸先序遍歷二叉樹
     * */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        Stack<TreeNode> treeStack = new Stack<>();
        if (root == null) //如果為空樹則返回
            return resultList;
        treeStack.push(root);
        while( !treeStack.isEmpty() ){
            TreeNode tempNode = treeStack.pop(); 
            if(tempNode != null){
                resultList.add(tempNode.val);//訪問根節(jié)點
                if (tempNode.right != null) {
                     treeStack.push(tempNode.right); //入棧右孩子
                }
                if (tempNode.left != null) {
                treeStack.push(tempNode.left);//入棧左孩子
                }
            }
        }
        return resultList;
    }

  2. 中序遍歷

    • 遞歸

    • 非遞歸

      /**
   非遞歸中序遍歷
*/
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();

    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;

    while(cur!=null || !stack.empty()){
        while(cur!=null){
            stack.add(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        list.add(cur.val);
        cur = cur.right;
    }

    return list;
}

  3. 后序遍歷

    • 遞歸

    • 非遞歸(加一個輔助棧)

      public static void posOrderTraverse(Node head) {
        System.out.println("pos-order");
        if(head != null) {
            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();     // 輔助棧，存儲 根 -> 右 -> 左 的結(jié)果
            stack1.push(head);
            while(!stack1.isEmpty()) {
                head = stack1.pop();
                stack2.push(head);
                // 有左孩子就先壓入左孩子
                if(head.left != null)
                    stack1.push(head.left);
                // 有右孩子就后壓入右孩子
                if(head.right != null)
                    stack1.push(head.right);
            }
            // 逆序打印 根 -> 右 -> 左 的結(jié)果，就是后序遍歷的結(jié)果
            while(!stack2.isEmpty())
                System.out.print(stack2.pop().val + " ");
        }
    }

  4. 層序遍歷(廣度優(yōu)先，用隊列)

    層序遍歷框架：

    void traverse(TreeNode root) {
    if (root == null) return;
    // 初始化隊列，將 root 加入隊列
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        TreeNode cur = q.poll();

        /* 層級遍歷代碼位置 */
        System.out.println(root.val);
        /*****************/

        if (cur.left != null) {
            q.offer(cur.left);
        }

        if (cur.right != null) {
            q.offer(cur.right);
        }
    }
}

    分層來打?。盒枰尤胍粋€Path

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);
        while (queue.size() != 0) {
            int size = queue.size();
            List<Integer> path = new ArrayList<>();
            for (int i=0;i<size;i++) { //這個循環(huán)很關(guān)鍵
                
                //按順序出隊列，訪問出隊列的元素的左右結(jié)點
                TreeNode temp = queue.removeFirst(); 
                if (temp.left != null) {
                    queue.addLast(temp.left);
                }
                if (temp.right != null) {
                    queue.addLast(temp.right);
                }
                path.add(temp.val);
            }
            res.add(path);
        }
        return res;
    }

  5. 通過先序遍歷和中序遍歷重建二叉樹

    [圖片上傳失敗...(image-923cb8-1609223312780)]

    TreeNode build(int[] preorder, int preStart, int preEnd, 
               int[] inorder, int inStart, int inEnd) {

    if (preStart > preEnd) {
        return null;
    }

    // root 節(jié)點對應(yīng)的值就是前序遍歷數(shù)組的第一個元素
    int rootVal = preorder[preStart];
    // rootVal 在中序遍歷數(shù)組中的索引
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }

    int leftSize = index - inStart;

    // 先構(gòu)造出當前根節(jié)點
    TreeNode root = new TreeNode(rootVal);
    // 遞歸構(gòu)造左右子樹，參考下面兩幅圖
    root.left = build(preorder, preStart + 1, preStart + leftSize,
                      inorder, inStart, index - 1);

    root.right = build(preorder, preStart + leftSize + 1, preEnd,
                       inorder, index + 1, inEnd);
    return root;
}
    image-20201226195602243
    image-20201226195624346

  6. 通過中序遍歷和后序遍歷重建二叉樹

    image-20201226195723841
    TreeNode build(int[] inorder, int inStart, int inEnd,
               int[] postorder, int postStart, int postEnd) {

    if (inStart > inEnd) {
        return null;
    }
    // root 節(jié)點對應(yīng)的值就是后序遍歷數(shù)組的最后一個元素
    int rootVal = postorder[postEnd];
    // rootVal 在中序遍歷數(shù)組中的索引
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }
    // 左子樹的節(jié)點個數(shù)
    int leftSize = index - inStart;
    TreeNode root = new TreeNode(rootVal);
    // 遞歸構(gòu)造左右子樹
    root.left = build(inorder, inStart, index - 1,
                        postorder, postStart, postStart + leftSize - 1);

    root.right = build(inorder, index + 1, inEnd,
                        postorder, postStart + leftSize, postEnd - 1);
    return root;
}
    image-20201226195748361

總結(jié)：主要是要找到正確的起始位置，可以自己舉一個例子畫圖來確定。leftSize是關(guān)鍵，他是中序遍歷左子樹的節(jié)點總數(shù)。

二叉樹的序列化與反序列化

? 二叉樹的序列化可以運用于對象轉(zhuǎn)化為JSON字符串，反序列化可運用于JSON轉(zhuǎn)化為對象。JSON的運用非常廣泛，比如我們經(jīng)常將變成語言中的結(jié)構(gòu)體序列化成 JSON字符串，存入緩存或者通過網(wǎng)絡(luò)發(fā)送給遠端服務(wù)，消費者接受JSON字符串然后進行反序列化，就可以得到原始數(shù)據(jù)了。這就是「序列化」和「反序列化」的目的，以某種固定格式組織字符串，使得數(shù)據(jù)可以獨立于編程語言。

  1. 前序遍歷解法

    ? 序列化代碼：如果結(jié)點是空結(jié)點，那么在字符串后面拼接一個“#,”;如果不是空結(jié)點，那么拼接“rootVal，”。最后結(jié)果返回一個把二叉樹“打平”了的字符串

    String SEP = ",";
String NULL = "#";

/* 主函數(shù)，將二叉樹序列化為字符串 */
String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serialize(root, sb);
    return sb.toString();
}

/* 輔助函數(shù)，將二叉樹存入 StringBuilder */
void serialize(TreeNode root, StringBuilder sb) {
    if (root == null) {
        sb.append(NULL).append(SEP);
        return;
    }

    /****** 前序遍歷位置 ******/
    sb.append(root.val).append(SEP);
    /***********************/

    serialize(root.left, sb);
    serialize(root.right, sb);
}

    ? 反序列化代碼：將序列化的字符串按照“,”進行分割，并轉(zhuǎn)化為鏈表結(jié)構(gòu)。然后通過前序遍歷框架反序列化。

    /* 主函數(shù)，將字符串反序列化為二叉樹結(jié)構(gòu) */
TreeNode deserialize(String data) {
    // 將字符串轉(zhuǎn)化成列表
    LinkedList<String> nodes = new LinkedList<>();
    for (String s : data.split(SEP)) {
        nodes.addLast(s);
    }
    return deserialize(nodes);
}

/* 輔助函數(shù)，通過 nodes 列表構(gòu)造二叉樹 */
TreeNode deserialize(LinkedList<String> nodes) {
    if (nodes.isEmpty()) return null;

    /****** 前序遍歷位置 ******/
    // 列表最左側(cè)就是根節(jié)點
    String first = nodes.removeFirst();
    if (first.equals(NULL)) return null;
    TreeNode root = new TreeNode(Integer.parseInt(first));
    /***********************/

    //遞歸的去調(diào)用
    root.left = deserialize(nodes);
    root.right = deserialize(nodes);

    return root;
}

  2. 后序遍歷解法

    序列化代碼：

    /* 輔助函數(shù)，將二叉樹存入 StringBuilder */
void serialize(TreeNode root, StringBuilder sb) {
    if (root == null) {
        sb.append(NULL).append(SEP);
        return;
    }

    serialize(root.left, sb);
    serialize(root.right, sb);

    /****** 后序遍歷位置 ******/
    sb.append(root.val).append(SEP);
    /***********************/
}

    反序列化代碼：首先要找到根節(jié)點，再按照根-->右-->左的順序還原。

    /* 主函數(shù)，將字符串反序列化為二叉樹結(jié)構(gòu) */
TreeNode deserialize(String data) {
    LinkedList<String> nodes = new LinkedList<>();
    for (String s : data.split(SEP)) {
        nodes.addLast(s);
    }
    return deserialize(nodes);
}

/* 輔助函數(shù)，通過 nodes 列表構(gòu)造二叉樹 */
TreeNode deserialize(LinkedList<String> nodes) {
    if (nodes.isEmpty()) return null;
    // 從后往前取出元素
    String last = nodes.removeLast();
    if (last.equals(NULL)) return null;
    TreeNode root = new TreeNode(Integer.parseInt(last));
    // 先構(gòu)造右子樹，后構(gòu)造左子樹
    root.right = deserialize(nodes);
    root.left = deserialize(nodes);

    return root;
}

  3. 層序遍歷解法

    序列化代碼：

    String SEP = ",";
String NULL = "#";

/* 將二叉樹序列化為字符串 */
String serialize(TreeNode root) {
    if (root == null) return "";
    StringBuilder sb = new StringBuilder();
    // 初始化隊列，將 root 加入隊列
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        TreeNode cur = q.poll();

        /* 層級遍歷代碼位置 */
        if (cur == null) {
            sb.append(NULL).append(SEP);
            continue;
        }
        sb.append(cur.val).append(SEP);
        /*****************/

        q.offer(cur.left);
        q.offer(cur.right);
    }

    return sb.toString();
}

    序列化后的結(jié)果如圖所示

    image-20201226195841319

    反序列化代碼：

    /* 將字符串反序列化為二叉樹結(jié)構(gòu) */
TreeNode deserialize(String data) {
    if (data.isEmpty()) return null;
    String[] nodes = data.split(SEP);
    // 第一個元素就是 root 的值
    TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));

    // 隊列 q 記錄父節(jié)點，將 root 加入隊列
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    for (int i = 1; i < nodes.length; ) {
        // 隊列中存的都是父節(jié)點
        TreeNode parent = q.poll();
        // 父節(jié)點對應(yīng)的左側(cè)子節(jié)點的值
        String left = nodes[i++];
        if (!left.equals(NULL)) {
            parent.left = new TreeNode(Integer.parseInt(left));
            q.offer(parent.left);
        } else {
            parent.left = null;
        }
        // 父節(jié)點對應(yīng)的右側(cè)子節(jié)點的值
        String right = nodes[i++];
        if (!right.equals(NULL)) {
            parent.right = new TreeNode(Integer.parseInt(right));
            q.offer(parent.right);
        } else {
            parent.right = null;
        }
    }
    return root;
}

  4. 總結(jié)：

    ? 注意后序遍歷解法，與前序遍歷、層序遍歷不同，后序遍歷序列化是按照標準后序遍歷框架進行的，而反序列化則是先找到最后一個元素即為根節(jié)點，從后往前(根-->右-->左)進行反序列化。

二叉(排序/搜索)樹 (BST樹)

? 二叉查找樹（Binary Search Tree），（又：二叉搜索樹，二叉排序樹）它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

  • 若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
  • 若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
  • 它的左、右子樹也分別為二叉排序樹。
  • 它的中序遍歷是升序的（左-->中-->右），也可以降序（右-->中-->左）

? 二叉搜索樹作為一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，它既有鏈表的快速插入與刪除操作的特點，又有數(shù)組快速查找的優(yōu)勢；所以應(yīng)用十分廣泛，例如在文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)一般會采用這種數(shù)據(jù)結(jié)構(gòu)進行高效率的排序與檢索操作。

  1. 查找

    ? 可以利用二叉搜索樹的性質(zhì)進行查找（二分查找），O(logn)時間復(fù)雜度，最壞情況O(n)(當樹退化為鏈表時)。

  2. 插入

    ? 在查找的基礎(chǔ)上進行插入操作

  3. 刪除

    分為三種情況：刪除葉子節(jié)點、刪除只有一個子結(jié)點的結(jié)點、刪除有兩個子結(jié)點的結(jié)點

    TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (root.val == key) {
        // 這兩個 if 把情況 1 和 2 都正確處理了
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        // 處理情況 3
         //minNode 右子樹的最小結(jié)點
        TreeNode minNode = getMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right, minNode.val);
    } else if (root.val > key) {
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

TreeNode getMin(TreeNode node) {
    // BST 最左邊的就是最小的
    while (node.left != null) node = node.left;
    return node;
}

平衡二叉樹(AVL樹)

? 平衡二叉搜索樹（Self-balancing binary search tree）又被稱為AVL樹（有別于AVL算法），且具有以下性質(zhì)：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
? 基本代碼準備：

/**
 * AVLTree是BST，所以節(jié)點值必須是可比較的
 */
public class AvlTree<E extends Comparable<E>>{
    private class Node{
        public E e;
        public Node left;
        public Node right;
        public int height;

        public Node(E e){
            this.e = e;
            this.left = null;
            this.right = null;
            this.height = 1;
        }
    }

    private Node root;
    private int size;

    public AvlTree(){
        root=null;
        size=0;
    }

    //獲取某一結(jié)點的高度
    private int getHeight(Node node){
        if(node==null){
            return 0;
        }
        return node.height;
    }
    
    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }
    
    /**
     * 獲取節(jié)點的平衡因子
     * @param node
     * @return
     */
    private int getBalanceFactor(Node node){
        if(node==null){
            return 0;
        }
        return getHeight(node.left)-getHeight(node.right);
    }
    
    //判斷樹是否為平衡二叉樹
    public boolean isBalanced(){
        return isBalanced(root);
    }

    private boolean isBalanced(Node node){
        if(node==null){
            return true;
        }
        int balanceFactory = Math.abs(getBalanceFactor(node));
        if(balanceFactory>1){
            return false;
        }
        return isBalanced(node.left)&&isBalanced(node.right);
    }
}

  1. LL（右旋）

    ? LL的意思是向左子樹（L）的左孩子（L）中插入新節(jié)點后導(dǎo)致不平衡，這種情況下需要右旋操作，而不是說LL的意思是右旋，后面的也是一樣。

在這里插入圖片描述
/**
 * 右旋轉(zhuǎn)
 */
private Node rightRotate(Node y){
    //x作為新頂點
    Node x = y.left;
    //因為即將要改變x的右指針，需要保存原來的右孩子
    Node t3 = x.right;
    x.right = y;
    y.left = t3;
    //更新height
    y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
    x.height = Math.max(getHeight(x.left),getHeight(x.right))+1;
    return x;
}

  1. RR（左旋）

    左旋操作
    /**
 * 左旋轉(zhuǎn)
 */
private Node leftRotate(Node y){
 Node x = y.right;
 Node t2 = x.left;
 x.left = y;
 y.right = t2;
 //更新height
 y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
 x.height = Math.max(getHeight(x.left),getHeight(x.right))+1;
 return x;
}

  1. LR（雙旋）

    image-20201209203744422
    private Node LRRotate(Node y){
    y.left = leftRotate(y.left);
    return rightRotate(y);
}

  2. RL（雙旋）

    image-20201209204242906
    private Node RLRotate(Node y){
    y.right = rightRotate(y.right);
    return leftRotate(y);
}

  3. 刪除結(jié)點類似于BST樹，但需要維護平衡性

B樹（又叫B-樹）和B+樹

  1. B樹

    又叫多路平衡搜索樹，一顆m叉的BTree特性如下（ceil()向上取整）：

    • 樹中每個節(jié)點最多包含m個孩子。
    • 除根節(jié)點與葉子節(jié)點外，每個節(jié)點至少有[ceil(m/2)]個孩子。
    • 若根節(jié)點不是葉子節(jié)點，則至少有兩個孩子。
    • 所有的葉子節(jié)點都在同一層。
    • 每個非葉子節(jié)點由n個key與n+1個指針組成，其中[ceil(m/2)-1] <= n <= m-1

? 以5叉BTree為例，key的數(shù)量：公式推導(dǎo)[ceil(m/2)-1] <= n <= m-1。所以 2 <= n <=4 。當n>4時，中間節(jié)點分裂到父節(jié)點，兩邊節(jié)點分裂。
? 插入 C N G A H E K Q M F W L T Z D P R X Y S 數(shù)據(jù)為例。

image-20201209221931890
image-20201209222034582
image-20201209222058261
image-20201209222116477

  1. B+樹

    image-20201209222155086

    MySQL中的B+樹

    image-20201209222244742
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 面試題58：二叉樹的下一個節(jié)點給定一個二叉樹和其中一個節(jié)點，如何找到中序遍歷順序的下一個節(jié)點？樹中的節(jié)點除了有兩個...
    小逗比兒閱讀 235評論 0贊 0
  • https://blog.csdn.net/Monster_ii/article/details/82115772...
    快樂的老周閱讀 364評論 0贊 0
  • 二叉樹的問題，一定要明白到底應(yīng)該深度優(yōu)先（前中后序）還是廣度優(yōu)先（層序遍歷） 最基本的遍歷方式：深度優(yōu)先和廣度優(yōu)先...
    金色888閱讀 282評論 0贊 0
  • 樹的節(jié)點: 先序:１２４６７８３５先序走的 /_ 形狀 中序:４７６８２１３５中序走 /\ 形狀 后序：７８６４２...
    Tim在路上閱讀 968評論 0贊 0
  • 重建樹 遍歷樹 =================================================...
    YOLO哈哈哈閱讀 343評論 0贊 0

友情鏈接更多精彩內(nèi)容