c - C 中二叉树的段错误

Question

我试图用C语言实现我的代码来创建二叉树。代码没有给出任何错误，但在运行时它会导致段错误。无法找出原因。请帮忙。

#include<stdio.h>
#include<malloc.h>

struct node{
    int value;
    struct node *left;
    struct node *right;
}*root = NULL;

struct node* create(int val)
{
    struct node *ptr;
    ptr = (struct node*)malloc(sizeof(struct node));
    ptr->value = val;
    ptr->left = NULL;
    ptr->right = NULL;
    return ptr;
}

void insert(int val)
{
    if(root == NULL)
    {
        root=create(val);
    }
    else if(val < (root)->value)
    {
        (root)->left = create(val);
    }
    else
    {
        (root)->right = create(val);
    }
}

void traverse(struct node** root)
{   
    if(*root==NULL)
        printf("TREE EMPTY");
        return 0;
    while((*root)!=NULL)
    {
        printf("%d",(*root)->value);
        traverse((*root)->left);
        traverse((*root)->right);
    }
}

int main()
{
    int val;
    char ch='y';
    while(ch=='y')
    {
        scanf("%d",&val);
        insert(val);
        printf("Want to insert more elements ?(y or n) =");
        scanf("%c",ch);
    }
    traverse(&root);
    free(root);
    return 0;
}

Answer 1

正如@BLUEPIXY所描述的，段错误是由解析变量ch的值而不是ch的地址引起的。除此之外，您的代码似乎存在一些逻辑错误。

1. 您的 insert 实现仅查看根节点，并根据根值将新值添加到其左子节点或右子节点。所需的行为是 insert 在树结构中向下搜索，直到到达叶节点，然后在此处插入新值。

2. 如 @BLUEPIXY 所示，traverse 函数中的 while ((*root)!=NULL) 等于 while (true) ，因为根元素永远不会更新。在这里，再次，遍历函数所需的行为是导航树结构(通常从左到右)并递归访问当前节点的子节点。下面的代码实现了一种简单的方法来实现这一点，只需在每个子级上调用 traverse，无需 while 循环。

3. 最后，正如@BLUEPIXY 还指出的那样，您以 root 作为参数调用 free 并不会释放整个树。 Free 仅释放其参数指向的内存块。它不会递归地跟踪该内存块内的指针。为了释放树结构所持有的所有资源，您需要再次遍历树并在每个节点上调用free。

以下代码基于您的代码，实现了二叉树。请注意，树在生长过程中不太可能保持平衡。要实现平衡二叉树，您需要在插入新节点时重新建模树。

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

typedef struct node{
    int value;
    struct node *left;
    struct node *right;
} node;

node *root = NULL;

node* create(int val)
{

    node *ptr;
    ptr = (node*)malloc(sizeof(node));
    ptr->value = val;
    ptr->left = NULL;
    ptr->right = NULL;
    return ptr;
}

void insert_(node *root, int val)
{
  if (val < root->value)
  {
    if (root->left != NULL)
    {
        insert_(root->left, val);
        } else {
        root->left = create(val);
        }
    }
    else
    {
        if (root->right != NULL)
        {
            insert_(root->right, val);
        } else {
            root->right = create(val);
        }
    }
}

void insert(int val)
{
    if(root == NULL)
    {
        root = create(val);
    }
    else
    {
        insert_(root, val);
    }
}

void traverse(node *root)
{
    if(root == NULL)
    {
        printf("E");
        return;
    }
    printf("%d (", root->value);
    traverse(root->left);
    printf( ") (");
    traverse(root->right);
    printf( ")");
}

void free_tree(node *root)
{
      if (root == NULL) {
            return;
      }
      free_tree(root->left);
      free_tree(root->right);
      free(root);
}

int main()
{
      int val;
      char ch='y';
      while(ch=='y')
      {
            scanf("%d",&val);
            insert(val);
            printf("Want to insert more elements ?(y or n) =");
            scanf(" %s", &ch);
      }
      traverse(root);
      free_tree(root);
      return 0;
}