二叉搜索树中的高度函数

Question

以下是我用于在 BST 中查找高度的代码。虽然它工作得很好，但我通过反复试验编写了这段代码。任何人都可以逐步解释它是如何工作的吗？非常感谢代码的枯燥运行示例。

int Tree::height(tree * Height)
{
    if(Height->left==NULL && Height->right==NULL)
    {
        return 0;
    }
    else
    {
        l=height(Height->left);
        r=height(Height->right);

        if (l>r)
        {
            l=l+1;
            return l;
        }
        else
        {
            r=r+1;
            return r;
        }
    }
}

Answer 1

我建议您将参数名称更改为 "node"，根据其含义并使用小写字母。

然后，此代码会立即检查根是否有子节点，如果没有，则 returns 0.

然后递归地从左到右访问树的所有节点，这是正确的。当它到达叶子时，返回的值对于 l 和 r 都是 0，因此 r 值递增，然后继续执行。当递归结束时，树的左右高度都减去 1（之前叶子计数为 0），所以加 1 就得到了整个高度。

注意这个方法returns树的高度但是你不知道哪个叶子是最深的，因为当l和r都返回0时你总是递增r。

Answer 2

您的 getHeight() 函数是此函数的变体

 int getHeight(tree *p)
{
   if (!p)
       return 0;

   int left = getHeight(p->left);
   int right = getHeight(p->right); 
   return max(left, right) +1;
}

最需要注意的是它使用递归意味着函数调用自身（getHeight()在getHeight()本身内部被调用）在您的代码中 getHeight() 被命名为 height()

树的高度相当于递归的深度

函数 getHeight() 被递归调用的次数与二叉搜索树的最低层数一样多 reached.The 递归深度是getHeight() 被递归调用。每次调用 getHeight() either 都会将计数器加一，所以最后计数器的值就是二叉搜索树的高度 or 在 BST 的最低级别 'level jumps' 的数量由 max(left, right) +1; 决定。这是 getHeight() 确定二叉搜索树高度的过程。

请参阅有关递归的维基百科文章 https://en.wikipedia.org/wiki/Recursion_(computer_science)

当指针引用结构的成员时使用箭头运算符 -> （在这种情况下结构 'p' 是树或其当前分支点 'left' 和 'right' 是去分支）

理解的关键点是递归是如何工作的。在物理学和数学中，递归类似于 self-mapping 或 self-reference

在函数式编程/Lambda 演算 (https://en.wikipedia.org/wiki/Functional_programming) 中，递归是唯一使用的编程技术。它是命令式编程的对应物。

Alan Turing 证明了每个可以用命令式编程编写的程序也可以用函数式编程/lambda 演算（使用递归）编写

二叉搜索树中的高度函数

Height function in Binary Search Tree

c++

tree

binary-search-tree