我对 C 语言相当陌生，并且一直在学习 K&R 的《The C Programming Language》一书。在对二叉树进行了练习之后，我想为 char*、long 和 double 制作二叉树的标头。
下面的代码中有一个函数让我很伤心——它应该用存储在树中的值以字典顺序填充一个字符指针数组，但是它在某个地方有一个错误。这是字符串树头 btree.h 的代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/************** TYPES **************/
typedef struct ctree
{
char *name;
ctree *left;
ctree *right;
};
/************** Globals **************/
static int c_inc = 0;
/************** Function Prototypes **************/
ctree *add_to_c_tree (ctree *cnode, char *name);
void print_c_tree (ctree *cnode);
ctree *c_tree_alloc (void);
void c_tree_free (ctree *cnode);
void return_c_tree (ctree *cnode, char **array);
/************** Function Definitions **************/
/* add_to_c_tree() : Adds a new node to a *character binary tree */
ctree *add_to_c_tree (ctree *cnode, char *name){
/* If the node is null, allocate memory for it,
* copy the name and set the internal nodes to null*/
if(cnode == NULL){
cnode = c_tree_alloc();
cnode->name = strdup(name);
cnode->left = cnode->right = NULL;
}
/* If initialised then add to the left node if it is lexographically
* less that the node above it else add it to the right node */
else{
if(strcmp(name, cnode->name) < 0)
cnode->left = add_to_c_tree(cnode->left,name);
else if(strcmp(name, cnode->name) > 0)
cnode->right = add_to_c_tree(cnode->right,name);
}
return cnode;
}
/* print_c_tree() : Print out binary tree */
void print_c_tree(ctree *cnode){
if (cnode != NULL) {
print_c_tree(cnode->left);
printf("%s\n",cnode->name);
print_c_tree(cnode->right);
}
}
/* return_c_tree() : return array of strings containing all values in binary tree */
void return_c_tree (ctree *cnode, char **array){
if (cnode != NULL) {
return_c_tree (cnode->left,array+c_inc);
c_tree_free(cnode->left);
*(array+c_inc++) = strdup(cnode->name);
// printf("arr+%d:%s\n", c_inc-1,*(array+(c_inc-1)));
return_c_tree (cnode->right,array+c_inc);
c_tree_free(cnode->right);
}
}
/* c_tree_alloc() : Allocates space for a tree node */
ctree *c_tree_alloc(void){
return (ctree *) malloc(sizeof(ctree));
}
/* c_tree_free() : Free's Memory */
void c_tree_free (ctree *cnode){
free(cnode);
}
我一直在用 bt.c 测试：
#include "btree.h"
int main(void){
ctree *node = NULL; char *arr[100];
node = add_to_c_tree(node, "foo");
node = add_to_c_tree(node, "yoo");
node = add_to_c_tree(node, "doo");
node = add_to_c_tree(node, "woo");
node = add_to_c_tree(node, "aoo");
node = add_to_c_tree(node, "boo");
node = add_to_c_tree(node, "coo");
print_c_tree(node);
return_c_tree(node,arr);
for (int i = 0; i < 7; ++i)
{
printf("%d:%s ..\n",i, arr[i]);
}
return 0;
}
这个问题的原因是我遇到了 return_c_tree() 函数的问题，该函数旨在模仿 K&R 的 print_c_tree() 函数的行为，除了递归调用自身直到 NULL ptr 并打印出节点的名称按字典顺序，这意味着将它们的名称添加到字符 ptrs 数组中并释放节点内存。
然而，我在上面运行时得到的输出是：
aoo
boo
coo
doo
foo
woo
yoo
0:aoo ..
1:(null) ..
2:boo ..
3:doo ..
4:foo ..
5:coo ..
6:(null) ..
这表明打印功能工作正常，但返回功能显然不是。令人困惑的是，如果在 return_c_tree() 中对 printf() 的调用未注释，则结果如下：
aoo
boo
coo
doo
foo
woo
yoo
arr+0:aoo
arr+1:boo
arr+2:coo
arr+3:doo
arr+4:foo
arr+5:woo
arr+6:yoo
0:aoo ..
1:(null) ..
2:boo ..
3:doo ..
4:foo ..
5:coo ..
6:(null) ..
这意味着它实际上确实以正确的顺序添加了字符串。我也尝试过不使用 c_inc 变量 -> 即只是在将数组传递给正确的节点之前递增数组，该节点从 return_c_tree() 中的 printf 产生相同的结果，但与 main 不同：
arr+-1:aoo
arr+-1:boo
arr+-1:coo
arr+-1:doo
arr+-1:foo
arr+-1:woo
arr+-1:yoo
0:foo ..
1:yoo ..
2:coo ..
3:(null) ..
4:(null) ..
5:(null) ..
6:(null) ..
我很困惑，所以如果有人可以提供帮助，我将不胜感激。我确定我只是在错误的地方增加它，但我不知道在哪里。
我以为我终于理解了指针，但显然没有。
最佳P