二次二叉树插入段错误

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); 
} 

而且成员null，这是否意味着内容为空？ 对不起格式化

Answer 1

当我初始化一个指针为null，这是否意味着内容为空？

不会。当您将指针初始化为空值时，它会将其设置为零。您仍然可以访问空指针并从中检索成员但在大多数操作系统上，这会导致崩溃，如分段错误。

您的崩溃是因为您为指针分配了一个指针，请参阅typedef BStree2_node** BStree2;双星号表示它是一个双指针类型（指向指针的指针）。

然后，您在bs_tree2_ini()中将内容初始化为NULL（因此，您有一个有效的NULL指针）。然后，您取消引用bs2_tree2_insert()中的第二个指针。

如果（* bst）为NULL，则不应设置其任何成员。这不是一个有效的指针。您需要先分配一个结构。例如，

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