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是一个公共变量，在构造函数中，我为此分配了零我的代码有什么问题？！

预先感谢您：）

Answer 1

与测试lchild和rchild的每个排列相比，有一种much更为简单的方法来进行此操作：

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;
}

由于这似乎已经以全代码的形式结束，因此，我将在how上添加简短说明，以使原始代码获得此答案。

在一个级别上，很容易观察到原始的四个分支中的每个分支都具有相同的形式(left - right)，但是只要left=0为空，就使用lchild，而当right=0为空时就使用rchild。

更广泛地说，寻找这种模式（即每个分支具有基本相同的表达式）非常有用。写出真值表或以其他方式在纸上划分状态空间，可以帮助在更复杂的代码中阐明这些模式。

您应该始终旨在了解一般情况是什么-是因为您首先实施了该一般情况，还是因为您能够从几个特定情况中将其排除在外。无论如何，实现一般情况通常足够好，并且是最容易理解的逻辑版本。

如果一般情况由于某种原因不够好，那么易于理解就意味着它仍然是一个很好的注释，因为它为您实际实现的特殊情况提供了比较点。

Answer 2

我猜测由于balance_factor方法中的这两行代码，根节点的tree::findBalanceFactor始终为0的原因：

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;
};

findBalanceFactor( *p.lchild )和findBalanceFactor( *p.rchild )中发生的事情是，我们将p.lchild和p.rchild的新副本传递到findBalanceFactor中（从指针取消引用中看到），因此balance_factor原始p.lchild和p.rchild的]属性未更新。

解决方案将是修改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，我们无需再次设置它们的balance_factor，因为在很长的balance_factor的4种可能情况之一中已经设置了每个node的if ]语句。