c - 二级二叉树插入分段错误

Question

在检查 bst 中的节点是否为空后，当我尝试将值分配给 bst 的成员时出现分段错误

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

typedef int Data_Item;

struct Bst2_Node
{
  int key;
  Data_Item data;
  struct Bst2_Node *left, *right;
};
typedef struct Bst2_Node BStree2_node;
typedef BStree2_node** BStree2;


BStree2 bs_tree2_ini(void)
{
  BStree2 bst;
  bst =(BStree2)malloc(sizeof(BStree2_node *));
  *bst=NULL;
  return bst;
}

void bs_tree2_insert(BStree2 bst, int key, Data_Item data)
{
  if(*bst==NULL)
{
    (*bst)->key = key;
    (*bst)->data = data;
}

  else if(key < (*bst)->key)
{
    bs_tree2_insert(&(*bst)->left, key, data);
}
  else if(key > (*bst)->key)
{
    bs_tree2_insert(&(*bst)->right, key, data);
}
  else return;
}

Data_Item *bs_tree2_search(BStree2 bst, int key)
{
    if(key==(*bst)->key)
{
    return &(*bst)->data;
}
    else return NULL;
}

void bs_tree2_traversal(BStree2 bst)
{
    if(!*bst) return;

    bs_tree2_traversal(&(*bst)->left);
    printf("%d\n", (*bst)->data);
    bs_tree2_traversal(&(*bst)->right);
}

static void btree_free(BStree2_node *bt)
{
   if(bt == NULL) return;
   btree_free(bt->left);
   btree_free(bt->right);
   free(bt);
}

void bs_tree2_free(BStree2 bst)
{
   btree_free(*bst);
   free(bst);
}

int main(int argc, char** argv)
{
 int a;
 int b;
 a = 1;
 b = 2;
 BStree2 bst = bs_tree2_ini();
 printf(".");
 bs_tree2_insert(bst, a, b);
 //bs_tree2_traversal(bst);
 bs_tree2_free(bst);
 return (0);
}

另外，当我将 a 指针初始化为空时，这是否意味着内容也为空？抱歉格式化

Answer 1

when I initialize the a pointer to null, does that mean the contents are null as well?

No. When you initialize the a pointer to null, it sets it to point to zero. You can still access a null pointer and retrieve members from it but on most operating systems, this will cause a crash such as a segmentation fault.

Your crash is because you allocate a pointer to a pointer, see typedef BStree2_node** BStree2; the double asterisk indicates it's a double pointer type (pointer to a pointer).

Then you initialize the contents to NULL (so, you have a valid pointer to NULL) in bs_tree2_ini(). Then you dereference the second pointer in bs2_tree2_insert().

If (*bst) is NULL, you should not set any of its members. It is not a valid pointer. You need to allocate a structure first. For example,

if ((*bst)==NULL)
{
    (*bst) = (BStree2_node*)malloc(sizeof(BStree2_node));
    if ((*bst) == NULL)
    {
        // allocation failed.
    }
    else
    {
        // allocation success. set data members here.
    }
}

Answer 2

我不确定为什么这些天教师们对哨兵节点感到高兴，但它们不是必需的。该值NULL与其他任何值一样好。考虑这样的实现，我强烈建议您花大量时间盯着、研究，如果可能的话，使用调试器单步执行：

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

typedef int Data_Item;
typedef struct BST_Node
{
    int key;
    Data_Item data;
    struct BST_Node *left, *right;
} BST_Node;

typedef enum
{
    BST_TRAVERSE_PREORDER,
    BST_TRAVERSE_INORDER,
    BST_TRAVERSE_POSTORDER
} BST_TRAVERSE_TYPE;

// allocate a new BST node and copy in the passed data
BST_Node *BST_newnode(int key, Data_Item data)
{
    BST_Node *p = malloc(sizeof(*p));
    p->left = p->right = NULL;
    p->key = key;
    p->data = data;
    return p;
}

