小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

平衡二叉樹算法詳解

 豆芽愛尚閱 2015-03-18


轉(zhuǎn)自：http://www.cnblogs.com/fornever/archive/2011/11/15/2249492.html

寫的有點兒俗，理論性不是很強，不過還算通俗易懂?？傊?，謝謝上位大俠的解釋~~~

平衡二叉樹定義(AVL)：它或者是一顆空樹，或者具有每以下性質(zhì)的二叉樹：它的左子樹和右子樹的深度之差的絕對值不超過1，且它的左子樹和右子樹都是一顆平衡二叉樹。

平衡因子(bf)：結(jié)點的左子樹的深度減去右子樹的深度，那么顯然-1<=bf<=1;

很顯然，平衡二叉樹是在二叉排序樹(BST)上引入的，就是為了解決二叉排序樹的不平衡性導(dǎo)致時間復(fù)雜度大大下降，那么AVL就保持住了(BST)的最好時間復(fù)雜度O(logn)，所以每次的插入和刪除都要確保二叉樹的平衡，那么怎么保持平衡呢？

我努力看了看數(shù)據(jù)結(jié)構(gòu)上的講解，但是看的只暈+_+！我對他的講解很無語，他所謂的“旋轉(zhuǎn)”操作講的不明不白，看的我氣的蛋疼！你說你旋轉(zhuǎn)，你得說清是如何旋轉(zhuǎn)？以那個結(jié)點為中心，那些或者說那個結(jié)點轉(zhuǎn)了，那些結(jié)點不動。你就在哪里旋轉(zhuǎn)來旋轉(zhuǎn)去的，誰知道你是咋轉(zhuǎn)的，你在哪慢慢轉(zhuǎn)吧！哥轉(zhuǎn)不過你，另找高明！于是在網(wǎng)上找啊找，只為想搞明白是到底怎么轉(zhuǎn)的！點擊打開鏈接讓我對“旋轉(zhuǎn)”有所領(lǐng)悟，表示感謝！

 

插入時：

那究竟是如何“轉(zhuǎn)”的呢？

 

首先必須明白一個核心操作，不讓它叫“旋轉(zhuǎn)”！而叫——>“兩個結(jié)點的變換”

如圖：

就拿第一個來說->點100和101的變換：

點101占據(jù)點100的位置，點100換到了101的對面的位置，其他點的相對位置不變。

我們可以更直觀的理解為：把101結(jié)點“上提”一下！

分析：101>100，所以100可以作為101的左孩子；

也就是在二叉排序樹中，兩個結(jié)點這樣的變換操作是可行的，是符合二叉排序樹的性質(zhì)。

不僅這個簡單的圖，任何復(fù)雜的二叉排序樹都可以，你可以試試，也許你會說如果點101左邊有孩子怎么辦？別著急~，當然有辦法！

 

下邊正式說這個圖的四種不平衡情況（插入時）及操作：

首先還需要明白一個概念->最小不平衡子樹的根結(jié)點：也就是當你進行插入操作時，找到該需要插入結(jié)點的位置并插入后，從該結(jié)點起向上尋找（回溯），第一個不平衡的結(jié)點即平衡因子bf變?yōu)?2或2。

為什么要引入這個最小不平衡根結(jié)點的概念，因為在插入時，對該子樹進行保持平衡操作后，其它的結(jié)點的平衡因子不會變，也就是整棵樹又恢復(fù)平衡了。為什么呢？

你想想不平衡點的bf一定是-2或2吧，經(jīng)過平衡操作后，他會把一邊子樹的一個結(jié)點分給另一邊的子樹，也就是一邊的深度分給另一邊，這樣就平衡了！

比如，插入前：左邊是深度1，右邊深度是0；插入后左邊深度是2，右邊深度是0，經(jīng)過平衡后左邊深度是1，右邊深度是1；

那么你說插入前和插入后該根結(jié)點所領(lǐng)導(dǎo)的子樹的深度變沒？？仍是1，顯然沒變！那么就仍保持了這棵樹的平衡了！

 

下面即四種情況分別為：左左、右右、左右、右左，每種情況又有兩個圖：①、②，①是該情況的最簡單的圖形，②是該情況的一般的圖形；

