免费一级毛片正在播放,久久99热精品免费观看无卡顿,国产综合视频

樹結(jié)構(gòu)對(duì)于程序員來說應(yīng)該不陌生，特別是二叉樹，基本只要接觸算法這一類的都一定會(huì)碰到的，所以我打算通過一篇文章，對(duì)二叉樹結(jié)構(gòu)的相關(guān)算法進(jìn)行總結(jié)匯總，思路和代碼實(shí)現(xiàn)相結(jié)合，讓你不在懼怕二叉樹。（ps：后面我還想寫一篇樹結(jié)構(gòu)的高級(jí)篇，就是多叉數(shù)，就是對(duì)我平時(shí)看算法論文碰到的一些新奇的算法，比如B樹、B+樹，還有我一種叫做Bed樹的新奇算法等等）

單純就是想分享技術(shù)博文，還想說一句就是，如果覺得有用，請(qǐng)點(diǎn)個(gè)關(guān)注、給個(gè)贊吧，也算對(duì)我來說是個(gè)寬慰，畢竟也得掉不少頭發(fā)，嘿嘿嘿。

下面的思路講解中，我會(huì)給出一個(gè)類偽代碼的思路，然后進(jìn)行相關(guān)說明，也就是一種思路框架，有了思路框架，以后碰到問題就直接交給框架完成。本文主要說一下二叉搜索樹（Binary Search Tree，簡(jiǎn)稱 BST），BST是一種很常用的的二叉樹。它的定義是：一個(gè)二叉樹中，任意節(jié)點(diǎn)的值要大于等于左子樹所有節(jié)點(diǎn)的值，且要小于等于右邊子樹的所有節(jié)點(diǎn)的值。如下就是一個(gè)符合定義的 BST：

后面如果遇到特殊的思路結(jié)構(gòu)，如多叉樹，我會(huì)特別說明。首先我們先給出二叉樹的節(jié)點(diǎn)定義（這個(gè)定義應(yīng)該不陌生吧，有刷算法題都會(huì)碰到）。

public class TreeNode {

      int val;

      TreeNode left;

      TreeNode right;

      TreeNode(int x) { val = x; }

}

遞歸

不過這里要說明一點(diǎn)的是，在偽代碼中的“進(jìn)行想要的操作”的位置，不一定就在我放置的位置，具體位置還需要我們根據(jù)不同的實(shí)際需求進(jìn)行判斷。不過因?yàn)榍爸泻笮虻谋闅v，遞歸進(jìn)入的時(shí)機(jī)應(yīng)該需要和我的一樣。

先序遍歷

遍歷根節(jié)點(diǎn)，如果根節(jié)點(diǎn)為空，返回；否則，遍歷根節(jié)點(diǎn)，然后先序遍歷左子樹，再先序遍歷右子樹。

public void preorderTraverse(TreeNode root){

    System.out.print(node.val+' ');

    preorderTraverse(root.left);

    preorderTraverse(root.right);

}

中序遍歷

路過根節(jié)點(diǎn)，如果根節(jié)點(diǎn)為空，返回；否則，中序遍歷左子樹，然后遍歷根節(jié)點(diǎn)，再中序遍歷右子樹。

public void inorderTraverse(TreeNode root){

    inorderTraverse(root.left);

    System.out.print(node.val+' ');

    inorderTraverse(root.right);

}

后序遍歷

路過根節(jié)點(diǎn)，如果根節(jié)點(diǎn)為空，返回；否則，后序遍歷左子樹，再后序遍歷右子樹，最后遍歷根節(jié)點(diǎn)。

public void postorderTraverse(TreeNode root){

    postorderTraverse(root.left);

    postorderTraverse(root.right);

    System.out.print(node.val+' ');

}

迭代（非遞歸）

我們使用迭代的思想，其實(shí)就是利用循環(huán)和棧來模擬遞歸的操作，上面遞歸的操作，其實(shí)就是一個(gè)不斷將自己以及左右子節(jié)點(diǎn)進(jìn)行壓棧和出棧的過程，如果理解了上面的算法下面的算法就好理解了

