バイナリ検索ツリーCの実装

Question

私は最近、挿入、検索、削除、および表示操作でバイナリ検索ツリーをC言語で実装しようとするかなり単純なコードを書いています。残念ながら、コードは機能していないようです。

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

struct TreeNode { 
    int data; 
    struct TreeNode *leftChildNode; 
    struct TreeNode *rightChildNode; 
}; 

typedef struct TreeNode node; 
node *rootNode = NULL; 

void insertNode(int i, node *n) { 
    if(n == NULL) { 
     n = (node*)malloc(sizeof(node)); 
     n->leftChildNode = NULL; 
     n->rightChildNode = NULL; 
     n->data = i; 
    } 
    else 
    if(n->data == i) 
     printf("\nThis value already exists in the tree!"); 
    else 
    if(i > n->data) 
     insertNode(i, n->rightChildNode); 
    else 
     insertNode(i, n->leftChildNode); 
    } 

void searchNode(int i, node *n) { 
    if(n == NULL) 
     printf("\nValue does not exist in tree!"); 
    else 
    if(n->data == i) 
     printf("\nValue found!"); 
    else 
    if(i > n->data) 
     searchNode(i, n->rightChildNode); 
    else 
     searchNode(i, n->leftChildNode); 
    } 

void deleteNode(int i, node *n) { 
    if(n == NULL) 
     printf("\nValue does not exist in tree!"); 
    else 
    if(n->data == i) { 
     if(n->leftChildNode == NULL) 
      n = n->rightChildNode; 
     else 
     if(n->rightChildNode == NULL) 
      n = n->leftChildNode; 
     else { 
      node *temp = n->rightChildNode; 
      while(temp->leftChildNode != NULL) 
       temp = temp->leftChildNode; 
      n = temp; 
     } 
    } 
    else 
    if(i > n->data) 
     deleteNode(i, n->rightChildNode); 
    else 
     deleteNode(i, n->leftChildNode); 
    } 

void displayPreOrder(node *n) { 
    if(n != NULL) { 
     printf("%d ", n->data); 
     displayPreOrder(n->leftChildNode); 
     displayPreOrder(n->rightChildNode); 
    } 
} 

void displayPostOrder(node *n) { 
    if(n != NULL) { 
     displayPostOrder(n->leftChildNode); 
     displayPostOrder(n->rightChildNode); 
     printf("%d ", n->data); 
    } 
} 

void displayInOrder(node *n) { 
    if(n != NULL) { 
     displayInOrder(n->leftChildNode); 
     printf("%d ", n->data); 
     displayInOrder(n->rightChildNode); 
    } 
} 

int main(void) { 
    int ch, num, num1; 
    do { 
     printf("\nSelect a choice from the menu below."); 
     printf("\n1. Insert a node."); 
     printf("\n2. Search for a node."); 
     printf("\n3. Delete a node."); 
     printf("\n4. Display the Binary Search Tree."); 
     printf("\nChoice: "); 
     scanf("%d", &ch); 
     switch(ch) { 
      case 1: printf("\nEnter an element: "); 
        scanf("%d", &num); 
        //printf("YESYES"); 
        insertNode(num, rootNode); 
        break; 

      case 2: printf("\nEnter the element to be searched for: "); 
        scanf("%d", &num); 
        searchNode(num, rootNode); 
        break; 

      case 3: printf("\nEnter the element to be deleted: "); 
        scanf("%d", &num); 
        deleteNode(num, rootNode); 
        break; 

      case 4: printf("\nSelect an order for the elements to be display in."); 
        printf("\n1. Pre-order."); 
        printf("\n2. Post-order."); 
        printf("\n3. In-order."); 
        printf("\nChoice: "); 
        scanf("%d", &num1); 
        switch(num1) { 
         case 1: printf("\nPre-order Display: "); 
           displayPreOrder(rootNode); 
           break; 

         case 2: printf("\nPost-order Display: "); 
           displayPostOrder(rootNode); 
           break; 

         case 3: printf("\nIn-order Display: "); 
           displayInOrder(rootNode); 
           break; 

         default: exit(0); 
        } 
        break; 

      default: exit(0); 
      } 
     //printf("%d", rootNode->data); 
     printf("\nIf you want to return to the menu, press 1."); 
     printf("\nChoice: "); 
     scanf("%d", &num); 
    } while(num == 1); 

    return 0; 
} 