設(shè)x為最小不平衡子樹的根結(jié)點，y為剛插入的點

 

左左：

即在x的左孩子a的左孩子c上插入一個結(jié)點y（該結(jié)點也可以是c,如圖①），即y可以是c，也可以是c的左孩子（如圖②），也可以是c的右孩子（不在畫出）

                                  

圖①就不用說了，結(jié)點x和結(jié)點a變換，則樹平衡了；那么圖②就是樹中的一般情況了a結(jié)點有右孩子d，那要進行x和a變換，那么a的右孩子放哪??？

很簡單，如圖放在x的左孩子上；分析：x>d,d>a,所以d可作為x的左孩子，且可作為a的右孩子中的孩子。下邊這樣的類似情況不再一一分析，自己分析分析~

實現(xiàn)：找到根結(jié)點x，與它的左孩子a進行交換即可使二叉樹樹再次平衡；

 

 

右右：

即在x的右孩子a的右孩子c上插入一個結(jié)點y（該結(jié)點也可以是c,如圖①），即y可以是c，也可以是c的右孩子（如圖②），也可以是c的左孩子（不在畫出）

實現(xiàn)：找到根結(jié)點x，與它的右孩子a進行交換即可使二叉樹樹再次平衡；

 

 

左右：

即在x的左孩子a的右孩子c上插入一個結(jié)點y（該結(jié)點也可以是c,如圖①），即y可以是c，也可以是c的右孩子（如圖②），也可以是c的左孩子（不在畫出）

 

 

這個左右和下邊的右左，稍微復(fù)雜了點，需要進行兩次交換，才能達到平衡，注意這時y是c的右孩子，最終y作為x的左孩子；若y是c的左孩子，最終y作為a

的右孩子，畫圖分析一下~~下邊類似，不再敖述。

 

實現(xiàn)：找到根結(jié)點x，讓x的左孩子a與x的左孩子a的右孩子c進行交換，然后再讓x與x此時的左孩子c進行交換，最終達到平衡；

 

右左：

即在x的右孩子a的左孩子c上插入一個結(jié)點y（該結(jié)點也可以是c,如圖①），即y可以是c，也可以是c的右孩子（如圖②），也可以是c的左孩子（不在畫出）

 

實現(xiàn)：找到根結(jié)點x，讓x的右孩子a與x的右孩子a的左孩子c進行交換，然后再讓x與x此時的右孩子c進行交換，最終達到平衡；

 

上邊的四種情況包含了所有插入時導(dǎo)致不平衡的情況，上面給出的僅僅是一棵大樹中的最小不平衡子樹，一定要想清楚，別迷了！

另外一定要注意這個交換操作，比如a與b交換（a在上，b在下），b一定要占據(jù)a的位置！什么意思？就是b要放在（覆蓋）儲存a的那塊內(nèi)存上，

再通俗點說，若a是x的左孩子，則交換后b要做x的左孩子；這就是所謂的b占據(jù)a的位置！

 

那么如何找到最小不平衡子樹的根結(jié)點x，并判斷出它是屬于那種情況的？

 

插入一個結(jié)點時，我們首先找到需要插入的位置，并插入；數(shù)據(jù)結(jié)構(gòu)上用的是遞歸，不要說遞歸太浪費時空，你想想一個含2^31個結(jié)點的平衡二叉樹的深度大約是31吧，它遞歸再多也不就是31層！而且遞歸代碼短小、精悍、富含藝術(shù)之美！所以我認為對于這個平衡二叉樹，用遞歸很合適！

顯然插入之后就要檢查是否出現(xiàn)不平衡的結(jié)點，那么如何檢查？

我們知道，你插入的時候用的是遞歸，一條線找到要插的位置，并插入；那么誰的平衡因子的有可能變呢？

不難想象，只有該條線上的結(jié)點的平衡因子有可能改變！那么我們在回溯的時候不就可以找到第一個不平衡的子樹的結(jié)點？！

可是我們?nèi)绾闻袛嘣摻Y(jié)點的平衡因子是否應(yīng)該改變，顯然要看它被插入結(jié)點的一邊的深度是否增加；

如何看它被插入結(jié)點的一邊的深度是否增加？