// insert. recurses until we reach a null node, then performs
//  the insertion at that node pointer. initial invoke is done
//  using the address of the root of our tree.
//
// note: this implementation does NOT allow duplicates
void BST_insert(struct BST_Node** p, int key, Data_Item data)
{
    if (*p == NULL)
    {
        *p = BST_newnode(key, data);
    }
    else if (key < (*p)->key)
    {
        BST_insert(&(*p)->left, key, data);
    }

    else if ((*p)->key < key)
    {
        BST_insert(&(*p)->right, key, data);
    }
}

// traverses based on traversal selection type
void BST_traverse(BST_Node* p, BST_TRAVERSE_TYPE tt,
                  void (*pfn)(int, Data_Item* data))
{
    if (!p)
        return;

    switch (tt)
    {
        case BST_TRAVERSE_PREORDER:
            pfn(p->key, &p->data);
            BST_traverse(p->left, tt, pfn);
            BST_traverse(p->right,tt, pfn);
            break;

        case BST_TRAVERSE_INORDER:
            BST_traverse(p->left, tt, pfn);
            pfn(p->key, &p->data);
            BST_traverse(p->right,tt, pfn);
            break;

        case BST_TRAVERSE_POSTORDER:
            BST_traverse(p->left, tt, pfn);
            BST_traverse(p->right,tt, pfn);
            pfn(p->key, &p->data);
            break;
    }
}

// deletes a node AND all its children
void BST_delete_all(BST_Node** p)
{
    // do nothing on a null pointer
    if (!*p)
        return;

    BST_delete_all(&(*p)->left);
    BST_delete_all(&(*p)->right);
    free(*p);
    *p = NULL;
}


// my print function
void print_data(int key, Data_Item* pData)
{
    printf("Key %.2d ==> %d\n", key, *pData);
}

int main(int argc, char *argv[])
{
    srand((unsigned)time(0));
    BST_Node* root = NULL;
    for (int i=0;i<16;++i)
        BST_insert(&root, rand()%50, i);

    printf("Preorder Traversal\n");
    printf("=================\n");
    BST_traverse(root, BST_TRAVERSE_PREORDER, &print_data);

    printf("\nInorder Traversal\n");
    printf("=================\n");
    BST_traverse(root, BST_TRAVERSE_INORDER, &print_data);

    printf("\nPostorder Traversal\n");
    printf("=================\n");
    BST_traverse(root, BST_TRAVERSE_POSTORDER, &print_data);

    // delete the tree
    BST_delete_all(&root);

    return EXIT_SUCCESS;
};

样本输出

Preorder Traversal
=================
Key 30 ==> 0
Key 07 ==> 2
Key 05 ==> 4
Key 04 ==> 5
Key 03 ==> 8
Key 24 ==> 3
Key 17 ==> 7
Key 10 ==> 14
Key 16 ==> 15
Key 19 ==> 9
Key 29 ==> 12
Key 43 ==> 1
Key 40 ==> 10
Key 39 ==> 11

Inorder Traversal
=================
Key 03 ==> 8
Key 04 ==> 5
Key 05 ==> 4
Key 07 ==> 2
Key 10 ==> 14
Key 16 ==> 15
Key 17 ==> 7
Key 19 ==> 9
Key 24 ==> 3
Key 29 ==> 12
Key 30 ==> 0
Key 39 ==> 11
Key 40 ==> 10
Key 43 ==> 1

Postorder Traversal
=================
Key 03 ==> 8
Key 04 ==> 5
Key 05 ==> 4
Key 16 ==> 15
Key 10 ==> 14
Key 19 ==> 9
Key 17 ==> 7
Key 29 ==> 12
Key 24 ==> 3
Key 07 ==> 2
Key 39 ==> 11
Key 40 ==> 10
Key 43 ==> 1
Key 30 ==> 0