前序遍歷

public List<Integer> preorderTraversal(TreeNode root) {

    List<Integer> list = new ArrayList<>();

    if(root==null){

        return list;

    }

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

    stack.push(root);

    while(!stack.isEmpty()){

        TreeNode res = stack.pop();

        if(res.right != null)

            stack.push(res.right);

        if(res.left != null)

            stack.push(res.left);

        list.add(res.val);

    }

    return list;

}

中序遍歷

public List<Integer> inorderTraversal(TreeNode root) {

    List<Integer> list = new ArrayList<>();

    if(root==null){

        return list;

    }

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

    TreeNode curr = root;

    while(curr != null || !(stack.isEmpty())){

        if(curr!= null){

            stack.push(curr);

            curr = curr.left;

        }else{

            curr = stack.pop();

            list.add(curr.val);

            curr = curr.right;

        }

    }

    return list;

}

后序遍歷

我們可以很簡(jiǎn)單的實(shí)現(xiàn)另一種遍歷：”根->右->左“遍歷。雖然這種遍歷沒有名字，但是他是后序遍歷的反序。所以我們可以利用兩個(gè)棧，利用棧的LIFO特點(diǎn)，來實(shí)現(xiàn)后續(xù)遍歷。

public List<Integer> preorderTraversal(TreeNode root) {

    List<Integer> list = new ArrayList<>();

    if(root==null){

        return list;

    }

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

    stack.push(root);

    while(!stack.isEmpty()){

        TreeNode res = stack.pop();

        if(res.left != null)

            stack.push(res.left);

        if(res.right != null)

        stack.push(res.right);

        list.add(res.val);

    }

    list.reserve();

    return list;

}

深度優(yōu)先搜索（DFS）

其實(shí)，二叉樹的先序遍歷，中序遍歷，后序遍歷，都是深度優(yōu)先搜索，深搜是一種思想，并不具體指代實(shí)現(xiàn)方式，你可以使用遞歸，也可以使用棧來實(shí)現(xiàn)，所以上面提到的都是深度優(yōu)先搜索的實(shí)現(xiàn)方式，畢竟“深度優(yōu)先”嘛。

那在這里我就是提幾個(gè)實(shí)際的應(yīng)用的例子，加深一下印象。

二叉樹的最大深度

public int maxDepth(TreeNode root) {

    if(root==null){

        return 0;

    }

    int left = maxDepth(root.left);

    int right = maxDepth(root.right);

    return Math.max(left,right)+1;

}

二叉樹的鏡像

public void Mirror(TreeNode root) {

    if(root!=null){

        if(root.left!=null || root.right!= null){

            TreeNode temp =root.left;

            root.left=root.right;

            root.right=temp;

        }

        Mirror(root.left);

        Mirror(root.right);

    }

}

對(duì)稱二叉樹

boolean isSymmetrical(TreeNode pRoot){

    if(pRoot == null)

        return true;

    return real(pRoot.left,pRoot.right);

}

public boolean real(TreeNode root1,TreeNode root2){

    if(root1 == null && root2 == null){

        return true;

    }

    if(root1 ==null || root2 == null){

        return false;

    }

    if(root1.val != root2.val){

        return false;

    }

    return real(root1.left,root2.right)&&real(root1.right,root2.left);

}

路徑總和

public class Solution {

    private ArrayList<Integer> list = new ArrayList<Integer>();

    private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {

        if(root == null)

            return listAll;

        list.add(root.val);

        target -= root.val;

        if(target == 0 && root.left==null && root.right == null){

            listAll.add(new ArrayList<Integer>(list));

        }

        FindPath(root.left,target);

        FindPath(root.right,target);

        list.remove(list.size()-1);

       return listAll;

    }

}

重建二叉樹

 public TreeNode reConstructBinaryTree(int [] pre,int [] in) {

    return reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);

}

