亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

Java實現(xiàn)基本數(shù)據(jù)結構2（樹）

opengps / 1548人閱讀

摘要：實現(xiàn)基本數(shù)據(jù)結構棧，隊列，鏈表這篇筆記側重點二叉樹的三種遍歷前中后迭代非迭代代碼重建二叉樹的代碼與分析和關于二叉樹的題簡單理解二叉查找樹紅黑樹，的性質(zhì)，實際用途。同時，以對應的節(jié)點為邊界，就會把中序遍歷的結果分為左子樹和右子樹。

雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/
.. 拒絕伸手復制黨

以下是算法導論第十章的學習筆記 即 劍指offer題目
劍指offer電子書 見我的github https://github.com/GsmToday/JianZhi-offer/tree/master

前面總結了，棧，隊列，鏈表。 Java 實現(xiàn)基本數(shù)據(jù)結構 1（棧，隊列，鏈表）
這篇筆記側重點：
1 二叉樹的三種遍歷（前中后）迭代非迭代代碼
2 重建二叉樹的代碼與分析 和 關于二叉樹的題 簡單理解
3 二叉查找樹, 紅黑樹，Btree的性質(zhì)，實際用途。比如hashmap用到了紅黑樹

1. 二叉樹 1.1 性質(zhì)

二叉樹最重要的操作某過于遍歷，namely 按照某一順序訪問樹中的所有節(jié)點。
通常有四種遍歷方式：

深度優(yōu)先：

- 前序遍歷 （根-左-右）10,6,4,8,14,12,16
用途：1 拷貝樹。 2 計算前綴表達式
- 中序遍歷 （左-根-右）4,6,8,10,12,14,16
用途：BST（二叉搜索樹）的中序遍歷以非降序方式輸出節(jié)點。
- 后序遍歷 （右-左-根）4,8,8,12,16,14,10
后序遍歷的用途：1 刪除樹 2 計算后綴表達式
2. 廣度優(yōu)先：
- 層序遍歷

二叉樹的遍歷時間復雜度，無論遞歸與否，方式與否，都是O(n). 這是因為每個算法都要遍歷每個節(jié)點僅僅一次。

1.2代碼 前序遍歷（遞歸） 
java    public static void preOrderTraverse(Treenode rootnode){
        Treenode p = rootnode;
        if(p!=null){
            System.out.println(p.value);
            preOrderTraverse(p.leftchild);
            preOrderTraverse(p.rightchild);
        }
        else return;
    }
前序遍歷（非遞歸）

樹的深度優(yōu)先遍歷，因為沒有parent指針，所有非遞歸形式一定要借助棧；相反，如果二叉樹的節(jié)點有parent指針，那么就不需要棧了。

先讓根進棧。只要棧不為空，就可以彈棧。每次彈出一個節(jié)點，要把它的左右節(jié)點進棧（右節(jié)點先進棧）。

java    public static void preOrderNonrecur(Treenode rootnode){
        if(rootnode==null){
            return;
        }
        Treenode p = rootnode;
        Stack stack = new Stack();
        stack.push(p);
        while(stack.isEmpty()!=true){
            p = stack.pop();
            System.out.println(p.value);
            if(p.rightchild != null ){
                stack.push(p.rightchild);
            }
            if(p.leftchild != null){
                stack.push(p.leftchild);
            }
        }
    }
中序遍歷（遞歸） 
java    public static void inOrderTraverse(Treenode rootnode){
        Treenode p = rootnode;
        if(p!=null){
            inOrderTraverse(p.leftchild);
            System.out.println(p.value);
            inOrderTraverse(p.rightchild);
        }
        else return;
    }
中序遍歷（非遞歸）:

current = root;

把current, current的左孩子，current的左孩子的左孩子都入棧,直至current = null -> 跳到step 3
（current = current.left, push(current)）

若current = null 且棧沒空，則彈棧，并訪問。current = 彈出的節(jié)點的右孩子 <- 十分重要，之后重復2。

geeksforgeeks思路參照link

java    public static void inOrderNonrecur(Treenode rootnode){
        if(rootnode==null){
            return;
        }

        Treenode current = rootnode;
        Stack stack = new Stack();
        while(current != null||stack.isEmpty()!=true){
            while(current!=null){
                stack.push(current);
                current = current.leftchild;
            }
            if(current==null){
                Treenode node = stack.pop();
                System.out.println(node.value);
                current = node.rightchild;
                }
        }   
    }
后序遍歷（遞歸) 
java    public static void postOrderTraverse(Treenode rootnode){
        Treenode p = rootnode;
        if(p!=null){
            postOrderTraverse(p.leftchild);
            postOrderTraverse(p.rightchild);
            System.out.println(p.value);
        }
        else return;
    }