如上圖，如何看x的右孩子a（即被插入結(jié)點的一邊）的深度增加？我們知道在a的右孩子上插入了結(jié)點y那么a的bf是一定要減1

那么x結(jié)點的bf？可根據(jù)a的bf決定是否改變！

若a:bf=-1或1，那么a之前一定為0，表示a的深度增加了，那么x的bf可根據(jù)a是x哪一邊的孩子決定+1或-1；

若a:bf=0，那么a之前一定為-1或1，表示a的深度沒增加，那么不僅x的bf就不用變，該條線上的所有結(jié)點的bf都不用變，直接返回即可；

 

當然了，那么找到最小不平衡子樹的根結(jié)點x了，如何判斷它屬于哪種不平衡呢？

①根據(jù)上邊的幾種情況，我們需要知道兩個方向，在回溯時可以記錄一下該結(jié)點到下一個結(jié)點的方向0：左、1：右為第二個方向，傳遞給上一層中，那么上層中的方向就是一個方向，有了這兩個方向就能確定是哪種不平衡了。

還就上邊的圖說吧~可以定義一個全局變量secdirection（第二個方向），也可在遞歸中定義一個局部變量，返回給上一層。在回溯到a中時，secdirection=1，到x的時候

x->a的方向也為1，定義firdirection=1；而這時x:bf=-2；那么就找到了最小不平衡子樹的根結(jié)點x，又知道了兩個方向，那么進行相應(yīng)的平衡操作不就行了。

②其實我代碼中的就是按照①寫的，可是剛又想了，其實不用用個變量記錄第二個方向，可以根據(jù)a的bf確定它的第二個方向，a:bf=-1說明右孩子的深度增加，y加到右孩子上；

a:bf=1;說明左孩子的深度增加，y加到左孩子上；

 

好了，找到了最小不平衡子樹的根結(jié)點x了，也知道了那種不平衡，調(diào)用keepbalance(...)就使樹平衡了，可是某些結(jié)點的平衡因子在變換是變了~~咋辦？

我就是一種一種情況推出來的，不知道別人怎么變的，每一種情況都有固定的幾個點變了，變成了一個固定的值！誰有更好的辦法，請多多指教！

 

下邊一一列出（插入操作中）變換后bf改變的結(jié)點及值：

左左：前a->bf=1 后 x->bf=0,a->bf=0；右右：前a->bf=-1 后x->bf=0,a->bf=0；顯然左左與右右的x與a變換后的bf都為0；

左右、右左中結(jié)點bf的改變要根據(jù)之前c的bf！

左右：若c->bf=1,則x->bf=-1,a->bf=0,c->bf=0；若c->bf=-1,則x->bf=0,a->bf=1,c->bf=0；若c->bf=0,則x->bf=0,a->bf=0,c->bf=0；

右左：若c->bf=1,則x->bf=0,a->bf=-1,c->bf=0；若c->bf=-1,則x->bf=1,a->bf=0,c->bf=0；若c->bf=0,則x->bf=0,a->bf=0,c->bf=0；

可以發(fā)現(xiàn)，當左右、右左的c->bf相同時x與a的bf剛好取相反的值。

 

好了，到現(xiàn)在插入一個結(jié)點的二叉樹終于平衡了，相應(yīng)的平衡因子也修改了！插入算是完成了??！

 

刪除時：

刪除類似插入的操作，蛋又不同，刪除會有一些特殊情況需要特殊處理，當然核心操作“保持平衡”是不變的！

 

刪除時少一個結(jié)點，也就是該結(jié)點所在的子樹深度可能會減小，而插入時多一個結(jié)點，該結(jié)點所在的子樹深度可能會增加，

所以遞歸刪除一個結(jié)點時，回溯時找到最小不平衡子樹的根結(jié)點時，要向相反的方向去找屬于哪種情況；

如圖：

y為要刪除的結(jié)點；

圖①：y結(jié)點刪除后，回溯到x結(jié)點x:bf=-1變?yōu)閤:bf=-2；則需從相反方向即從x的右孩子的方向向下檢查屬于哪種情況，顯然第一個方向為1：右；

