AVL樹的平衡因素

Question

我有一個AVL樹類，我想找到的每個節點的平衡因子（balance_factor: node->Left_child->height - node->right_Child->height）

這裏是我的代碼

int tree::findBalanceFactor(node p){ 

int a; 
if(p.lchild) p.lchild->balance_factor=findBalanceFactor(*p.lchild);  
if(p.rchild) p.rchild->balance_factor=findBalanceFactor(*p.rchild); 

if(p.rchild && p.lchild)   a=p.balance_factor = p.lchild->height - p.rchild->height ; 
if(p.rchild && !p.lchild)   a=p.balance_factor = 0 - p.rchild->height; 
if(!p.rchild && p.lchild)   a=p.balance_factor = p.lchild->height; 
if(!p.rchild && !p.lchild)  a=p.balance_factor = 0; 

cout << "md" << a << endl; 
return a; 

但在主要功能當我打印root->balance_factor它表明我總是編號爲零 balance_factor是一個公共變量，並在構造函數中，我將0賦值爲 我的代碼有什麼問題？

預先感謝您:)

Answer 1

我猜測爲什麼根節點的balance_factor始終爲0，因爲在tree::findBalanceFactor方法，這些兩行代碼的原因：

if(p.lchild) p.lchild->balance_factor=findBalanceFactor(*p.lchild);  
if(p.rchild) p.rchild->balance_factor=findBalanceFactor(*p.rchild); 

我假設node結構/類看起來是這樣的：

struct node { 
    struct node *lchild; 
    struct node *rchild; 
    int balance_factor; 
    int height; 
}; 

在會發生什麼10和findBalanceFactor(*p.rchild)是，我們傳遞新副本的p.lchild和p.rchild成findBalanceFactor（從指針引用看到的），並且因此不被更新的原始p.lchild和p.rchild的balance_factor屬性。

該解決方案將是修改tree::findBalanceFactor方法採取指針到節點，像這樣（我已經採取自由美化一點的代碼）：

int tree::findBalanceFactor(node *p) { 
    int a; 
    if (p->lchild) { 
     findBalanceFactor(p->lchild); 
    } 
    if (p->rchild) { 
     findBalanceFactor(p->rchild); 
    } 

    if (p->rchild && p->lchild) { 
     a = p->balance_factor = p->lchild->height - p->rchild->height; 
    } else if (p->rchild && !p->lchild) { 
     a = p->balance_factor = 0 - p->rchild->height; 
    } else if (!p->rchild && p->lchild) { 
     a = p->balance_factor = p->lchild->height; 
    } else { 
     // this is the case for !p->rchild && !p->lchild 
     a = p->balance_factor = 0; 
    } 

    cout << "md" << a << endl; 
    return a; 
} 

對於p->lchild和p->rchild ，因爲node中的balance_factor已經設置在很長的if聲明的4種可能情況中的一種中，所以我們不需要再設置其balance_factor。

Answer 2

有一個多簡單的方式做到這一點不是測試lchild和rchild的每一個排列：

int tree::findBalanceFactor(node &n) { 
    int lheight = 0; 
    int rheight = 0; 

    if (n.lchild) { 
     findBalanceFactor(*n.lchild); 
     lheight = n.lchild->height; 
    } 
    if (n.rchild) { 
     findBalanceFactor(*n.rchild); 
     rheight = n.rchild->height; 
    } 
    n.balance_factor = lheight - rheight; 
    std::cout << "md " << n.balance_factor << std::endl; 
    return n.balance_factor; 
}