は実際には、ちょうどmain()両端でdo-whileブロックの前にコメント行printf("%d", rootNode->data);に気づきます。この行のコメントを外してプログラムをコンパイルして実行すると、プログラムはセグメンテーション違反をスローします。誰も、なぜこのエラーが発生しているのか、なぜコード全体が動いていないのか教えていただけますか？前もって感謝します。それを印刷しようとすると、ノードがまだNULLになり、あなたが取得している理由です - 上部に

Answer 1

、あなたは（マットの答えを参照してくださいに成功）insertNodeを実行しない場合

node *rootNode = NULL; 

を宣言しますsegfault。

Answer 2

Cが引数を処理する方法について誤解があります。 Cでは、すべての引数はポインタを含む値で渡されます。関数内でポインタを再割り当てすると、そのポインタのコピーが再割り当てされます。例えば

：

void f (int *p); 

int *p; 

f(p); 

ポインタのアドレス（&p）は機能が異なります。彼らは両方とも同じ場所（同じ値の）を指していますが、それぞれがのです。ポインタを戻り値mallocに割り当てると、そのポインタの関数ローカルコピーのみが割り当てられます。

これを修正する方法の1つは、別のレベルのインダイレクションを導入し、ポインタのアドレス（void insertNode(int i, node **n)）を渡すことです。これはinsertNode(0, &n)のように呼び出すことができます。それを他のものに変更したい場合は、一度参照解除して、次にを割り当てます：*p = malloc(sizeof(node))。

もう1つの解決策は、関数にポインタを返し、呼び出しコードに割り当てる方法です：return malloc(sizeof(node))。 （注：実際には、初期化コードの後に​​返すでしょう... Cの返り値mallocもキャストしないでください）。

Answer 3

printfステートメントをコメント解除するときにコードsegfaultsが発生するのは、rootNodeがNULLポインターであるためです。このNULLポインターを関数呼び出しで省略すると、segfaultが発生します。

rootNodeがNULLポインタである理由は、コードによって決して変更されないということです。 insertNode()を呼び出すと、ローカル変数nはrootNode（この場合はNULL）に格納されている値に設定されます。 insertNode()関数のnの変更はrootNodeに変更されません。

コードを修正するには、insertNodeとdeleteNode関数を変更して、ルートノードポインタへのポインタを受け入れることができます。例えばinsertCode()機能はなる：あなたはまた、私はまた、あなたが様々なscanfの呼び出しの戻り値を確認することをお勧めルートノードinsertNode(num, &rootNode);を参照して

をinsertNode()を呼び出すようにコードを変更する必要があります

void insertNode(int i, node **n) { 
    if(*n == NULL) { 
     (*n) = (node*)malloc(sizeof(node)); 
     (*n)->leftChildNode = NULL; 
     (*n)->rightChildNode = NULL; 
     (*n)->data = i; 
    } 
    else 
    { 
     if((*n)->data == i) 
     { 
      printf("\nThis value already exists in the tree!"); 
     } 
     else 
     { 
      if(i > (*n)->data) 
       insertNode(i, &(*n)->rightChildNode); 
      else 
       insertNode(i, &(*n)->leftChildNode); 
     } 
    } 
} 

。 scanf("%d",x)が0を返した場合、値はintに変換されず、xの内容は未定義です。理想的には、コードはこのケースを正常に処理します。

Answer 4

私はprobblemは、以下のコードを試してみてください挿入機能のための署名であり、それは

void insertNode(int i, node **n) { 
    if(*n == NULL) { 
     *n = (node*)malloc(sizeof(node)); 
     (*n)->leftChildNode = NULL; 
     (*n)->rightChildNode = NULL; 
     (*n)->data = i; 
    } 
    else 
    if((*n)->data == i) 
     printf("\nThis value already exists in the tree!"); 
    else 
    if(i > (*n)->data) 
     insertNode(i, &((*n)->rightChildNode)); 
    else 
     insertNode(i, &((*n)->leftChildNode)); 
    } 

を仕事と

insertNode(num, &rootNode); 

以前の変更は、関数の挿入に残るよう挿入機能を使用すると思いますのみ。内側にはダブルポインタを使用します。