c - BST 中的这个递归函数如何返回一个有序的链表

Question

BST中的这个递归函数如何返回一个有序的链表？

给定：（结构）

typedef struct TreeNode
{
    struct TreeNode *left ;  //left child
    struct TreeNode *right ;     //right child
    struct TreeNode *next ;  //field for linked list in tree
    Data Node_info;             //info data in node
} TreeNode;

假设我们有一个数字为 3,2,4 的 BST。（3 是根，2 是左子，4 是右子）

我有 2 个执行相同操作的函数，它们从 BST 创建一个链表。我无法跟进这里的递归，如果有人能帮我弄清楚，那就太棒了！

第一个功能：

void  what1(TreeNode **head, TreeNode *root)
{
     if(root == NULL) 
           return; 
     what1((head),root->right);
     root->next=(*head);
     (*head)=root;
     what1((head),root->left);
}

我的计算：转到右子树，直到我们达到 null，返回，在 NULL 上制作 4-> 下一个点，在 4 上制作头部点，然后向左，返回 4，再次返回到 1，现在是 3->4 上的下一个点，并在 4 上生成头部点，依此类推。

但是我仍然不了解其他函数何时"暂停"以及何时执行它们，这意味着我的计算不准确，并且我无法正确跟进函数，这意味着我缺乏对递归的理解。

这是第二个函数，我完全不知道如何遵循它，它实际上做同样的事情。如果您可以帮助我使用任何这些函数，我将不胜感激，因为我正在尝试完全理解 BST 的递归。我在这里发布许多关于这个问题的问题，直到我完全理解这一点。

TreeNode * what2(TreeNode *root)
{
    TreeNode *left = NULL, *right = NULL, *tmp = root;
    if (root != NULL) 
    {      
        left = what2(root->left);      
        right = what2(root->right);      
        root->next = right;      
        if (left != NULL)
        {
            tmp=left;  
            while (left->next != NULL)              
                left=left->next;         
            left->next=root;      
        }   
    } 
    return tmp;
}   

Answer 1

你对第一个函数的工作方式是正确的，你基本上从头到尾构建树。

要理解第二个，您需要注意的是，它将在子树中创建一个列表，然后合并两个列表。调用该函数时，将执行以下步骤：

1. 获取仅从左侧节点创建的列表的头部
2. 获取仅从正确节点创建的列表的头部
3. 通过将左侧列表的末尾设置为指向根来附加根节点，然后将根指向右侧列表的开头。

这可以通过

1.

left = what2(root->left);

在您的示例中，这将简单地返回左节点，因为它是单独的，但是发生这种情况是因为左节点的left->left和left->right为 NULL，因此它只返回 left 。

阿拉伯数字。

right = what2(root->right);

同样的事情在这里发生，但使用正确的节点。

3.

root->next = right;      
if (left != NULL)
{
    tmp=left;  
    while (left->next != NULL)              
        left=left->next;         
    left->next=root;      
} 

在这里，我们首先将root->next设置为 right，以便我们基本上创建了列表的中间。然后，将tmp设置为 left，因为它将成为列表的头部（最左边，所以开始）。然后遍历左侧列表，直到我们可以将最后一个元素设置为 root .这将创建一个从left到root到right的连续列表，因此按顺序排列。

Answer 2

这是

给what1的。

在这里，head是一个Node ** - 这意味着：

head   : is a : pointer to a pointer to TreeNode
*head  : is a : pointer to a TreeNode
**head : is a : TreeNode

现在，当what1从main（或其他函数）调用它时，它的调用方式如下：

/* Suppose root points to root TreeNode in tree */
/* ll_head will point to first node in linked list */
TreeNode *ll_head = NULL;
/* Call what1 and pass address of ll_head so that
 * address of the first node in linked_list can be stored in ll_head
 */  
what1(&ll_head, root);

现在看看当what1(&llhead, root)时会发生什么，（即 what1(&ll_head, node 3) ） 称为：

调用 what1(&ll_head, node 3) 时，它会执行以下操作：

1. 调用（&ll_head，节点 4）
2. 对节点 3 进行一些处理
3. 调用（&ll_head，节点 2）

让我们一一看：

1. 在节点 4 中

4->next = (*head) /* which right now is pointing to NULL */ 
(*head) /* which is ll_head in main */ = address of node 4 

所以，到现在为止：

4->next = NULL, and 
(*head) /* which is ll_head in main */ =  address of node 4

2. 节点 3 中的处理

3->next = (*head) /* which right now is pointing to node 4 */
(*head) /* which is ll_head in main */ = address of node 3

所以，到现在为止：

4->next is NULL,
3->next = address of node 4, and
(*head) /* which is ll_head in main */  = address of node 3

3. 在节点 2 中

2->next = (*head) /* which right now is pointing to node 3 */
3->next = address of node 4
4->next = NULL, and
(*head) /* which is ll_head in main */  = address of node 2

所以当 what1（*ll_head， node3） 返回时，这将是事物的状态：

ll_head = address of node 2
2->next = address of node 3
3->next = address of node 4
4->next = NULL

这是此BST的顺序链表。