后序遍歷（非遞歸）

1.1 創(chuàng)建一個空棧
2.1 當current is not null
a) 先右孩子進棧，然后current進棧
b) 設置current為左孩子
這樣從根節(jié)點，down to 最左孩子節(jié)點。最后current == null

2.2 出棧，設置出棧的節(jié)點為current
既然出棧了，該節(jié)點肯定沒有左孩子。
a) 如果出棧節(jié)點存在右孩子
并且 右孩子是棧頂^1（這個是必要的，原因下面講）
并且 棧不為空 ^2（這個是必要的，原因下面講）,
則 再彈棧（彈出右孩子），把current指向的剛剛出棧的節(jié)點（右孩子的爹）入棧。
設置 current = current.right;
b) 如果出棧節(jié)點不存在右孩子，那么就可以訪問之。記得設置current = null
2.3 重復 2.1 and 2.2 直到?？?

^1 請看例子：
如果current指向6，他存在右孩子，但是這個時候他的孩子節(jié)點都已經(jīng)訪問完畢，沒必要再把8入棧。所以要判斷。
^2 判斷條件2出現(xiàn)在遍歷根節(jié)點的時候，因為訪問一個節(jié)點的時機必是彈棧之后，當根節(jié)點彈棧之后，棧已空，所以stack.peek（）會報錯。

geeksforgeeks思路參照link

java    public static void postOrderNonrecur(Treenode rootnode){
        if(rootnode==null){
            return;
        }   
        Stack stack = new Stack();
        Treenode current = rootnode;
        while(current !=null || stack.isEmpty()!=true){     
            //step 1 
            while(current!=null){   
                if(current.rightchild!=null){
                    stack.push(current.rightchild);
                }
                stack.push(current);
                current = current.leftchild;
            }

            // step2 既然出棧了，該節(jié)點肯定沒有左孩子。
            current = stack.pop();
    　　　　if(current.rightchild!=null && !stack.isEmpty() && current.rightchild == stack.peek())  {
                    stack.pop(); //出棧右孩子
                    stack.push(current);
                    current = current.rightchild;
            }
            else{
                System.out.println(current.value);
                current = null;
            }
        }
    }
層序遍歷（遞歸）

先介紹下如何計算樹的高度
樹的高度的定義："height of the root"
節(jié)點高度的定義："number of edges in longest path from the node to a leaf node". 如：葉子節(jié)點的高度是0.
計算高度的時候，利用遞歸,從父節(jié)點到子節(jié)點，直至葉子節(jié)點，設置葉子節(jié)點的高度是0。再從葉子回到父節(jié)點，直至跟根節(jié)點，height(parentnode) = max(height(left),height(son))+1

節(jié)點深度的定義："number of edges in path from root to that node"

java    public static int height(Treenode rootnode){
        if(rootnode == null){
            return -1;
        }
        int lheight = height(rootnode.leftchild); 計算該節(jié)點左孩子的高度
        int rheight = height(rootnode.rightchild); 計算該節(jié)點右孩子的高度
        return Math.max(lheight, rheight)+1; 返回給該節(jié)點自己的高度
    }

貼的是我在leetcode AC 的代碼

javapublic class Solution {
       public List> levelOrder(TreeNode rootnode) {
        List> resultlist = new ArrayList>();

        for(int level = 0; level<= height(rootnode);level++)
        {
            List list = new ArrayList();
            printGivenLevel(rootnode,level,list);
            resultlist.add(list);
        }
        return resultlist;

    }
    public int height(TreeNode rootnode){
        if(rootnode==null){
            return -1;
        }
        else{
            return Math.max(height(rootnode.left),height(rootnode.right))+1;
        }
    }
    public void printGivenLevel(TreeNode rootnode, int level, List list){
        if(rootnode==null){
            return;
        }   
        if(level == 0){
            list.add(rootnode.val);
        }
        else{
            printGivenLevel(rootnode.left, level-1, list);
            printGivenLevel(rootnode.right, level-1, list);
        }
    }
}

思路參照

層序遍歷（非遞歸）

無論是樹，還是圖的廣度優(yōu)先遍歷，都要使用先進先出的隊列結構。
步驟：
1. 創(chuàng)建隊列
2. tempnode = root
3. tempnode 不是 null時候循環(huán)
a） 輸出tempnode.value
b) 將tempnode的孩子入隊（先左后右）
c) 出隊，把出隊的值賦予tempvalue

java    public static void LevelOrderNonRecur(Treenode rootnode){
        Treenode tempnode = rootnode; 
        ArrayDeque queue=new ArrayDeque();

        if(rootnode==null){
            return;
        }   
        queue.add(tempnode);
        while(queue.isEmpty()!=true){
            tempnode = queue.remove();
            System.out.println(tempnode.value);
            if(tempnode.leftchild!=null)
                queue.add(tempnode.leftchild);
            if(tempnode.rightchild!=null)
                queue.add(tempnode.rightchild);
        }       
    }
