C语言 指针创建二叉树时出现问题

Question

我正在从 c 中的位字符串创建一个二叉树，即 1100100 创建一个树：

  1
 / 
1   1

我

决定使用递归函数来构建这棵树，但是我不断收到错误调试断言失败...表达式 ： CrtIsValidHeapPointer(pUserData(

这是我的代码片段

typedef
struct Node {
  char key;
  struct Node *left;
  struct Node *right; 
} Node;
char string[1000];
int i = 0;
void insertRecursivePreorder(Node **node)
{
    Node* parent = *node;
    if(string[i] == '0')
    {
        parent = NULL;
        i++;
    }
    else
    {
        Node *newn = (Node*)malloc(sizeof(Node));
        newn->key = string[i];
        parent = newn;
        i++;
        insertRecursivePreorder(&newn->left); //errors occur here
        insertRecursivePreorder(&newn->right); //errors occur here
        free(newn);
        free(parent);
    }
}
int main(void)
{
    void printTree(Node* node);
    Node* root = NULL;
    scanf("%s", string);
    insertRecursivePreorder(&root);
    //... do other junk
}

我想知道为什么会出现此错误以及我可以做些什么来修复它。

Answer 1

眼前的问题可能是在指针上调用free两次。在 insertRecursivePreorder 中，您将parent设置为 newn ，然后对两者调用free。例如，以下程序失败(但如果您注释掉free(..)之一，则可以正常工作(：

#include <stdlib.h>
int main() {
  int *a = malloc(sizeof(int)),
      *b = a;
  free(a);
  free(b);
  return 0;
}

但是，这里的逻辑存在几个问题。只有在完全完成指针操作后，才应调用free，因此，如果您稍后使用树，则无法在构造树时释放它。您应该创建第二个函数 recursiveDestroyTree ，该函数在树上遍历并调用free(自下而上！

而且，您可能想要*node = newn而不是parent = newn，因为后者是唯一实际修改node 。

(你也可以改变你的函数来返回一个Node *指针，然后去：

root = insertRecursivePreorder();

和

newn->left = insertRecursivePreorder();
newn->right = insertRecursivePreorder();

而不是试图跟踪指向指针等的指针(

(此外，在风格上，使用全局变量通常是不好的做法，因此您可以让insertRecursivePreorder获取int i参数并char * string并使用它们而不是全局变量。

Answer 2

问题是：你从来没有在'insertRecursivePreorder'中分配给双指针，所以root总是保持NULL。

#include <stdio.h>
#include <stdlib.h>
typedef
struct Node {
  char key;
  struct Node *left;
  struct Node *right;
} Node;
        /* slightly changed the syntax for the str
        ** ; now '.' indicates a NULL pointer, values represent themselves.
        */
char *string = "12..3.." ;
/* Removed the global index 'i' */
void printTree(Node* node, int level);
unsigned insertRecursivePreorder(Node **pp, char *str);
unsigned insertRecursivePreorder(Node **pp, char *str)
{
    unsigned pos =1;
    if (!*str) { *pp = NULL; return 0; } /* safeguard for end of string */
    if (*str == '.') { *pp = NULL; return pos; }
    *pp  = malloc(sizeof **pp);
    (*pp)->key = *str;
    pos += insertRecursivePreorder(&(*pp)->left, str+pos);
    pos += insertRecursivePreorder(&(*pp)->right, str+pos);
    return pos;
}
void printTree(Node* node, int level)
{
unsigned pos,len;
len = level> 0 ? level : -level;
    for (pos =0; pos < len; pos++) putchar (' ');
    if (!level) printf ("Root=");
    else if (level<0) printf ("Left=");
    else printf ("Right=");
    if (!node) { printf( "Nulln" ); return; }
    printf("Key=%cn", node->key );
    printTree(node->left, -(len+1) ) ;
    printTree(node->right, len+1) ;
}
int main(void)
{   
    Node *root = NULL;
    unsigned result = 0;
    result = insertRecursivePreorder(&root, string);
    printf( "Result=%un", result);
    printTree(root, 0);
    return 0; printTree(root, 0);
}

输出：

Result=7
Root=Key=1
 Left=Key=2
  Left=Null
  Right=Null
 Right=Key=3
  Left=Null
  Right=Null