public TreeNode reConstructBinaryTree(int [] pre,int startpre,int endpre,int [] in,int startin,int endin){

    if(startpre > endpre || startin > endin){

        return null;

    }

    TreeNode root = new TreeNode(pre[startpre]);

    for(int i =startin;i<=endin;i++){

        if(in[i] == pre[startpre]){

            root.left = reConstructBinaryTree(pre,startpre+1,startpre+i-startin,in,startin,i-1);

            root.right = reConstructBinaryTree(pre,startpre+i-startin+1,endpre,in,i+1,endin);

        }

    }

    return root;

}

二叉搜索樹的最近公共祖先

class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root == null || root == p || root == q){

            return root;

        }

        TreeNode left = lowestCommonAncestor(root.left,p,q);

        TreeNode right = lowestCommonAncestor(root.right,p,q);

        if(left!=null && right!=null){

            return root;

        }

        return left!=null?left:right;

    }

}

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

序列化：

public String serialize(TreeNode root) {

    if (root == null) {

        return null;

    }

    // 利用二叉樹的層次遍歷方式進(jìn)行序列化

    StringBuilder res = new StringBuilder();

    LinkedList<TreeNode> queue = new LinkedList<>();

    queue.add(root);

    while (!queue.isEmpty()) {

        TreeNode node = queue.remove();

        if (node != null) {

            res.append(node.val).append(',');

            queue.add(node.left);

            queue.add(node.right);

        } else {

            res.append('null,');

        }

    }

    return res.toString();

}

反序列化：

public TreeNode deserialize(String data) {

    if (data == null || data.length() == 0) {

        return null;

    }

    String[] dataArr = data.split(',');

    // 層次遍歷逆向還原二叉樹

    int index = 0;

    TreeNode root = toNode(dataArr[index]);

    LinkedList<TreeNode> queue = new LinkedList<>();

    queue.add(root);

    while (index < dataArr.length - 2 && !queue.isEmpty()) {

        TreeNode cur = queue.remove();

        // 添加左子節(jié)點(diǎn)

        TreeNode leftNode = toNode(dataArr[++index]);

        cur.left = leftNode;

        // 隊(duì)列中的節(jié)點(diǎn)用于為其賦值孩子節(jié)點(diǎn)，若該節(jié)點(diǎn)本身為 null，

        // 沒有孩子節(jié)點(diǎn)，便不再添加到隊(duì)列中，下同理

        if (leftNode != null) {

            queue.add(leftNode);

        }

        // 添加右子節(jié)點(diǎn)

        TreeNode rightNode = toNode(dataArr[++index]);

        cur.right = rightNode;

        if (rightNode != null) {

            queue.add(rightNode);

        }

    }

    return root;

}



private TreeNode toNode(String val) {

    if (!'null'.equals(val)) {

        return new TreeNode(Integer.parseInt(val));

    } else {

        return null;

    }

}

廣度優(yōu)先搜索（BFS）

首先將根節(jié)點(diǎn)放入隊(duì)列中。
從隊(duì)列中取出第一個(gè)節(jié)點(diǎn)，并檢驗(yàn)它是否為目標(biāo)。
如果找到目標(biāo)，則結(jié)束搜索并回傳結(jié)果。
否則將它所有尚未檢驗(yàn)過的直接子節(jié)點(diǎn)加入隊(duì)列中。
若隊(duì)列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜索的目標(biāo)。結(jié)束搜索并回傳“找不到目標(biāo)”。
重復(fù)步驟2。

public List<List<Integer>> levelOrder(TreeNode root) {

    List<List<Integer>> res = new ArrayList<List<Integer>>();

    List<TreeNode> quene = new ArrayList<TreeNode>();

    if(root == null){

        return res;

    }

    quene.add(root);

    while(quene.size()!=0){

        int count = quene.size();

        List<Integer> list = new ArrayList<Integer>();

        while(count>0){

            TreeNode temp =quene.remove(0);

            list.add(temp.val);

            if(temp.left!=null){

                quene.add(temp.left);

            }

            if(temp.right!=null){

                quene.add(temp.right);

            }

            count--;

        }

        res.add(list);

    }

    return res;

}

莫里斯遍歷（Morris）

