对于我的 C 代码，我不确定二叉树是如何循环的，因为我的预期输出与实际输出不同？

Question

我正在跟踪教授给出的部分代码，但我不明白二叉树是如何工作的。问题是：“编写一个函数来查找二叉搜索树中的最低公共祖先和 return 一个指针。树 T 中两个节点 a 和 b 之间的最低公共祖先定义为 T 中同时具有 a 和 b 作为后代的最低节点。以下面的树为例。 4 和 8 的最低共同祖先是 6。4 和 14 的最低共同祖先是 10。

        10
     6     14
   4  8  12  16

我的问题是我不明白它是如何循环的？

node *lca(node *ptr, int a, int b)
{
    if(ptr==NULL)
        return NULL;
    while (ptr != NULL)
    {   
        if (ptr->key >= a && ptr->key <= b)//What's key?
            return (ptr);
        else if (ptr->key > b)
            ptr = ptr->left;
        else if (ptr->key < a)
            ptr = ptr->right;
    }
    return (ptr);
}

Answer 1

这段代码的思路如下：

假设树是二进制排序的，我们可以检查 a 和 b 元素是否在当前节点的不同侧（如果是，我们找到了我们的 lca）。

在二叉树中，对于每个节点，较大的元素向右移动，较小的元素向左移动。所以，如果 a 小于当前节点而 b 更大，则意味着它们来自不同的一侧 -> lca.

ptr->key正在访问节点中的数据。

当第一个 if 语句失败时，这意味着 a 和 b 都来自同一侧 -> 下一个 2 if 语句选择是否继续向右或向左搜索（b 是否比当前节点都小在左侧，如果电流更大，则在右侧）

注意这段代码假定a小于b。

对于我的 C 代码，我不确定二叉树是如何循环的，因为我的预期输出与实际输出不同？

For my C code, I am not sure how the binary tree is looping because my expected output is different then the actual output?

tree

binary-tree

pointers

loops

nodes