首页 文章

二进制搜索树的最大深度

提问于
浏览 次
0

我想找到二进制搜索树的最大深度 . 我找到了一个代码 .

int maxDepth(struct node* node) { 
  if (node==NULL) { 
    return(0); 
  } 
  else { 
    // compute the depth of each subtree 
    int lDepth = maxDepth(node->left); 
    int rDepth = maxDepth(node->right);
    // use the larger one 
    if (lDepth > rDepth) return(lDepth+1); 
    else return(rDepth+1); 
  } 
}

我想知道node-> left怎么会返回1？

这是默认的吗？代码很简单，但我不知道答案即将来临，有人可以解释一下吗？

c++ algorithm data-structures binary-search-tree

2 回答

  • 2

    鉴于这棵树：

    [一个]

    / \

    [B] [C]

    将使用NULL为[B]调用maxDepth，对于具有NULL的[C]，将返回零，因此递归调用最终返回0 1 .

    如果在[C]下有一个节点[D]，那么对[D] maxDepth的调用将返回NULL而D将返回0 1，那么递归将继续按比例放大，[C]将接收0 1并且将为1，返回maxDepth为2，它大于保持[B]的分支的深度，该分支是1，因此从完全递归返回maxDepth为2 .

    回复于
  • 1

    当 node 指向一个叶子时，它的 node->left 和 node->right 都是 NULL . 所以 maxDepth() 都返回 0 . 所以这个叶子的当前递归只返回深度 0 + 1 = 1.

    你可以证明它的正确性 .

    Initialization

    当节点为 NULL 时，它返回 0 . 确实，空树的深度为 0 . 当节点为leaf时，它返回 1 . 刚刚解释过 .

    Maintenance

    如果存在节点（不是 NULL ）并且我们知道其子节点的深度，则此节点的深度将为 max(depth of left, depth of right) + 1 . 这就是回归 .

    Termination

    它将终止，因为当它到达叶子时，递归将停止变深并返回 . 当整个递归完成时， maxDepth(root) 返回 root 的深度 .

    回复于

相关问题