第二個方向看a:bf的值——若為1時，那就相當于插入時‘右左’的情況；若為-1時，那就相當于插入時‘左左’的情況；可現(xiàn)在a:bf既不是1也不是-1

而是0，這就是刪除的特殊情況了！我們不妨試試對他進行類似于插入時的‘右右’操作，看怎么樣~    如上圖，經(jīng)過變換后該子樹平衡了！但是因子的

修改就跟插入時的‘右右’不一樣了！此時變?yōu)椋簒:bf=-1,a:bf=1；所以我們不妨就把a:bf=0也歸納為刪除的‘右右’或‘左左’（如圖②，不再敖述）操作；

那么刪除時因子的改變需在插入時因子的改變中添加上：

左左：前a:bf=0 后x:bf=1,a:bf=-1； 右右：前a:bf=0 后x:bf=-1,a:bf=1；其他不變！

 

插入時結(jié)束結(jié)點平衡因子的修改，直接返回（也就是該樹已經(jīng)平衡了）：

回溯時發(fā)現(xiàn)兒子結(jié)點的平衡因子為0（當發(fā)現(xiàn)不平衡結(jié)點，并進行平衡操作后，平衡后根結(jié)點的bf一定為0，也結(jié)束了）

但是刪除時結(jié)束結(jié)點平衡因子的修改，直接返回，就與插入時不一樣了：回溯時發(fā)現(xiàn)兒子結(jié)點的平衡因子為-1或1！

再刪除操作中，平衡一個子樹后，該子樹的深度不一定不變，而只有上邊那種特殊情況該子樹的深度不變，其他都會變！

可以想象，其實是很簡單的道理：除了特殊情況其他都與插入的情況一模一樣，說白了就是把深度大的子樹（根結(jié)點的其中一個）向深度小子樹貢獻一個深度，

那么這樣一來，該子樹（對于根結(jié)點所領(lǐng)導(dǎo)的樹）的深度是不是比原來的小1了？！所以要繼續(xù)向上一個一個進行檢索，直到根結(jié)點為止！

 

好了，到這里刪除也算是說完了，可以貼代碼了吧~

 

