c++ - 检查BST中每个节点的平衡因子并将其存储在节点中

Question

我正在尝试编写此函数，将每个节点的余额存储在 BST 中并将其存储在节点内。在我的 BST 中，我添加了变量 bal 来存储它。

在递归方面我仍然是一个初学者，所以请原谅任何错误我只需要帮助看看我的逻辑是否正确或者是否有更好的方法! 这是我的功能:

 void calculateBalanceValue(BinaryNode *& t)
        {
            if (t==nullptr) return;

            int left = height(t->left);
            int right = height(t->right);
            t->bal=abs(left -right);
            calculateBalanceValue(t->right);
            calculateBalanceValue(t->left);

        }

Answer 1

这个逻辑在我看来是合理的，但在我看来，将其速度提高大约两倍是相当微不足道的。

现在，您遍历每个子树一次以计算其高度，然后再次遍历 at 以计算其平衡度。

因为无论如何它都需要遍历子树来完成它的工作，所以我会让 calculateBalance 返回树的高度。这样一来，通过一次遍历计算平衡和高度就变得相当简单了。

因为我们不想修改传递给这个函数的指针，所以我只是按值传递指针。

int calculateBalanceValue(BinaryNode *t)
    {
        if (t==nullptr) 
            return 0;

        int left = calculateBalance(t->left);
        int right = calculateBalance(t->right);
        t->bal=abs(left -right);
        return 1 + std::max(left, right);
    }

顺便说一句，如果您想对工作代码进行评论，您可能需要查看 Stack Exchange 的 Code Review专门用于此目的的网站。