二叉搜索树C的实现

问题描述：

我最近写了一段相当简单的代码，尝试在C中使用插入，搜索，删除和显示操作来实现二叉搜索树。不幸的是，代码似乎不起作用。二叉搜索树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);。如果我取消注释这一行，编译程序并运行它，程序将引发分段错误。任何人都可以告诉我为什么这个错误正在发生，为什么整个代码没有运行？提前致谢。

答

在顶部，你声明

node *rootNode = NULL;

如果你不跑insertNode（成功 - 见马特的答案），试图打印它时，该节点将仍然是NULL，这就是为什么你得到段错误。

为什么downvote？我意识到这不是完整的答案，但OP也试图在打印时询问为什么他的代码段错误。 – 2013-05-09 02:00:35

答

你对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的返回值）。

答

当您取消注释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的内容未定义。理想情况下，代码将优雅地处理这种情况。

答

我觉得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);

早些时候的变化停留在功能插入只要。在里面使用双指针。

二叉搜索树C的实现

相关推荐