函數來平衡搜索樹

所以我需要一些幫助，因爲我正在從一個文件中讀取並插入到一個列表和一棵樹中進行搜索，這個函數並沒有保存所有的節點，它丟失了信息運行。函數來平衡搜索樹

fe=left child 
fd=right child

NodeCount回報多少節點都是在樹和旋轉功能正常

TREE *rotate left(TREE *A) //right just replace fe for fd: 
{ 
    ARVORE *aux; 
    aux=A->fd; 
    A->fd=aux->fe; 
    aux->fe=A; 
    return A; 
}

如果樹是平衡的，否則爲0

TREE *balances (TREE *A) 
{ 
     TREE *aux = A; 
     if(aux == NULL) 
     return A; 

     while(!balance(aux)) 
     { 
      if((NodeCount(aux->fe) - NodeCount(aux->fd)) > 1) 
       aux=rotateright(aux); 
      if((NodeCount(aux->fd) - NodeCount(aux->fe)) > 1) 
       aux=rotateleft(aux); 
      return aux; 
     } 
     return A; 
} 


    output : 
    before balances :0 
    [email protected] 
    [email protected] 
    [email protected] 
    [email protected] 
    [email protected] 
    [email protected] lost 
    [email protected] lost 
    [email protected] lost 
    [email protected] lost 
    After Balances 
    [email protected] 
    [email protected] 
    [email protected] 
    [email protected] 
    [email protected] 
    Equi:1

來源

2015-12-21 euphz2011

「這個功能是不是保存所有的節點」。你指的是哪個功能？請提供[最小完整和可驗證示例]（http://stackoverflow.com/help/mcve），其中包括測試輸入，預期行爲和實際行爲。 – kaylum

餘額功能，功能不會返回樹的正確的根 – euphz2011

我正在閱讀約1000個電子郵件從一個文件，並在樹中只有一些，但電子郵件都讀了，我知道，因爲我是將它們插入鏈表並且它們在列表中@kaylum – euphz2011

平衡函數返回的1個工作

你的問題是合乎邏輯的。你的if語句在邏輯上不相互連接，條件重疊。結果aux被第二個if的所有語句覆蓋，然後如此返回。

例：第一aux = [email protected];然後aux = [email protected];和[email protected]被返回。

如果仔細觀察，會發現缺少的東西，恰恰是正確的部分子樹（所有元素都大於根）。因爲它看起來是一個inorder遍歷，因此根必須是[email protected]。從這裏你可以很容易地看到它。

最快的解決辦法是把一個return aux;在每個if語句正文：

while(!balance(aux)) { 
     if ((NodeCount(aux->fe) - NodeCount(aux->fd)) > 1) { 
      aux=rotateright(aux); 
      return aux; 
     } 
     if ((NodeCount(aux->fd) - NodeCount(aux->fe)) > 1) { 
      aux=rotateleft(aux); 
      return aux; 
     } 
}

來源

2015-12-21 18:19:59 user8

@ euphz2011歡迎來到SO！由於你（相對）新，你可能想檢查這[鏈接]（http://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work/5235#5235） – user8

函數來平衡搜索樹

回答

相關問題