平衡二叉樹的C實現(xiàn)：

  1. View Code   
  2.  #include <stdio.h>  
  3.  #include <stdlib.h>  
  4.  #include <string.h>  
  5.    
  6.  typedef int Elemtype;  
  7.    
  8.  typedef struct Balanced_Binary_Tree  
  9.  {  
  10.      Elemtype e;  
  11.      int bf;  
  12.      struct Balanced_Binary_Tree *child[2];  
  13.  }*AVL;  
  14.    
  15.  ///------------簡單的位操作-------------------  
  16.  void setbit(char *i,char val,char pos)  
  17.  {  
  18.      if(pos==1)  
  19.          (*i)=(*i)|1;  
  20.      else  
  21.      {  
  22.          if(val==1)    (*i)=(*i)|2;  
  23.          else    (*i)=(*i)&1;  
  24.      }  
  25.  }  
  26.  char getbit(char i,char pos)  
  27.  {  
  28.      ///調(diào)試時，發(fā)現(xiàn)這里能返回2///  
  29.  //    return (i&pos); 出錯的地方  
  30.      return (i&pos)&&1;  
  31.      /////////////////////////////  
  32.  }  
  33.  ///--------------------------------------------  
  34.    
  35.  ///-----------生成一個結(jié)點---------------------  
  36.  AVL createnode(Elemtype e)  
  37.  {  
  38.      AVL node=NULL;  
  39.    
  40.      node=(AVL)malloc(sizeof(struct Balanced_Binary_Tree));  
  41.      node->e=e;    node->bf=0;  
  42.      node->child[0]=node->child[1]=NULL;  
  43.        
  44.      return node;  
  45.  }  
  46.  ///---------------------------------------------  
  47.    
  48.  ///★★★★★★★★AVL的核心操作★★★★★★★★★★★★  
  49.  ///★★★★★★★★★保持平衡★★★★★★★★★★★★★★  
  50.    
  51.  //改變因子函數(shù)  
  52.  void setfactor(AVL f,int button)  
  53.  {  
  54.      char fir=button/10,sec=button%10;  
  55.      AVL s=f->child[fir],ss=s->child[sec];  
  56.      char choice=ss->bf;  
  57.      int a=1,b=0;  
  58.    
  59.      //////////調(diào)試時發(fā)現(xiàn)，刪除時的特殊情況/////////////  
  60.  /////插入時，不會有這種情況，若button=0,則s->bf=1//  
  61.  /////若button=11，則s->bf=-1；然而刪除時，卻會出現(xiàn)/  
  62.  /////button=0或者button=11時 s->bf=0!!!!!!!////////  
  63.  /////那么這種特殊情況，平衡后所得的因子就跟一般的//  
  64.  /////不一樣了!!!如下///////////////////////////////  
  65.      if(button==0 && s->bf==0)    f->bf=1,s->bf=-1;  
  66.      else if(button==11 && s->bf==0)    f->bf=-1,s->bf=1;  
  67.      ///////////////////////////////////////////////////  
  68.      else if(button==0 || button==11)  
  69.      {  
  70.          f->bf=0;  
  71.          s->bf=0;  
  72.      }  
  73.      else  
  74.      {  
  75.          /////寫博客時，發(fā)現(xiàn)這里有問題///////////////////  
  76.      //    if(button==1)    choice=-choice;  
  77.          /////但是為什么我測試的時候怎么都對?!///////////  
  78.  /////經(jīng)再次測試，上邊確實錯了!!!////////////////  
  79.  /////改為下邊應(yīng)該就對了吧///////////////////////  
  80.          if(button==1)    {a^=b,b^=a,a^=b;}  
  81.          ////////////////////////////////////////////////  
  82.    
  83.          if(choice==-1)    f->bf=a,s->bf=b;  
  84.          else if(choice==0)    f->bf=s->bf=0;  
  85.          else    f->bf=-b,s->bf=-a;  
  86.            
  87.          ss->bf=0;  
  88.      }  
  89.  }  
  90.  //兩節(jié)點變換函數(shù)  
  91.  void conversion(AVL *T,char direction)  
  92.  {  
  93.      AVL f=*T,s=f->child[direction];  
  94.    
  95.      f->child[direction]=s->child[!direction];  
  96.      s->child[!direction]=f;  
  97.      *T=s;  
  98.  }  
  99.  //保持平衡函數(shù)  
  100.  void keepbalance(AVL *T,char fir,char sec)  
  101.  {  
  102.      AVL *s=&((*T)->child[fir]);  
  103.      int button=fir*10+sec;  
  104.    
  105.      if(button==0 || button==11)  
  106.      {  
  107.          setfactor((*T),button);  
  108.          conversion(T,fir);  
  109.      }  
  110.      else  
  111.      {  
  112.          setfactor((*T),button);  
  113.          conversion(s,sec);  
  114.          conversion(T,fir);  
  115.      }  
  116.  }  
  117.  ///★★★★★★★★★★★★★★★★★★★★★★★★★★  
  118.    
  119.  ///------------插入時的選向操作-------------------  
  120.  void selectforInsert(AVL *T,char *info,int direction)  
  121.  {  
  122.      AVL cur=*T;  
  123.      char firdirection,secdirection;  
  124.    
  125.      if(direction==0)    (cur->bf)++;  
  126.      else    (cur->bf)--;  
  127.    
  128.      if(cur->bf==0)    setbit(info,1,1);  
  129.      else if(cur->bf==-1 || cur->bf==1)    setbit(info,direction,2);  
  130.      else  
  131.      {          
  132.          firdirection=direction;  
  133.          secdirection=getbit(*info,2);  
  134.          keepbalance(T,firdirection,secdirection);  
  135.          setbit(info,1,1);  
  136.      }  
  137.  }  
  138.  //----------------------------------------------  
  139.    
  140.  //*************插入操作************************//  
  141.  char InsertAVL(AVL *T,Elemtype e)  
  142.  {                                //可用于查詢  
  143.      char info;  
  144.        
  145.      if(!(*T))  
  146.      {  
  147.          (*T)=createnode(e);  
  148.          return 0;  
  149.      }  
  150.      else if((*T)->e==e)        return -1;  
  151.      else if((*T)->e>e)//左  
  152.      {  
  153.          info=InsertAVL(&((*T)->child[0]),e);  
  154.    
  155.          if(getbit(info,1))    return info;  
  156.            
  157.          selectforInsert(T,&info,0);  
  158.      }  
  159.      else              //右  
  160.      {  
  161.          info=InsertAVL(&((*T)->child[1]),e);  
  162.    
  163.          if(getbit(info,1))    return info;  
  164.    
  165.          selectforInsert(T,&info,1);  
  166.      }  
  167.      return info;  
  168.  }  
  169.  //*********************************************//  
  170.    
  171.  //-------------刪除時的選向操作--------------------  
  172.  void selectforDelete(AVL *T,char *info,char direction)  
  173.  {  
  174.      AVL cur=(*T);  
  175.      char firdirection,secdirection;  
  176.    
  177.      if(direction==0)    (cur->bf)--;  
  178.      else    (cur->bf)++;  
  179.        
  180.      if(cur->bf==0)    *info=0;  
  181.      else if(cur->bf==-1 || cur->bf==1)    *info=1;  
  182.      else  
  183.      {  
  184.          firdirection=!direction;  
  185.          ///調(diào)試時，發(fā)現(xiàn)這里少寫了一個等號////////////////////  
  186.  //        if(cur->child[firdirection]->bf=1)    secdirection=0;草，真帥氣!原來1==a這樣寫確實有必要!  
  187.          if(1==cur->child[firdirection]->bf)    secdirection=0;  
  188.          /////////////////////////////////////////////////////  
  189.          else    secdirection=1;  
  190.          keepbalance(T,firdirection,secdirection);  
  191.    
  192.          /////////////////////////////////////////////////////////////////////////////////////////  
  193.  ///調(diào)試時，發(fā)現(xiàn)經(jīng)過子樹平衡操作后，*info不一定都是0，就是那個特殊情況，在setfactor中/////  
  194.  ///的那種特殊情況時，這里*info應(yīng)改為1! 所以代碼改如下：//////////////////////////////////  
  195.  /////////////////////////////////////////////////////////////////////////////////////////  
  196.      //    *info=1; 寫代碼時：這跟插入可不一樣啊...該子樹平衡了，它父節(jié)點的因子比變!  
  197.  //    *info=0;//因此，這還沒完還要是0!! ............啊……這里不一定是0!   
  198.  ////還是那個特殊情況搞的鬼!//  
  199.          if(cur->bf==0)    *info=0;  
  200.          else    *info=1;  
  201.          /////////////////////////////////////////////////////////////////////////////////////////  
  202.      }  
  203.  }  
  204.  //------------------------------------------------  
  205.    
  206.  //-------------變向遞歸--輔助刪點-----------------  
  207.  char find(AVL *gogal,AVL *p)  
  208.  {  
  209.      char info;  
  210.      AVL tp=NULL;  
  211.        
  212.      if(NULL!=(*p)->child[0])  
  213.      {  
  214.          info=find(gogal,&((*p)->child[0]));  
  215.          if(info!=0)    return info;  
  216.          selectforDelete(p,&info,0);  
  217.      }  
  218.      else  
  219.      {  
  220.          (*gogal)->e=(*p)->e;  
  221.          tp=(*p)->child[1];  
  222.          free((*p));  
  223.          *p=tp;  
  224.          info=0;  
  225.      }  
  226.      return info;  
  227.  }  
  228.  //------------------------------------------------  
  229.    
  230.  //**************刪除操作*************************//  
  231.  char DeleteAVL(AVL *T,Elemtype e)  
  232.  {  
  233.      char info;  
  234.      AVL tp=NULL;  
  235.    
  236.      if(!(*T))    return -1;//原if(!T)    return -1;于2011年11月29日8:59:15修改  
  237.      else if((*T)->e==e)  
  238.      {  
  239.          if(NULL!=(*T)->child[1])  
  240.          {  
  241.              info=find(T,&((*T)->child[1]));  
  242.              if(info!=0)    return info;  
  243.              selectforDelete(T,&info,1);  
  244.          }  
  245.          else  
  246.          {  
  247.              //////////////調(diào)試時，發(fā)現(xiàn)這樣寫不對!!!///////////////////////////////////////  
  248.          //    (*T)=(p=(*T)->child[0])-(free((*T)),0);//Just save a variable! 這里出問題  
  249.  //    (*T)=p-(free((*T)),0); 可以  
  250.  //    (*T)=(p=((*T)->child[0]))+(free((*T)),0); 不可以  
  251.              tp=((*T)->child[0]);  
  252.              free((*T));  
  253.              *T=tp;  
  254.              //調(diào)試時，發(fā)現(xiàn)這里漏了給info賦值  
  255.              info=0;  
  256.              ///////////////////////////////////////////////////////////////////////////////  
  257.          }  
  258.      }  
  259.      else if((*T)->e>e)  
  260.      {  
  261.          info=DeleteAVL(&(*T)->child[0],e);  
  262.          if(info!=0)    return info;  
  263.          selectforDelete(T,&info,0);  
  264.      }  
  265.      else  
  266.      {  
  267.          info=DeleteAVL(&(*T)->child[1],e);  
  268.          if(info!=0)    return info;  
  269.          selectforDelete(T,&info,1);  
  270.      }  
  271.      return info;  
  272.  }  
  273.  //************************************************//  
  274.    
  275.    
  276.  //*****************JUST FOR TEST************************//  
  277.  #define MOVE(x)    (x=(x+1)%1000)  
  278.  AVL queue[1000];  
  279.    
  280.  void print(AVL p,int i)  
  281.  {  
  282.      int front,rear,temp,count;  
  283.    
  284.      front=rear=-1; count=temp=0;  
  285.      queue[MOVE(rear)]=p; count++;  
  286.        
  287.      printf("%d\n",i);  
  288.      while(front!=rear)  
  289.      {  
  290.          p=queue[MOVE(front)];    count--;  
  291.            
  292.            
  293.          if(p->child[0])    queue[MOVE(rear)]=p->child[0],temp++;  
  294.          if(p->child[1])    queue[MOVE(rear)]=p->child[1],temp++;  
  295.            
  296.          printf("%d->%d ",p->e,p->bf);  
  297.          if(count==0)  
  298.          {  
  299.              printf("\n");  
  300.              count=temp;  
  301.              temp=0;  
  302.          }      
  303.      }  
  304.      printf("\n");  
  305.  }  
  306.  //**************************************************//  
  307.    
  308.    
  309.  int main()  
  310.  {  
  311.      AVL T=NULL;  
  312.      int i,nodenum=0;  
  313.    
  314.      freopen("input.txt","w",stdout);  
  315.      nodenum=100;  
  316.      for(i=0;i<nodenum;i++)  
  317.      {  
  318.          InsertAVL(&T,i);  
  319.      }  
  320.        
  321.      print(T,-1);  
  322.    
  323.      for(i=0;i<nodenum-1;i++)  
  324.      {  
  325.          DeleteAVL(&T,i);  
  326.          print(T,i);  
  327.      }  
  328.        
  329.      return 0;  
  330.  }  



 

那個位操作函數(shù)，使程序好像很復(fù)雜似的，完全可以用一個外部結(jié)構(gòu)體替換！只是我不想用外部變量，盡量在函數(shù)內(nèi)完成吧

由于本人比較笨，寫了很長時間~~有什么不正確的，歡迎指正?。?！

這些圖費了很大功夫才弄好，本來在編輯框里畫的好好的，可是一發(fā)表，那些圖有些就亂了，剛開始我還試著一個一個對照著修改，看最終發(fā)現(xiàn)還是不行……最后忽然想到我怎么不在編輯框中截圖呢？最后在編輯框中一個一個截圖一個一個上傳，這樣效果好多了！費這么大功夫只為一點：讓讀者看著舒服，容易理解。

我還想說：開這個博客園以來，也沒多長時間，蛋把我氣的不淺！每次都是搞好程序，準備到這里寫博客時，就是打不開！氣死我了！卡死啦！有時候確實是我網(wǎng)速慢，但有時候網(wǎng)速好了也很難打開?。∧阏f你還是程序員的家園！看你卡的，我都無語了！網(wǎng)速稍微慢點就打不開，就這浪費了我很多時間！我對博客園很失望??！

朋友們，你們感覺呢？

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

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多