c - 在二叉树中添加节点时使用指向结构指针的指针

Question

我想知道为什么我们在二叉树中插入节点时使用指向指针的指针。但是，在遍历二叉树时，我们只是通过指向根节点的简单指针来引用树。但是为什么在插入节点时呢？

任何人都可以帮助我提供原因或引用链接以了解为什么它是 pointer to pointer 。

/*This program clears out all the three methods of traversal */

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

/* Let us basically describe how a particular node looks in the binary tree .... Every node in the tree has three major elements , left child, right child, and  and the data. */

struct  TreeNode {
int data;
struct TreeNode *leftChild;
struct TreeNode *rightChild;
};

void inorder(struct TreeNode *bt);
void preorder(struct TreeNode *bt);
void postorder(struct TreeNode *bt);
int insert(struct TreeNode **bt,int num);

main()
{
int num,elements;
struct TreeNode *bt;
int i;

printf("Enter number of elements to be inserted in the tree");
scanf("%d",&num);

printf("Enter the elements to be inserted inside the tree");
for(i=0;i<num;i++)
{
scanf("%d",&elements);
insert(&bt,elements);
printf("\n");
}

printf("In Order Traversal \n");
inorder(bt);

printf("Pre Order Traversal \n");
preorder(bt);

printf("Post Order Traversal \n");
postorder(bt);

return 0;
}

int insert(struct TreeNode **bt,int num)
{
if(*bt==NULL)
{
*bt= malloc(sizeof(struct TreeNode));

(*bt)->leftChild=NULL;
(*bt)->data=num;
(*bt)->rightChild=NULL;

return;
}
else{
/* */
if(num < (*bt)->data)
{
insert(&((*bt)->leftChild),num);
}
else
{
insert(&((*bt)->rightChild),num);
}
}
return;
}

void inorder(struct TreeNode *bt){
if(bt!=NULL){


//Process the left node
inorder(bt->leftChild);

/*print the data of the parent node */
//printf(" %d ", bt->data);

/*process the right node */
inorder(bt->rightChild);
}

}

void preorder(struct TreeNode *bt){
if(bt)
{
//Process the parent node first
printf("%d",bt->data);

//Process the left node.
preorder(bt->leftChild);

//Process the right node.
preorder(bt->rightChild);


}

}


void postorder(struct TreeNode *bt){

if(bt)
{
//process the left child
postorder(bt->leftChild);

//process the right child
postorder(bt->rightChild);


//process the parent node
printf("%d",bt->data);


}
}

Answer 1

“我想知道为什么我们在二叉树中插入节点时使用指向指针的指针。但是，在遍历二叉树时，我们只是通过指向根节点的简单指针来引用树。但是为什么在插入节点时呢？”

我们实际上什至不需要代码来回答这个问题。如果你想在 C 的外部函数中修改(写入)数据，你需要有数据的地址。就像:

main() {
   int x = 2;
   change_me(x);
   printf("%d\n", x); // prints 2
}

void change_me(int x){
   x++;
}

没有意义。您(在此示例中)获取了 vairable 的本地副本，对值所做的任何更改仅在本地范围内。如果您希望这些更改传播回调用函数，您需要地址:

main() {
   int x = 2;
   change_me(&x);
   printf("%d\n", x); // prints 3
}

void change_me(int* x){
   (*x)++;
}

这同样适用于指针。在链表的例子中，如果我想打印值，我需要遍历树并读取数据。我不需要更改任何内容，只需指针即可。但是，如果我想修改树:

struct node{
   int val;
   sturct node* next;
};

main() {
  struct node* head = malloc(sizeof(struct node));
  head->val = 3;
  insert_a_node_in_front(head);
}

insert_a_node_in_front(node * ptr) {
    struct node* temp = ptr;
    ptr = malloc(sizeof(struct node));
    ptr->val = 5;
    ptr->next = temp;
}

嗯，你猜怎么着？我们实际上并没有插入那个节点，因为 head 的值从未改变过。它仍然指向带有 val==3 的原始节点。原因和之前一样，我们尝试改变参数本地副本的值。如果我们想让这些更改生效，它需要原始副本的地址:

  insert_a_node_in_front(&head);
}

insert_a_node_in_front(node ** ptr) {
    struct node* temp = (*ptr);
    (*ptr) = malloc(sizeof(struct node));
    (*ptr)->val = 5;
    (*ptr)->next = temp;
}