2 二叉樹的題 2.1 線性時間判斷一個樹是否是平衡二叉樹：

最直接的方法是遍歷樹的每個節(jié)點的時候，調(diào)用函數(shù)的TreeDepth得到他的左右節(jié)點的高度，如果每個節(jié)點的左右子樹的高度相差不超過 1. 則它就是一顆平衡二叉樹。

但是在計算一個節(jié)點的深度的時候，就把該節(jié)點和該節(jié)點level以下的所有節(jié)點都遍歷了。 因此，一個節(jié)點會被重復遍歷多次，這種思路的時間效率不高。所以，效率更高的做法是在計算高度的時候，邊計算邊判斷。
思路參考

java  private int getHeight(TreeNode root) {  
      if (root == null) return 0;  
      int depL = getHeight(root.left);  
      int depR = getHeight(root.right);  
      if (depL < 0 || depR < 0 || Math.abs(depL - depR) > 1) return -1;  返回給該節(jié)點自己的value
      else return Math.max(depL, depR) + 1;    返回給該節(jié)點自己的value
    }  
    public boolean isBalanced(TreeNode root) {  
      return (getHeight(root) >= 0);  
    }
2.2 輸入兩棵二叉樹A，B，判斷B是不是A的子結構。 
java   //遍歷Tree1,查找與Tree2 root相同的節(jié)點
  boolean  HasSubtree(TreeNode root1, TreeNode root2){
        boolean result = false;
        if(root1 != null && root2 != null){
            if(root1.val == root2.val){
                //查找到與Tree2 root相同的節(jié)點，接著判斷二者是否具有相同結構
                result = DoesTree1hasTree2(root1,root2);
            }
            if(result != true)
                result = HasSubtree(root1.left, root2);
            if(result != true)
                result = HasSubtree(root1.right, root2);    
        }
        return result;
    }


java   boolean  DoesTree1hasTree2(TreeNode root1, TreeNode root2){
        boolean lflag = false;
        boolean rflag = false;
        //Tree2結束
        if(root2==null){
            return true;
        }
        //Tree2有節(jié)點時候，Tree1還有，說明肯定不是包含關系
        if(root1==null){
            return false;
        }
        if(root1.val != root2.val){
            return false;
        }
        else{
            lflag = DoesTree1hasTree2(root1.left,root2.left);
            rflag = DoesTree1hasTree2(root1.right,root2.right);
            return lflag && rflag;
        }
    }
2.3 輸入某二叉樹的前序遍歷和中序遍歷結果，請重建二叉樹 ，假設前序遍歷和中序遍歷中不含重復數(shù)字。

思路： 前序遍歷的每一個節(jié)點都是當前子樹的根節(jié)點。同時，以對應的節(jié)點為邊界，就會把中序遍歷的結果分為左子樹和右子樹。

java     public static TreeNode buildTree(int[] preOrder,int start, int[] inOrder,
int end,int length){    
            // 邊界驗證      
            if (preOrder == null || preOrder.length == 0 || inOrder == null    
                    || inOrder.length == 0 || length <= 0) {    
                return null;    
            }    

            //根據(jù) 前序遍歷的第一個元素建立樹根節(jié)點      
            int value = preOrder[start];    
            TreeNode root = new TreeNode();    
            root.val = value;    

            // 遞歸終止條件：子樹只有一個節(jié)點      
            if (length == 1)    
                return root;    

            // 根據(jù) 前序遍歷的第一個元素在中序遍歷中的位置分拆樹的左子樹和右子樹      
            int i = 0;    
            while (i < length) {    
                if (value == inOrder[end - i]) {    
                    break;    
                }    
                i++;    
            }    

            // 建立子樹的左子樹      
            root.left = buildTree(preOrder, start + 1, inOrder,
             end - i - 1, length - 1 - i);    
            // 建立子樹的右子樹      
            root.right = buildTree(preOrder, start + length - i,
             inOrder, end, i);    

            return root;    
       }
2.3.1 根據(jù)中序+后序遍歷結果重構二叉樹 
java    public static TreeNode buildTree(int postOrder[], int pend, int inOrder[],int iend, int length){
        //boundary test
        if(postOrder == null || postOrder.length == 0 || inOrder == null || inOrder.length == 0 || postOrder.length != inOrder.length)
        {
            System.out.print("te");  
            return null;
        }
        //create root;
        TreeNode root = new TreeNode();
        int value = postOrder[pend];
        root.val = value;

        if(length ==1)
            return root;
        // search the index of the root in inorder
        int i =0;
        while(inOrder[iend-i]!=value){
            i++;
        }

        root.right =  buildTree(postOrder, pend-1, inOrder, iend,  i);  
        root.left =  buildTree(postOrder,  pend-i-1, inOrder, iend-i-1,  length-i-1);
        return root;

    }
