在C中插入二叉搜索树

Question

我目前正在学习 C 语言以及一些数据结构，例如二叉搜索树等。我很难理解在某些情况下如何在函数内准确更改指针值，而在其他情况下却不会...我会附上我写的一些代码。这是一个插入函数，可将值插入到 BST 中的正确位置（它应该正常工作）。我尝试使用指向指针的指针来使用函数更改值。即使它有效，我仍然很困惑为什么它真的有效。我不太明白为什么我的插入函数实际上改变了 BST 即使我只在我的插入函数中使用局部变量 (tmp, parent_ptr) 而且我并没有真正取消引用除了“ tmp = * 之外的任何指针p2r " 在插入函数中。

感谢您的帮助。

#include <stdio.h>
#include <stdlib.h>


struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode** createTree(){
    struct TreeNode** p2r;
    p2r = malloc(sizeof(struct TreeNode*));
    *p2r = NULL;
    return p2r;
}

void insert(struct TreeNode** p2r, int val){
    // create TreeNode which we will insert
    struct TreeNode* new_node = malloc(sizeof(struct TreeNode));
    new_node -> val = val;
    new_node -> left = NULL;
    new_node -> right = NULL;
    //define onestep delayed pointer
    struct TreeNode* parent_ptr = NULL;
    struct TreeNode* tmp = NULL;
    tmp = *p2r;
    // find right place to insert node
    while (tmp != NULL){
        parent_ptr = tmp;
        if (tmp -> val < val) tmp = tmp->right;
        else tmp = tmp->left;
    }
    if (parent_ptr == NULL){
        *p2r = new_node;
    }
    else if (parent_ptr->val < val){ //then insert on the right
        parent_ptr -> right = new_node;
    }else{
        parent_ptr -> left = new_node;
    }
}

int main(){
    struct TreeNode **p2r = createTree();
    insert(p2r, 4);
    insert(p2r, 2);
    insert(p2r, 3);
    return 0;
}

Answer 1

虽然指针本身确实是局部变量，但它们指向内存中的特定位置。当您使用 -> 符号取消引用指针时，您基本上是在访问存储指针指向的确切变量的内存。这就是为什么您的更改也反映在函数外部的原因。

你基本上告诉了一个局部变量你的树的存储位置，它有助于插入，然后它超出了范围。树本身不是局部变量，因此更改会反映在它上面。

我建议阅读指针的工作原理。

Answer 2

首先，永远记住关于指针的一件事，它们存储的是内存地址，而不是值。例如：

int val = 5;
int copy = val;
int *original = &val;

printf("%d\n", val);
printf("%d\n", copy);
printf("%d\n", *original);

val = 8;

printf("%d\n", val);
printf("%d\n", copy);
printf("%d\n", *original);

执行这段代码时，输出将是

注意，如何改变val的值，copy的值保持不变，原始指向的值变化。发生这种情况是因为指针 original 指向内存位置 val.

现在，来到插入函数，虽然您只使用局部变量（tmp，parent_ptr），但请记住它们是指针变量，它们引用内存地址。因此，无论何时在循环中，你遍历 tmp -> right 或 tmp -> left，你实际上是在内存中从一个位置跳到另一个位置，以正确的顺序，这就是它起作用的原因。下面的例子会更清楚。

     56 (A)
     /    \
    /      \
  45 (B)  60 (C)

考虑上面的BST，括号中是内存地址。让我们在这个 BST 中插入 40。最初，tmp 将指向 A，地址为 56。现在 40 小于 56，因此 tmp 向左移动，现在指向 B，地址为 45。一次，它再次向左移动，现在它为空。但是现在，parent_ptr 指向 B。因此 40 的新节点附加到 B 的左侧。

      56 (A)
     /    \
    /      \
  45 (B)  60 (C)
  /
 /
40 (D)

Answer 3

让我们一步步分析方法。

首先我们考虑下面的简单程序。

#include <stdio.h>
#include <stdlib.h>

struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void create( struct TreeNode *head, int val )
{
    head = malloc( sizeof( struct TreeNode ) );
    
    head->val   = val;
    head->left  = NULL;
    head->right = NULL;
}

