2

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

谁能帮助我提供原因或参考链接以了解为什么它是指向指针的指针。

/*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);


}
}
4

3 回答 3

3

"I want to know the reason why do we use, pointer to pointer while inserting nodes in the binary tree. But, While traversing the binary tree, we just refer the tree by simple pointer to the root node. But why while inserting node?"

我们实际上甚至不需要代码来回答这个问题。如果要在 C 中的外部函数中修改（写入）数据，则需要知道数据的地址。就像：

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

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

没有任何意义。您（在此示例中）获得了变量的本地副本，对值所做的任何更改都仅在本地范围内。如果您希望这些更改传播回调用函数，您需要地址：

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;
}
于 2013-06-20T17:48:32.193 回答
2

这是因为插入的第一部分它分配了一个新的结构树节点。如果你只传入一个结构树节点 * 这看起来像这样：

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;
   }
  ...
}

这样做的问题是 bt 是本地插入的，因此 main 中的 bt 将保持不变。所以你传入一个指向 main 的 bt 的指针，它允许 insert 改变它。

于 2013-06-20T17:48:01.660 回答
1

这里给出了一个关于使用指针的非常好的提示：试试这个基础知识：-

http://www.geeksforgeeks.org/how-to-write-functions-that-modify-the-head-pointer-of-a-linked-list/

于 2013-06-27T15:02:22.647 回答