C中的二叉树

Question

我在C语言中构建二叉树时遇到了问题。我想能够将书籍添加到树中，在这些树中随后出版年份的书籍被添加到左侧，并且早期出版年份被添加在右边。我不断收到运行错误，我不确定为什么。

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


struct book { 
    char* name; 
    int year; 
}; 

typedef struct tnode { 
    struct book *aBook; 
    struct tnode *left; 
    struct tnode *right; 
} BTree; 

BTree* addBook(BTree* nodeP, char* name, int year){ 
    if(nodeP == NULL) 
    { 
     nodeP = (struct tnode*) malloc(sizeof(struct tnode)); 
     (nodeP->aBook)->year = year; 
     (nodeP->aBook)->name = name; 
     /* initialize the children to null */ 
     (nodeP)->left = NULL;  
     (nodeP)->right = NULL; 
    } 
    else if(year > (nodeP->aBook)->year) 
    { 
     addBook(&(nodeP)->left,name,year); 
    } 
    else if(year < (nodeP->aBook)->year) 
    { 
     addBook(&(nodeP)->right,name,year); 
    } 
    return nodeP; 
} 

void freeBTree(BTree* books) 
{ 
    if(books != NULL) 
    { 
     freeBTree(books->left); 
     freeBTree(books->right); 
     //free(books); 
    } 
} 

void printBooks(BTree* books){ 
    if(books != NULL){ 

    } 
} 

int main(int argc, char** argv) { 
    BTree *head; 
    head = addBook(head,"The C Programming Language", 1990); 
    /*addBook(head,"JavaScript, The Good Parts",2008); 
    addBook(head,"Accelerated C++: Practical Programming by Example", 2000); 
    addBook(head,"Scala for the impatient",2012);*/ 
} 

Answer 1

的一个问题是，你是不是初始化为NULL：

BTree *head; 

应该

BTree *head = NULL; 

我建议设置你的编译器警告高。你的两个递归调用不正确，编译器应该警告对他们：

addBook(&(nodeP)->left,name,year); 

应该是：

addBook(nodeP->left,name,year); 

从参数传递的立场。但是，由于当节点指针为NULL时添加了这个函数，因此此函数将无法正常工作，这意味着您无法将父项附加到子项，因为父指针节点已经消失。我认为逻辑应该查看适用的右/左节点，如果为NULL，则在该例程中直接添加，否则递归调用，直到找到具有NULL右/左指针的节点。

事情是这样的：

BTree *makeNode(char *name, int year) 
{ 
    // NOTE: 3 frees required for every node 
    BTree *nodeP = malloc(sizeof(struct tnode)); // 1 
    nodeP->aBook = malloc(sizeof(struct book));  // 2 
    (nodeP->aBook)->year = year; 
    (nodeP->aBook)->name = malloc(strlen(name) + 1); // 3 
    strcpy((nodeP->aBook)->name,name); 
    /* initialize the children to null */ 
    nodeP->left = NULL;  
    nodeP->right = NULL; 
    return nodeP; 
} 

BTree* addBook(BTree* nodeP, char* name, int year) 
{ 
    if (nodeP == NULL) 
    { 
     nodeP = makeNode(name,year); 
    } 
    else if (year > (nodeP->aBook)->year) 
    { 
     if (nodeP->left == NULL) 
      nodeP->left = makeNode(name,year); 
     else 
      addBook(nodeP->left,name,year); 
    } 
    else if(year < (nodeP->aBook)->year) 
    { 
     if (nodeP->right == NULL) 
      nodeP->right = makeNode(name,year); 
     else 
      addBook(nodeP->right,name,year); 
    } 
    return nodeP; 
} 

void printBooks(BTree* books) 
{ 
    if (books != NULL) { 
     printf("book: %s %d\n",books->aBook->name,books->aBook->year); 
     printBooks(books->right); 
     printBooks(books->left); 
    } 
} 

Answer 2

你试图访问一个未初始化的指针nodeP->aBook：

nodeP = (struct tnode*) malloc(sizeof(struct tnode)); 
(nodeP->aBook)->year = year; 

• 你必须与malloc分配空间。或者，将数据直接存储在节点（具有结构，而不是指向结构的指针）中。