int main(void) 
{
    struct TreeNode *head = NULL;
    
    printf( "Before calling the function create head == NULL is %s\n",
            head == NULL ? "true" : "false" );
            
    create( head, 10 );
    
    printf( "After  calling the function create head == NULL is %s\n",
            head == NULL ? "true" : "false" );
            
    return 0;
}

程序输出为

Before calling the function create head == NULL is true
After  calling the function create head == NULL is true

如您所见，main 中的指针 head 没有改变。原因是该函数处理原始指针值的副本head。所以改变副本不会影响原来的指针。

如果将函数参数重命名为head_parm（以区分原指针head和函数参数）那么你可以想象函数定义和它的调用方式如下

create( head, 10 );

//...

void create( /*struct TreeNode *head_parm, int val */ )
{
    struct TreNode *head_parm = head;
    int val = 10;
    head_parm = malloc( sizeof( struct TreeNode ) );
    //...

在函数内创建了一个局部变量 head_parm，它由参数 head 的值初始化，并且这个函数局部变量 head_parm 在函数内被更改。

表示函数参数按值传递

要更改在 main 中声明的原始指针 head，您需要通过引用传递它。

在 C 中，引用传递机制是通过指向对象的指针间接传递对象来实现的。因此，在函数中取消引用指针，您将可以直接访问原始对象。

所以让我们按照下面的方式重写上面的程序。

#include <stdio.h>
#include <stdlib.h>

struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void create( struct TreeNode **head, int val )
{
    *head = malloc( sizeof( struct TreeNode ) );
    
    ( *head )->val   = val;
    ( *head )->left  = NULL;
    ( *head )->right = NULL;
}

int main(void) 
{
    struct TreeNode *head = NULL;
    
    printf( "Before calling the function create head == NULL is %s\n",
            head == NULL ? "true" : "false" );
            
    create( &head, 10 );
    
    printf( "After  calling the function create head == NULL is %s\n",
            head == NULL ? "true" : "false" );
            
    return 0;
}

现在程序输出是

Before calling the function create head == NULL is true
After  calling the function create head == NULL is false

在你的程序中，你没有像上面的程序那样声明指向头节点的指针

struct TreeNode *head = NULL;

您动态分配了这个指针。事实上你在你的程序中所做的是以下

#include <stdio.h>
#include <stdlib.h>

struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void create( struct TreeNode **head, int val )
{
    *head = malloc( sizeof( struct TreeNode ) );
    
    ( *head )->val   = val;
    ( *head )->left  = NULL;
    ( *head )->right = NULL;
}

int main(void) 
{
    struct TreeNode **p2r = malloc( sizeof( struct TreeNode * ) );
    *p2r = NULL;
    
    printf( "Before calling the function create *p2r == NULL is %s\n",
            *p2r == NULL ? "true" : "false" );
            
    create( p2r, 10 );
    
    printf( "After  calling the function create *p2r == NULL is %s\n",
            *p2r == NULL ? "true" : "false" );
            
    return 0;
}

程序输出为

Before calling the function create *p2r == NULL is true
After  calling the function create *p2r == NULL is false

与之前的程序相比，当您使用 struct TreeNode ** 类型的表达式 &head 调用函数 create 时，您现在引入了一个中间变量 p2r 由于此代码段

而存储表达式 &head 的值

struct TreeNode **p2r = malloc( sizeof( struct TreeNode * ) );
*p2r = NULL;

那是你早点调用函数 create like

create( &head, 10 );

现在实际上你正在调用函数

struct TreeNode **p2r = &head; // where head was allocated dynamically
create( p2r, 10 );

同样的情况也发生在你的程序中。在取消引用指针 p2r 的函数 insert 中，您可以直接访问指向头节点的指针

if (parent_ptr == NULL){
    *p2r = new_node;
    ^^^^ 
}

因此，该函数将指针更改为通过指针 p2r 引用传递的头节点。

其他节点的数据成员 left 和 right 也通过使用指针对它们的引用而改变 parent_ptr

else if (parent_ptr->val < val){ //then insert on the right
    parent_ptr -> right = new_node;
    ^^^^^^^^^^^^^^^^^^^  
}else{
    parent_ptr -> left = new_node;
    ^^^^^^^^^^^^^^^^^^
}

在C中插入二叉搜索树

Inserting into a binary search tree in C

c

pointers

heap-memory

pass-by-reference

binary-search-tree