C语言 不能向二叉树插入节点

Question

我正试图将节点插入二叉树。这是我创建Node的函数(其余部分已经完成)。

void BVSCreate_function(TNodef *rootPtr, function_save token) {
TNodef *newPtr = malloc(sizeof(struct tnodef));
if (newPtr == NULL) {
fprintf(stderr, "99");
return;
}
TNodef init;
string initStr;
initStr.str = NULL;
initStr.length = 0;
initStr.alloc = 0;
newPtr = &init;
newPtr->content = &initStr;
newPtr->leftPtr = NULL;
newPtr->rightPtr = NULL;
newPtr->return_type = token.ret_value;
newPtr->parameters = token.param_count;
strCpyStr(newPtr->content, token.content);
rootPtr = newPtr;
}
void BVSInsert_function(TNodef *rootPtr, function_save token) {
if (rootPtr == NULL) {
BVSCreate_function(rootPtr, token);
} else {
if ((strCmpStr(token.content, rootPtr->content)) < 0) {
BVSCreate_function(rootPtr->leftPtr, token);
} else
if ((strCmpStr(token.content, rootPtr->content)) > 0) {
BVSCreate_function(rootPtr->rightPtr, token);
}
}
}

当TNodef和function_save为结构体时:

typedef struct {
string *content;
int param_count;
int ret_value;
} function_save;
typedef struct tnodef {
string *content;
struct tnodef *leftPtr;
struct tnodef *rightPtr;
int parameters;
int return_type;
} TNodef;

其中string定义为如下结构体:

typedef struct {
char *str;  // content of string
int length; // length of string
int alloc;  // amount of memory allocated
} string;

strCpystr功能:

int strCpyStr(string *s1, string *s2) {
int len2 = s2->length;
if (len2 > s1->alloc) {
if (((s1->str) = (char *)realloc(s1->str, len2 + 1)) == NULL) {
return 1;
}
s1->alloc = len2 + 1;
}
strcpy(s1->str, s2->str);
s1->length = len2 + 1;
return 0;
}

我试图在二叉树中创建一个节点，并从结构体function_save中获取信息。但是当我尝试在插入后打印这棵树时，它显示树仍然是空的。

Answer 1

您在BVSCreate_function中的代码有未定义的行为，因为:

• newPtr = &init;丢弃分配的节点，而使用本地结构，该结构将在函数返回时立即失效。

• newPtr->content = &initStr;是不正确的，同样的原因:你应该为string分配内存，或者可能修改TNodeDef，使content成为string对象，而不是指针。

函数BVSInsert_function不返回更新后的根指针，因此调用方的根节点永远不会更新。你可以通过传递要更新的指针的地址来改变API。

在BVSInsert_function中也有一个混淆:当沿着树向下走时，它应该递归地调用自己，而不是调用BVSCreate_function。

修改后的版本:

/* Allocate the node and return 1 if successful, -1 on failure */
int BVSCreate_function(TNodef **rootPtr, function_save token) {
TNodef *newPtr = malloc(sizeof(*newPtr));
string *newStr = malloc(sizeof(*content));
if (newPtr == NULL || newStr == NULL) {
fprintf(stderr, "99");
free(newPtr);
free(newStr);
return -1;
}
newStr->str = NULL;
newStr->length = 0;
newStr->alloc = 0;
newPtr->content = newStr;
newPtr->leftPtr = NULL;
newPtr->rightPtr = NULL;
newPtr->return_type = token.ret_value;
newPtr->parameters = token.param_count;
strCpyStr(newPtr->content, token.content);
*rootPtr = newPtr;
return 1;
}
int BVSInsert_function(TNodef **rootPtr, function_save token) {
if (*rootPtr == NULL) {
return BVSCreate_function(rootPtr, token);
} else {
if (strCmpStr(token.content, rootPtr->content) < 0) {
return BVSInsert_function(&rootPtr->leftPtr, token);
} else
if ((strCmpStr(token.content, rootPtr->content)) > 0) {
return BVSInsert_function(&rootPtr->rightPtr, token);
} else {
/* function is already present: return 0 */
return 0;
}
}
}

还请注意，如果s1->len是字符串的长度，则函数strCpyStr可能会在分配区域的末尾len2 == s1->alloc之外写入，不包括空终止符。

修改后的版本:

int strCpyStr(string *s1, const string *s2) {
int len2 = s2->length;
if (len2 >= s1->alloc) {
char *newstr = (char *)realloc(s1->str, len2 + 1);
if (newstr == NULL) {
return 1;
}
s1->str = newstr;
s1->alloc = len2 + 1;
}
strcpy(s1->str, s2->str);
s1->length = len2;
return 0;
}