为什么在这个编程中使用指针指针？

Question

以下程序显示了如何在C程序中构建二叉树。它使用动态内存分配，指针和递归。二叉树是一个非常有用的数据结构，因为它允许在排序列表中进行高效插入，搜索和删除。由于这样的树本质上是一个递归定义的结构，所以递归编程是处理它的自然和有效的方式。

tree 
    empty 
    node left-branch right-branch 

left-branch 
    tree 

right-branch 
    tree 

下面的代码：

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

struct tree_el { 
    int val; 
    struct tree_el * right, * left; 
}; 

typedef struct tree_el node; 

void insert(node ** tree, node * item) { 
    if(!(*tree)) { 
     *tree = item; 
     return; 
    } 
    if(item->val<(*tree)->val) 
     insert(&(*tree)->left, item); 
    else if(item->val>(*tree)->val) 
     insert(&(*tree)->right, item); 
} 

void printout(node * tree) { 
    if(tree->left) printout(tree->left); 
    printf("%d\n",tree->val); 
    if(tree->right) printout(tree->right); 
} 

void main() { 
    node * curr, * root; 
    int i; 

    root = NULL; 

    for(i=1;i<=10;i++) { 
     curr = (node *)malloc(sizeof(node)); 
     curr->left = curr->right = NULL; 
     curr->val = rand(); 
     insert(&root, curr); 
    } 

    printout(root); 
} 

为什么使用指针到指针？

Answer 1

因为插入方法需要修改树的根。

Answer 2

更精确的答案将是： 因为函数需要更换某一领域（指针）

Answer 3

白板它的内容。或修改示例代码来做到这一点：

for(i=1;i<=10;i++) { 
    curr = (node *)malloc(sizeof(node)); 
    curr->left = curr->right = NULL; 
    curr->val = rand(); 
    printf("before: %d\n", root); 
    insert(&root, curr); 
    printf("after: %d\n", root); 
} 

// printout(root); 

打印结果如下：
前：0
后：3871888
前：3871888
后：3871888
前：3871888
之后：3871888

这是为什么？

因为它改变了你传递给它的指针。

如何插入工作：插入遍历树。首先访问当前节点。然后左节点（通过递归）。然后右节点（通过递归）。如果涉及到一个空的节点（NULL），它会用item替换该节点。

为此，它取消引用外部指针，并将指针“item”的值分配给该内部指针。

在一般情况下，指针就像int或char。您按值传递指针。如果取消引用它，则可以修改它指向的任何内容，但不能修改指针本身。如果传递指针指针，则可以更改内部指针，但外部指针不能。

这里的一些指针示例代码来啃：

#include <cstdio> 
#include <cstdlib> 

void some_func(int* value) 
{ 
    *value = 12; 
} 

int main(int argc, char* argv[]) 
{ 
    int a = 5; 
    printf("%d\n", a); // prints 5 
    some_func(&a); 
    printf("%d\n", a); // prints 12 

    int b = 7; 
    int* c = &b; 
    printf("%d\n", b); // prints 7 
    printf("%d\n", c); // prints 2029440 (some random memory address) 
    some_func(c); 
    printf("%d\n", b); // prints 12 
    printf("%d\n", c); // prints 2029440 (the same value as before) 
} 

和：

#include <cstdio> 
#include <cstdlib> 

void some_other_func(int** other_value) 
{ 
    *other_value = NULL; 
} 

int main(int argc, char* argv[]) 
{ 
    int b = 7; 
    int* c = &b; 

    printf("%d\n", c); // prints 4718288 (some random memory address) 
    some_other_func(&c); 
    printf("%d\n", c); // prints 0 
} 

最后但并非最不重要的：

#include <cstdio> 
#include <cstdlib> 

void some_third_func(int* third_value) 
{ 
    *third_value = 12; 
    int** lets_modify_third_value = &third_value; 
    *lets_modify_third_value = NULL; 
} 

int main(int argc, char* argv[]) 
{ 
    int b = 7; 
    int* c = &b; 

    printf("%d\n", b); // prints 7 
    printf("%d\n", c); // prints 1637380 (some random memory address) 
    some_third_func(c); 
    printf("%d\n", b); // prints 12 
    printf("%d\n", c); // prints 1637380 (same as before. Note that the pointer was passed by value, so "third_value" was just a COPY of the address) 
} 

Answer 4

的替代的 '在去'参数 - 一个返回值，需要在每个访问级别进行额外的分配：

typedef node* node_ref; 

node_ref insert (node_ref tree, node_ref item) { 
    if (!tree) 
     return item; 

    if (item -> val < tree -> val) 
     tree -> left = insert (tree -> left, item); 
    else if (item -> val > tree -> val) 
     tree -> right = insert (tree -> right, item); 

    return tree; 
} 

... 
// in the loop 
    root = insert (root, curr); 

该方法（或与原始代码）的另一个缺点是，无法告诉节点是否被插入;如果添加了一个返回值，以表明它，你不必泄漏curr如果不插入：

typedef node* node_ref; 

bool insert (node_ref *tree, node_ref item) { 
    if (!*tree) { 
     *tree = item; 
     return true; 
    } 

    if (item -> val < (*tree) -> val) 
     return insert (& (*tree) -> left, item); 

    if (item -> val > (*tree) -> val) 
     return insert (& (*tree) -> right, item); 

    return false; 
} 

... 
// in the loop 
for (int i = 1; i <= 10; ++i) { 
    node_ref curr = malloc (sizeof (node)); 

    curr -> left = curr -> right = NULL; 
    curr -> val = rand(); 

    if (! insert (&root, curr)) 
     free (curr); 
}