二叉搜索樹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);。如果我取消註釋這一行，編譯程序並運行它，程序將引發分段錯誤。任何人都可以告訴我爲什麼這個錯誤正在發生，爲什麼整個代碼沒有運行？提前致謝。

Answer 1

在頂部，你聲明

node *rootNode = NULL; 

如果你不跑insertNode（成功 - 見馬特的答案），試圖打印它時，該節點將仍然是NULL，這就是爲什麼你得到段錯誤。

Answer 2

你對C處理參數的方式有一種誤解。在C中，所有參數都通過值傳遞，包括指針。當您在函數內重新分配一個指針時，您將重新分配該指針的一個副本。

例如：

void f (int *p); 

int *p; 

f(p); 

指針的地址（&p）是在功能不同。他們都指向相同的位置（有相同的值），但每個都有不同的地址。當您將指針指定給返回值malloc時，它只分配該指針的函數本地副本。

解決此問題的一種方法是引入另一個間接級別，並傳遞指針的地址：void insertNode(int i, node **n)，您可以調用該地址，如insertNode(0, &n)。當你想把它改成別的東西時，請將它解引用一次，然後，然後分配：*p = malloc(sizeof(node))。

另一種解決方案是讓函數返回指針並將其分配給調用代碼：return malloc(sizeof(node))。 （注意：你會在初始化代碼後返回它......也不會在C中返回malloc的返回值）。

Answer 3

當您取消註釋printf語句時代碼段錯誤的原因是因爲rootNode是一個NULL指針。在函數調用中解引用這個NULL指針會導致段錯誤。

rootNode是一個NULL指針的原因是它永遠不會被代碼改變。調用insertNode()導致局部變量n被設置爲存儲在rootNode（在本例中爲NULL）中的值。 insertNode()函數中的n的更改不會更改rootNode。

要修復代碼，您可以更改insertNode和deleteNode函數以接受指向根節點指針的指針。例如，insertCode()功能將成爲：

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()到根節點insertNode(num, &rootNode);

我也建議您檢查一下scanf函數調用的返回值。如果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); 

早些時候的變化停留在功能插入只要。在裏面使用雙指針。