通常我們對(duì)于二叉樹進(jìn)行遍歷時(shí)，使用遞歸遍歷或是基于棧來遍歷，這兩種方法都擁有最差為O(n)的空間復(fù)雜度(遞歸方法會(huì)在遞歸調(diào)用上浪費(fèi)更多的時(shí)間)，以及O(n)的時(shí)間復(fù)雜度。對(duì)于時(shí)間復(fù)雜度來說，由于需要遍歷每個(gè)元素一次，所以O(shè)(n)已是最優(yōu)情況。如此只能對(duì)空間進(jìn)行優(yōu)化。Morris遍歷如何做到的呢？首先我們需要分析遞歸和基于棧的遍歷它們?yōu)槭裁从蠴(n)的空間占用。以下圖這個(gè)簡(jiǎn)單的二叉樹遍歷為例：

例如進(jìn)行中序遍歷(LDR)，從1開始：

1有左孩子2，將1放入棧中，移動(dòng)到節(jié)點(diǎn)2；
2有左孩子4，將2放入棧中，移動(dòng)到節(jié)點(diǎn)4；
4左孩子為空，輸出節(jié)點(diǎn)4，此時(shí)節(jié)點(diǎn)4右孩子也為空，彈?；氐焦?jié)點(diǎn)2；
輸出節(jié)點(diǎn)2，節(jié)點(diǎn)2有右孩子5，移動(dòng)到節(jié)點(diǎn)5；
5左孩子為空，輸出節(jié)點(diǎn)5，此時(shí)節(jié)點(diǎn)5右孩子也為空，彈?；氐焦?jié)點(diǎn)1；

…

從上面分析可以得知，傳統(tǒng)遍歷利用空間存儲(chǔ)未實(shí)現(xiàn)全部操作的父節(jié)點(diǎn)，比如對(duì)于1節(jié)點(diǎn)，一開始進(jìn)行L操作，沒有進(jìn)行D、R操作所以需要存儲(chǔ)起來。為解決這一問題，Morris算法用到了”線索二叉樹”的概念，利用葉節(jié)點(diǎn)的左右空指針指向某種遍歷順序的前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn)。Morris算法中序遍歷流程：

設(shè)置節(jié)點(diǎn)1為Current節(jié)點(diǎn)；
Current節(jié)點(diǎn)不為空，且有左孩子，于是找到節(jié)點(diǎn)1左子樹中的最右側(cè)節(jié)點(diǎn)，即節(jié)點(diǎn)5，使其右孩子指針指向自己，即link1；
Current節(jié)點(diǎn)移動(dòng)到左孩子節(jié)點(diǎn)2，并刪除父節(jié)點(diǎn)的左指針，使其指向?yàn)閚ull，即刪除erase1；
節(jié)點(diǎn)2不為空，且有左孩子，于是找到節(jié)點(diǎn)2左子樹中最右側(cè)節(jié)點(diǎn)，即節(jié)點(diǎn)4，使其右孩子指針指向自己，即link2；
Current節(jié)點(diǎn)移動(dòng)到左孩子節(jié)點(diǎn)4，并刪除父節(jié)點(diǎn)的左指針，使其指向?yàn)閚ull，即刪除erase2；
節(jié)點(diǎn)4左孩子為空，輸出節(jié)點(diǎn)4，移動(dòng)到右孩子節(jié)點(diǎn)2；
節(jié)點(diǎn)2無左孩子(指針指向null)，輸出節(jié)點(diǎn)2，移動(dòng)到右孩子節(jié)點(diǎn)5；
節(jié)點(diǎn)5無左孩子，輸出節(jié)點(diǎn)5，移動(dòng)到右孩子節(jié)點(diǎn)1；
節(jié)點(diǎn)2無左孩子(指針指向null)，輸出節(jié)點(diǎn)1，移動(dòng)到右孩子節(jié)點(diǎn)3；
…

代碼實(shí)現(xiàn)：

