乡下人产国偷v产偷v自拍,国产午夜片在线观看,婷婷成人亚洲综合国产麻豆,久久综合给合久久狠狠狠9

    • <output id="e9wm2"></output>
    <s id="e9wm2"><nobr id="e9wm2"><ins id="e9wm2"></ins></nobr></s> 
    

    • 
    
    
      



    
      
        
      
            
        
      
        
      
    
      
    
      
        
      
        
      
            
            
      
                
      
                    
                
      
                搜索
            
      

            分享
                
            

            
            
            
            
            
            
            
            

            
        
      
    
      
    
      

    
      

    
      
        
      
        
      
        
      
        
      
            
      
                
      
                    
      【數(shù)據(jù)結(jié)構(gòu)與算法04】二叉樹
      
                    
                    
                    
                    
      
                         黃家v少
                        
                        
                        2018-04-22
                        
                            
                        
                    
      
                    
      
                        
                        
      
                    
      
                    
                    
      
                        
      
                            
                        
      
                        
      
                            
                                
      
                                    
                                        
      

                                        
                                        

                                        
             在有序數(shù)組中，可以快速找到特定的值，但是想在有序數(shù)組中插入一個(gè)新的數(shù)據(jù)項(xiàng)，就必須首先找出新數(shù)據(jù)項(xiàng)插入的位置，然后將比新數(shù)據(jù)項(xiàng)大的數(shù)據(jù)項(xiàng)向后移動(dòng)一位，來(lái)給新的數(shù)據(jù)項(xiàng)騰出空間，刪除同理，這樣移動(dòng)很費(fèi)時(shí)。顯而易見，如果要做很多的插入和刪除操作和刪除操作，就不該選用有序數(shù)組。
      

              另一方面，鏈表中可以快速添加和刪除某個(gè)數(shù)據(jù)項(xiàng)，但是在鏈表中查找數(shù)據(jù)項(xiàng)可不容易，必須從頭開始訪問鏈表的每一個(gè)數(shù)據(jù)項(xiàng)，直到找到該數(shù)據(jù)項(xiàng)為止，這個(gè)過(guò)程很慢。
      

              樹這種數(shù)據(jù)結(jié)構(gòu)，既能像鏈表那樣快速的插入和刪除，又能想有序數(shù)組那樣快速查找。這里主要實(shí)現(xiàn)一種特殊的樹——二叉（搜索）樹。二叉搜索樹有如下特點(diǎn)：一個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)的關(guān)鍵字值小于這個(gè)節(jié)點(diǎn)，右子節(jié)點(diǎn)的關(guān)鍵字值大于或等于這個(gè)節(jié)點(diǎn)。插入一個(gè)節(jié)點(diǎn)需要根據(jù)這個(gè)規(guī)則進(jìn)行插入。
      

              刪除節(jié)點(diǎn)時(shí)二叉搜索樹中最復(fù)雜的操作，但是刪除節(jié)點(diǎn)在很多樹的應(yīng)用中又非常重要，所以詳細(xì)研究并總結(jié)下特點(diǎn)。刪除節(jié)點(diǎn)要從查找要?jiǎng)h的節(jié)點(diǎn)開始入手，首先找到節(jié)點(diǎn)，這個(gè)要?jiǎng)h除的節(jié)點(diǎn)可能有三種情況需要考慮：
      

               ·該節(jié)點(diǎn)是葉節(jié)點(diǎn)，沒有子節(jié)點(diǎn)
      

               ·該節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)
      

               ·該節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
      

               第一種最簡(jiǎn)單，第二種也還是比較簡(jiǎn)單的，第三種就相當(dāng)復(fù)雜了。下面分析這三種刪除情況：
      

              要?jiǎng)h除葉節(jié)點(diǎn)，只需要改變?cè)摴?jié)點(diǎn)的父節(jié)點(diǎn)對(duì)應(yīng)子字段的值即可，由指向該節(jié)點(diǎn)改為null就可以了。垃圾回收器會(huì)自動(dòng)回收葉節(jié)點(diǎn)，不需要自己手動(dòng)刪掉；當(dāng)節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)時(shí)，這個(gè)節(jié)點(diǎn)只有兩個(gè)連接：連向父節(jié)點(diǎn)和連向它唯一的子節(jié)點(diǎn)。需要從這個(gè)序列中剪斷這個(gè)節(jié)點(diǎn)，把它的子節(jié)點(diǎn)直接連到它的父節(jié)點(diǎn)上即可，這個(gè)過(guò)程要求改變父節(jié)點(diǎn)適當(dāng)?shù)囊茫ㄗ笞庸?jié)點(diǎn)還是右子節(jié)點(diǎn)），指向要?jiǎng)h除節(jié)點(diǎn)的子節(jié)點(diǎn)即可；第三種情況最復(fù)雜，如果要?jiǎng)h除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)，就不能只用它的一個(gè)子節(jié)點(diǎn)代替它，比如要?jiǎng)h除節(jié)點(diǎn)25，如果用35取代它，那35的左子節(jié)點(diǎn)是15呢還是30？
      

      

          
      

              因此需要考慮另一種方法，尋找它的中序后繼來(lái)代替該節(jié)點(diǎn)。下圖顯示的就是要?jiǎng)h除節(jié)點(diǎn)用它的后繼代替它的情況，刪除后還是有序的。（這里還有更麻煩的情況，即它的后繼自己也有右子節(jié)點(diǎn)，下面再討論。）
      


      

              那么如何找后繼節(jié)點(diǎn)呢？首先得找到要?jiǎng)h除的節(jié)點(diǎn)的右子節(jié)點(diǎn)，它的關(guān)鍵字值一定比待刪除節(jié)點(diǎn)的大。然后轉(zhuǎn)到待刪除節(jié)點(diǎn)右子節(jié)點(diǎn)的左子節(jié)點(diǎn)那里（如果有的話），然后到這個(gè)左子節(jié)點(diǎn)的左子節(jié)點(diǎn)，以此類推，順著左子節(jié)點(diǎn)的路徑一直向下找，這個(gè)路徑上的最后一個(gè)左子節(jié)點(diǎn)就是待刪除節(jié)點(diǎn)的后繼。如果待刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)沒有左子節(jié)點(diǎn)，那么這個(gè)右子節(jié)點(diǎn)本身就是后繼。尋找后繼的示意圖如下：
      


      

              找到了后繼節(jié)點(diǎn)，現(xiàn)在開始刪除了，先看第一種情況，后繼節(jié)點(diǎn)是delNode右子節(jié)點(diǎn)的做后代，這種情況要執(zhí)行以下四個(gè)步驟：
      

               ·把后繼父節(jié)點(diǎn)的leftChild字段置為后繼的右子節(jié)點(diǎn)；
      

               ·把后繼的rightChild字段置為要?jiǎng)h除節(jié)點(diǎn)的右子節(jié)點(diǎn)；
      

               ·把待刪除節(jié)點(diǎn)從它父節(jié)點(diǎn)的leftChild或rightChild字段刪除，把這個(gè)字段置為后繼；
      

               ·把待刪除的左子節(jié)點(diǎn)移除，將后繼的leftChild字段置為待刪除節(jié)點(diǎn)的左子節(jié)點(diǎn)。
      
        如下圖所示：


      

              如果后繼節(jié)點(diǎn)就是待刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)，這種情況就簡(jiǎn)單了，因?yàn)橹恍枰押罄^為跟的子樹移到刪除的節(jié)點(diǎn)的位置即可。如下圖所示：
      


      

              看到這里，就會(huì)發(fā)現(xiàn)刪除時(shí)相當(dāng)棘手的操作。實(shí)際上，因?yàn)樗浅?fù)雜，一些程序員都嘗試著躲開它，他們?cè)贜ode類中加了一個(gè)Boolean字段來(lái)標(biāo)識(shí)該節(jié)點(diǎn)是否已經(jīng)被刪除，在其他操作之前會(huì)先判斷這個(gè)節(jié)點(diǎn)是不是已經(jīng)刪除了，這樣刪除節(jié)點(diǎn)不會(huì)改變樹的結(jié)構(gòu)，。當(dāng)然樹中還保留著這種已經(jīng)刪除的節(jié)點(diǎn)，對(duì)存儲(chǔ)造成浪費(fèi)，但是如果沒有那么多刪除的話，這也不失為一個(gè)好方法。下面是二叉搜索樹的主要代碼：
      

      1. public class BinaryTree {  
      2.     private BNode root; //根節(jié)點(diǎn)  
      3.       
      4.     public BinaryTree() {  
      5.         root = null;  
      6.     }  
      7.       
      8.     //二叉搜索樹查找的時(shí)間復(fù)雜度為O(logN)  
      9.     public BNode find(int key) { //find node with given key  
      10.         BNode current = root;  
      11.         while(current.key != key) {  
      12.             if(key < current.key) {  
      13.                 current = current.leftChild;  
      14.             }  
      15.             else {  
      16.                 current = current.rightChild;  
      17.             }  
      18.             if(current == null) {  
      19.                 return null;  
      20.             }  
      21.         }  
      22.         return current;  
      23.     }  
      24.       
      25.     //插入節(jié)點(diǎn)  
      26.     public void insert(int key, double value) {  
      27.         BNode newNode = new BNode();  
      28.         newNode.key = key;  
      29.         newNode.data = value;  
      30.         if(root == null) { //if tree is null  
      31.             root = newNode;  
      32.         }  
      33.         else {  
      34.             BNode current = root;  
      35.             BNode parent;  
      36.             while(true) {  
      37.                 parent = current;  
      38.                 if(key < current.data) { //turn left  
      39.                     current = current.leftChild;  
      40.                     if(current == null) {  
      41.                         parent.leftChild = newNode;  
      42.                         newNode.parent = parent;  
      43.                         return;  
      44.                     }  
      45.                 }  
      46.                 else { //turn right  
      47.                     current = current.rightChild;  
      48.                     if(current == null) {  
      49.                         parent.rightChild = newNode;  
      50.                         newNode.parent = parent;  
      51.                         return;  
      52.                     }  
      53.                 }  
      54.             }  
      55.         }  
      56.     }  
      57.       
      58.     //遍歷二叉樹  
      59.     public void traverse(int traverseType) {  
      60.         switch(traverseType)  
      61.         {  
      62.         case 1: System.out.println("Preorder traversal:");  
      63.                 preOrder(root);//前向遍歷  
      64.                 break;  
      65.         case 2: System.out.println("Inorder traversal:");  
      66.                 inOrder(root);//中向遍歷  
      67.                 break;  
      68.         case 3: System.out.println("Postorder traversal:");  
      69.                 postOrder(root);//后向遍歷  
      70.                 break;  
      71.         default: System.out.println("Inorder traversal:");  
      72.                 inOrder(root);  
      73.                 break;  
      74.         }  
      75.         System.out.println("");  
      76.     }  
      77.       
      78.     //前向遍歷  
      79.     private void preOrder(BNode localRoot) {  
      80.         if(localRoot != null) {  
      81.             System.out.print(localRoot.data + " ");  
      82.             preOrder(localRoot.leftChild);  
      83.             preOrder(localRoot.rightChild);  
      84.         }  
      85.     }  
      86.       
      87.     //中向遍歷  
      88.     private void inOrder(BNode localRoot) {  
      89.         if(localRoot != null) {  
      90.             inOrder(localRoot.leftChild);  
      91.             System.out.print(localRoot.data + " ");  
      92.             inOrder(localRoot.rightChild);  
      93.         }  
      94.     }  
      95.       
      96.     //后向遍歷  
      97.     private void postOrder(BNode localRoot) {  
      98.         if(localRoot != null) {  
      99.             postOrder(localRoot.leftChild);  
      100.             postOrder(localRoot.rightChild);  
      101.             System.out.print(localRoot.data + " ");  
      102.         }  
      103.     }  
      104.       
      105.     //查找最小值  
      106.     /*根據(jù)二叉搜索樹的存儲(chǔ)規(guī)則，最小值應(yīng)該是左邊那個(gè)沒有子節(jié)點(diǎn)的那個(gè)節(jié)點(diǎn)*/  
      107.     public BNode minNumber() {  
      108.         BNode current = root;  
      109.         BNode parent = root;  
      110.         while(current != null) {  
      111.             parent = current;  
      112.             current = current.leftChild;  
      113.         }     
      114.         return parent;  
      115.     }  
      116.       
      117.     //查找最大值  
      118.     /*根據(jù)二叉搜索樹的存儲(chǔ)規(guī)則，最大值應(yīng)該是右邊那個(gè)沒有子節(jié)點(diǎn)的那個(gè)節(jié)點(diǎn)*/  
      119.     public BNode maxNumber() {  
      120.         BNode current = root;  
      121.         BNode parent = root;  
      122.         while(current != null) {  
      123.             parent = current;  
      124.             current = current.rightChild;  
      125.         }     
      126.         return parent;  
      127.     }  
      128.       
      129.     //刪除節(jié)點(diǎn)  
      130.     /* 
      131.      * 刪除節(jié)點(diǎn)在二叉樹中是最復(fù)雜的，主要有三種情況： 
      132.      * 1. 該節(jié)點(diǎn)沒有子節(jié)點(diǎn)（簡(jiǎn)單） 
      133.      * 2. 該節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)（還行） 
      134.      * 3. 該節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)（復(fù)雜） 
      135.      * 刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(logN) 
      136.      */  
      137.     public boolean delete(int key) {  
      138.         BNode current = root;  
      139. //      BNode parent = root;  
      140.         boolean isLeftChild = true;  
      141.           
      142.         if(current == null) {  
      143.             return false;  
      144.         }  
      145.         //尋找要?jiǎng)h除的節(jié)點(diǎn)  
      146.         while(current.data != key) {  
      147. //          parent = current;  
      148.             if(key < current.key) {  
      149.                 isLeftChild = true;  
      150.                 current = current.leftChild;  
      151.             }  
      152.             else {  
      153.                 isLeftChild = false;  
      154.                 current = current.rightChild;  
      155.             }  
      156.             if(current == null) {  
      157.                 return false;  
      158.             }  
      159.         }  
      160.           
      161.         //找到了要?jiǎng)h除的節(jié)點(diǎn)，下面開始刪除  
      162.         //1. 要?jiǎng)h除的節(jié)點(diǎn)沒有子節(jié)點(diǎn),直接將其父節(jié)點(diǎn)的左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)賦為null即可  
      163.         if(current.leftChild == null && current.rightChild == null) {  
      164.             return deleteNoChild(current, isLeftChild);  
      165.         }  
      166.           
      167.         //3. 要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)  
      168.         else if(current.leftChild != null && current.rightChild != null) {  
      169.             return deleteTwoChild(current, isLeftChild);  
      170.         }  
      171.           
      172.         //2. 要?jiǎng)h除的節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)，直接將其砍斷，將其子節(jié)點(diǎn)與其父節(jié)點(diǎn)連起來(lái)即可，要考慮特殊情況就是刪除根節(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)沒有父節(jié)點(diǎn)  
      173.         else {  
      174.             return deleteOneChild(current, isLeftChild);  
      175.         }  
      176.           
      177.     }  
      178.       
      179.     public boolean deleteNoChild(BNode node, boolean isLeftChild) {  
      180.         if(node == root) {  
      181.             root = null;  
      182.             return true;  
      183.         }  
      184.         if(isLeftChild) {  
      185.             node.parent.leftChild = null;  
      186.         }  
      187.         else {  
      188.             node.parent.rightChild = null;  
      189.         }  
      190.         return true;  
      191.     }  
      192.       
      193.     public boolean deleteOneChild(BNode node, boolean isLeftChild) {  
      194.         if(node.leftChild == null) {  
      195.             if(node == root) {  
      196.                 root = node.rightChild;  
      197.                 node.parent = null;  
      198.                 return true;  
      199.             }  
      200.             if(isLeftChild) {  
      201.                 node.parent.leftChild  = node.rightChild;  
      202.             }  
      203.             else {  
      204.                 node.parent.rightChild = node.rightChild;  
      205.             }  
      206.             node.rightChild.parent = node.parent;  
      207.         }  
      208.         else {  
      209.             if(node == root) {  
      210.                 root = node.leftChild;  
      211.                 node.parent = null;  
      212.                 return true;  
      213.             }  
      214.             if(isLeftChild) {  
      215.                 node.parent.leftChild  = node.leftChild;  
      216.             }  
      217.             else {  
      218.                 node.parent.rightChild = node.leftChild;  
      219.             }  
      220.             node.leftChild.parent = node.parent;  
      221.         }  
      222.         return true;  
      223.     }  
      224.       
      225.     public boolean deleteTwoChild(BNode node, boolean isLeftChild) {  
      226.         BNode successor = getSuccessor(node);  
      227.         if(node == root) {  
      228.             successor.leftChild = root.leftChild;  
      229.             successor.rightChild = root.rightChild;  
      230.             successor.parent = null;  
      231.             root = successor;  
      232.         }  
      233.         else if(isLeftChild) {  
      234.             node.parent.leftChild = successor;  
      235.         }  
      236.         else {  
      237.             node.parent.rightChild = successor;  
      238.         }  
      239.         successor.leftChild = node.leftChild;//connect successor to node's left child  
      240.         return true;  
      241.     }  
      242.       
      243.     //獲得要?jiǎng)h除節(jié)點(diǎn)的后繼節(jié)點(diǎn)（中序遍歷的下一個(gè)節(jié)點(diǎn)）  
      244.     public BNode getSuccessor(BNode delNode) {  
      245.         BNode successor = delNode;  
      246.         BNode current = delNode.rightChild;  
      247.         while(current != null) {  
      248.             successor = current;  
      249.             current = current.leftChild;  
      250.         }  
      251.         if(successor != delNode.rightChild) {  
      252.             successor.parent.leftChild = successor.rightChild;  
      253.             if(successor.rightChild != null) {        
      254.                 successor.rightChild.parent = successor.parent;//刪除后續(xù)節(jié)點(diǎn)在原來(lái)的位置  
      255.             }  
      256.             successor.rightChild = delNode.rightChild;//將后續(xù)節(jié)點(diǎn)放到正確位置，與右邊連上  
      257.         }  
      258.         return successor;  
      259.     }  
      260. }  
      261.   
      262. class BNode {  
      263.     public int key;  
      264.     public double data;  
      265.     public BNode parent;  
      266.     public BNode leftChild;  
      267.     public BNode rightChild;  
      268.       
      269.     public void displayNode() {  
      270.         System.out.println("{" + key + ":" + data + "}");  
      271.     }  
      272. }  
      


      
                                          		
                                
      
                                  
                        
      
                    
      



                
      
                
      
                    
                    
                        
      
                            
                                
        
                                    		
                        
        
                            
                
        
                
        
                
                
                
        
                
        


                

                
        本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
        
                
                

                
        
                    轉(zhuǎn)藏
                    
                    
                    
                    
                    
                    
                        分享
                        
                        
                    
                    獻(xiàn)花（0）
                            
                
        
                
                
                
        
                    
        
                        
                        
                    
        
                
        

            
        

            
        

            
        
                
                
                
        
                
        
                    
        
                        
        0條評(píng)論
        
                        
                        
                        
        
                            
                            
        
                                發(fā)表
                            
        
                        
        
                        
                    
        
                    
                    
        請(qǐng)遵守用戶 評(píng)論公約
        
                    
                    
          
                    
        
                    
        
                    
        
                    
                
        
               
                
        
                    
        
                        類似文章
                        更多