2.4 二叉樹中和位某一值的所有路徑 
java    private static Stack stack=new Stack();

    public static void findPathk(TreeNode root,int k,int sum){
        boolean isLeaf = false;
        // 為了追溯路徑，需要記住棧記錄父節(jié)點
        stack.push(root);
        // 記錄路徑的sum
        sum = root.val + sum;
        // 判斷是否路徑到頭
        if(root.left == null && root.right==null){
            isLeaf = true;
        }
        // 路徑到頭且和達到k
        if(isLeaf && sum ==k){
            System.out.println(stack);
        }
        // 左子樹
        if(root.left != null){
            findPathk(root.left,k,sum);
        }
        // 右子樹
        if(root.right != null){
            findPathk(root.right,k,sum);
        }
        // 出棧
        stack.pop();
    }

想更一進步的支持我，請掃描下方的二維碼，你懂的~

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/64291.html

相關文章

  • Java數(shù)據(jù)結構與算法——樹（基本概念，很重要）

    摘要：有網(wǎng)友私信我，期待我的下一篇數(shù)據(jù)結構。前言數(shù)據(jù)結構與算法專題會不定時更新，歡迎各位讀者監(jiān)督。本文介紹數(shù)據(jù)結構里一些復雜的數(shù)據(jù)結構樹，相應的會補充一些算法。除根節(jié)點外，每個節(jié)點又可以分為多個不相交的子樹。 聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。有網(wǎng)友私信我，期待我的下一篇數(shù)據(jù)結構。非常榮幸文章被認可，也非常感謝你們的監(jiān)督。 前言：Java數(shù)據(jù)結構與算法專題會不定時更新，歡...

    MangoGoing 評論0 收藏0

  • Javag工程師成神之路（2019正式版）

    摘要：結構型模式適配器模式橋接模式裝飾模式組合模式外觀模式享元模式代理模式。行為型模式模版方法模式命令模式迭代器模式觀察者模式中介者模式備忘錄模式解釋器模式模式狀態(tài)模式策略模式職責鏈模式責任鏈模式訪問者模式。 主要版本 更新時間 備注 v1.0 2015-08-01 首次發(fā)布 v1.1 2018-03-12 增加新技術知識、完善知識體系 v2.0 2019-02-19 結構...

    Olivia 評論0 收藏0

  • 一名3年工作經(jīng)驗的java程序員應該具備的職業(yè)技能

    摘要：一名年工作經(jīng)驗的程序員應該具備的技能，這可能是程序員們比較關心的內(nèi)容。數(shù)據(jù)結構和算法分析數(shù)據(jù)結構和算法分析，對于一名程序員來說，會比不會好而且在工作中能派上用場。 一名3年工作經(jīng)驗的Java程序員應該具備的技能，這可能是Java程序員們比較關心的內(nèi)容。我這里要說明一下，以下列舉的內(nèi)容不是都要會的東西—-但是如果你掌握得越多，最終能得到的評價、拿到的薪水勢必也越高。 1、基本語法 這包括...

    renweihub 評論0 收藏0

  • 數(shù)據(jù)結構與算法（十四）深入理解紅黑樹和JDK TreeMap和TreeSet源碼分析

    摘要：很多文章或書籍在介紹紅黑樹的時候直接上來就是紅黑樹的個基本性質(zhì)插入刪除操作等。這也不奇怪，算法的作者就是紅黑樹的作者之一。所以，理解樹對掌握紅黑樹是至關重要的。 本文主要包括以下內(nèi)容： 什么是2-3樹 2-3樹的插入操作 紅黑樹與2-3樹的等價關系 《算法4》和《算法導論》上關于紅黑樹的差異 紅黑樹的5條基本性質(zhì)的分析 紅黑樹與2-3-4樹的等價關系 紅黑樹的插入、刪除操作 JDK ...

    curlyCheng 評論0 收藏0

  • 【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結構解析和算法實現(xiàn)-二分搜索樹

    摘要：在數(shù)據(jù)結構領域?qū)獦浣Y構來說二叉樹是最常用的一種樹結構，二叉樹具有一個唯一的根節(jié)點，也就是最上面的節(jié)點。二叉樹每個節(jié)點最多有兩個孩子，一個孩子都沒有的節(jié)點通常稱之為葉子節(jié)點，二叉樹每個節(jié)點最多有一個父親，根節(jié)點是沒有父親節(jié)點的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

    ghnor 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<