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

打開APP
userphoto
未登錄

開通VIP，暢享免費(fèi)電子書等14項(xiàng)超值服

開通VIP

首頁(yè)

好書

留言交流

下載APP

聯(lián)系客服
【數(shù)據(jù)結(jié)構(gòu)與算法04】二叉樹

       在有序數(shù)組中，可以快速找到特定的值，但是想在有序數(shù)組中插入一個(gè)新的數(shù)據(jù)項(xiàng)，就必須首先找出新數(shù)據(jù)項(xiàng)插入的位置，然后將比新數(shù)據(jù)項(xiàng)大的數(shù)據(jù)項(xiàng)向后移動(dòng)一位，來給新的數(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è)過程很慢。

        樹這種數(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è)過程要求改變父節(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？

   

        因此需要考慮另一種方法，尋找它的中序后繼來代替該節(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字段來標(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)連起來即可，要考慮特殊情況就是刪除根節(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)在原來的位置  
  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. }  


本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊舉報(bào)。
打開APP，閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
數(shù)據(jù)結(jié)構(gòu)與算法：15 樹
打破常規(guī)，Linux內(nèi)核新的數(shù)據(jù)結(jié)構(gòu)上場(chǎng)maple tree
常見數(shù)據(jù)結(jié)構(gòu)與算法整理總結(jié)（上）
Leetcode算法「114. 二叉樹展開為鏈表」
[樹]基于二叉樹的中序遍歷非遞歸算法
二叉樹操作算法實(shí)例
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長(zhǎng)圖 關(guān)注 下載文章
綁定賬號(hào)成功
后續(xù)可登錄賬號(hào)暢享VIP特權(quán)！
如果VIP功能使用有故障，
可點(diǎn)擊這里聯(lián)系客服！

聯(lián)系客服