使用递归的二叉树平衡检查？

Question

你们好，伙计们，我正在试图理解我如何看到二叉树是否平衡。我试图打印出cout语句，以便进一步理解它，但运气不好。

算法的想法是，如果它返回-1，它就不平衡，如果它返回其他任何东西，它是平衡的。

然而，我并没有真正理解这个算法是如何工作的。但是我想知道的一些事情是；

int checkBalance(node *root)
{
if (root == NULL) return 0;

int left = checkBalance(root->left);
int right = checkBalance(root->right);
 //cout << "Root: " << root->key << " Left: " << left << ", Right: " << right << endl;

if (left == -1 || right == -1) return -1;
if (abs(left-right) > 1) return -1;

if (left > right) return left+1;
return right+1;
}

我的困惑点在于以下代码行：

• 如果 （根 == 空） 返回 0;
  • 当它返回 0 时会发生什么，何时达到 0？它只是为了防止递归继续转到未知的内存地址，还是返回数字0有任何意义？

  如果（左

  • 左边怎么比右边大？当我查看它时，它总是返回right 1，因为没有任何东西会“left”递增，因为条件从不为真

  int 左 = 检查平衡（根-

  • 用这种方式声明int是什么意思？这是向左的东西吗

  感谢您抽出时间阅读，我已经尝试自己研究这个问题，但是我很难理解这段代码是如何工作的。

  完整代码:html" target="_blank">http://pastebin.com/raw/VaiUNVdJ(案例6检查，案例1添加节点)

Answer 1

这是基本的BBT检查。它检查子树是否平衡。如果不是，则返回-1；如果是，它返回深度。

在伪代码中：

< li >如果给定的子树为空，则返回0(深度) < li >在左右子树上循环(检查平衡和深度) < li >如果任一子树不平衡，则返回-1 < li >比较左侧

要解决您的具体问题：

1. 此算法返回树深度（如果不平衡，则返回-1）。空树的深度为0。
2. 只要左树比右树深，左树就比右树大。你看到这个还有问题吗
3. 这就是如何声明和初始化变量。它与left=0中的语法相同，只是赋值的RHS是一个表达式

这足以让你摆脱困境了吗？

让我们采用您给出的节点值，使用根部为 49、子级为 48 和 51 的树结构，中缀表示法可能如下所示：

(48, 49, (50, 51, 52))

以更严格的形式，

49->left  = 48
49->right = 51
51->left  = 50
51->right = 52
There are no other children

在开始时根 = 节点 49，我们得到

int left = checkBalance(root->left);    // returns depth of 1
int right = checkBalance(root->right);  // returns depth of 2

现在，向左