void Morris_inorderTraversal(TreeNode root) {

    TreeNode curr = root;

    TreeNode pre;

    while (curr != null) {   

        if (curr.left == null) {    // 左孩子為空

            System.out.print(curr.val+' ');

            curr = curr.right; 

        }

        else {   // 左孩子不為空

            // 找左子樹中的最右節(jié)點(diǎn)

            pre = curr.left; 

            while (pre.right != null) {  

                pre = pre.right;

            }

            // 刪除左孩子，防止循環(huán)

            pre.right = curr; 

            TreeNode temp = curr; 

            curr = curr.left; 

            temp.left = null;

        }

    }

}

AVL樹

AVL 樹是一種平衡二叉樹，平衡二叉樹遞歸定義如下：

左右子樹的高度差小于等于 1。
其每一個(gè)子樹均為平衡二叉樹。

為了保證二叉樹的平衡， AVL 樹引入了所謂監(jiān)督機(jī)制，就是在樹的某一部分的不平衡度超過一個(gè)閾值后觸發(fā)相應(yīng)的平衡操作。保證樹的平衡度在可以接受的范圍內(nèi)。既然引入了監(jiān)督機(jī)制，我們必然需要一個(gè)監(jiān)督指標(biāo)，以此來判斷是否需要進(jìn)行平衡操作。這個(gè)監(jiān)督指標(biāo)被稱為“平衡因子（Balance Factor）”。定義如下：

平衡因子：某個(gè)結(jié)點(diǎn)的左子樹的高度減去右子樹的高度得到的差值。

基于平衡因子，我們就可以這樣定義 AVL 樹。

AVL 樹：所有結(jié)點(diǎn)的平衡因子的絕對(duì)值都不超過 1 的二叉樹。

為了計(jì)算平衡因子，我們自然需要在節(jié)點(diǎn)中引入高度這一屬性。在這里，我們把節(jié)點(diǎn)的高度定義為其左右子樹的高度的最大值。因此，引入了高度屬性的 AVL 樹的節(jié)點(diǎn)定義如下：

public class TreeNode {

      int val;

      int height;

      TreeNode left;

      TreeNode right;

      TreeNode(int x) { val = x; }

}

這里的節(jié)點(diǎn)和上面的不同的地方在于，我們多加了一個(gè)高度，用來記錄每個(gè)節(jié)點(diǎn)的高度，如何得到每個(gè)節(jié)點(diǎn)的高度很簡(jiǎn)單，前面講的算法中任何一種思路都可以實(shí)現(xiàn)，我這里就不贅述了，不過這里要多說一點(diǎn)的是，與之對(duì)應(yīng)地，我們?cè)谶M(jìn)行如下操作時(shí)需要更新受影響的所有節(jié)點(diǎn)的高度：

在插入結(jié)點(diǎn)時(shí)，沿插入的路徑更新結(jié)點(diǎn)的高度值
在刪除結(jié)點(diǎn)時(shí)（delete），沿刪除的路徑更新結(jié)點(diǎn)的高度值

我們重新定義了節(jié)點(diǎn)之后，有了高度屬性，計(jì)算平衡因子的操作就得以很簡(jiǎn)單的實(shí)現(xiàn)，也就是某個(gè)節(jié)點(diǎn)的平衡因子=左節(jié)點(diǎn)高度-右節(jié)點(diǎn)高度。

當(dāng)平衡因子的絕對(duì)值大于 1 時(shí)，就會(huì)觸發(fā)樹的修正，或者說是再平衡操作。

樹的平衡化操作

二叉樹的平衡化有兩大基礎(chǔ)操作：左旋和右旋。左旋，即是逆時(shí)針旋轉(zhuǎn)；右旋，即是順時(shí)針旋轉(zhuǎn)。這種旋轉(zhuǎn)在整個(gè)平衡化過程中可能進(jìn)行一次或多次，這兩種操作都是從失去平衡的最小子樹根結(jié)點(diǎn)開始的(即離插入結(jié)點(diǎn)最近且平衡因子超過1的祖結(jié)點(diǎn))。其中，右旋操作示意圖如下

