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

意味がありません。(この例では) 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;
}
于 2013-06-20T17:48:32.193 に答える
2

これは、insert の最初の部分で、新しい構造体ツリーノードを malloc するためです。struct treenode * のみを渡した場合、これは次のようになります。

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 がローカルに挿入されるため、メインの bt が変更されないことです。したがって、main の bt へのポインターを渡すと、insert で変更できるようになります。

于 2013-06-20T17:48:01.660 に答える