所謂右旋操作，就是把上圖中的 B 節(jié)點(diǎn)和 C 節(jié)點(diǎn)進(jìn)行所謂“父子交換”。在僅有這三個(gè)節(jié)點(diǎn)時(shí)候，是十分簡(jiǎn)單的。但是當(dāng) B 節(jié)點(diǎn)處存在右孩子時(shí)，事情就變得有點(diǎn)復(fù)雜了。我們通常的操作是：拋棄右孩子，將之和旋轉(zhuǎn)后的節(jié)點(diǎn) C 相連，成為節(jié)點(diǎn) C 的左孩子。這樣，對(duì)應(yīng)的代碼如下。

TreeNode treeRotateRight(TreeNode root) {

    TreeNode left = root.left;



    root.left = left.right; // 將將要被拋棄的節(jié)點(diǎn)連接為旋轉(zhuǎn)后的 root 的左孩子

    left.right = root; // 調(diào)換父子關(guān)系



    left.height = Math.max(treeHeight(left.left), treeHeight(left.right))+1;

    right.height = Math.max(treeHeight(right.left), treeHeight(right.right))+1;



    return left;

}

而左旋操作示意圖如下

左旋操作和右旋操作十分類似，唯一不同的就是需要將左右互換下。我們可以認(rèn)為這兩種操作是對(duì)稱的。代碼如下：

TreeNode treeRotateLeft(TreeNode root) {

    TreeNode right = root.ight;

    root.right = right.left;

    right.left = root;

    left.height = Math.max(treeHeight(left.left), treeHeight(left.right))+1;

    right->height = Math.max(treeHeight(right.left), treeHeight(right.right))+1;

    return right;

}

需要平衡的四種情況

LL 型

所謂 LL 型就是上圖左邊那種情況，即因?yàn)樵诟?jié)點(diǎn)的左孩子的左子樹添加了新節(jié)點(diǎn)，導(dǎo)致根節(jié)點(diǎn)的平衡因子變?yōu)?+2，二叉樹失去平衡。對(duì)于這種情況，對(duì)節(jié)點(diǎn) n 右旋一次即可。

RR 型

RR 型的情況和 LL 型完全對(duì)稱。只需要對(duì)節(jié)點(diǎn) n 進(jìn)行一次左旋即可修正。

LR 型

LR 就是將新的節(jié)點(diǎn)插入到了 n 的左孩子的右子樹上導(dǎo)致的不平衡的情況。這時(shí)我們需要的是先對(duì) i 進(jìn)行一次左旋再對(duì) n 進(jìn)行一次右旋。

RL 型

RL 就是將新的節(jié)點(diǎn)插入到了 n 的右孩子的左子樹上導(dǎo)致的不平衡的情況。這時(shí)我們需要的是先對(duì) i 進(jìn)行一次右旋再對(duì) n 進(jìn)行一次左旋。

這四種情況的判斷很簡(jiǎn)單。我們根據(jù)破壞樹的平衡性（平衡因子的絕對(duì)值大于 1）的節(jié)點(diǎn)以及其子節(jié)點(diǎn)的平衡因子來判斷平衡化類型。

平衡化操作的實(shí)現(xiàn)如下：

int treeGetBalanceFactor(TreeNode root) {

    if(root == NULL)

        return 0;

    else

        return x.left.height - x.right.height;

}



TreeNode treeRebalance(TreeNode root) {

    int factor = treeGetBalanceFactor(root);

    if(factor > 1 && treeGetBalanceFactor(root.left) > 0) // LL

        return treeRotateRight(root);

    else if(factor > 1 && treeGetBalanceFactor(root.left) <= 0) { //LR

        root.left = treeRotateLeft(root.left);

        return treeRotateRight(temp);

    } else if(factor < -1 && treeGetBalanceFactor(root.right) <= 0) // RR

        return treeRotateLeft(root);

    else if((factor < -1 && treeGetBalanceFactor(root.right) > 0) { // RL

        root.right = treeRotateRight(root.right);

        return treeRotateLeft(root);

    } else { // Nothing happened.

        return root;

    }

本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊舉報(bào)。

免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版