1

我正在从 c 中的位串创建二叉树。即 1100100 创建一棵树：

  1
 / \
1   1

我决定使用递归函数来构建这棵树，但是我不断收到错误 Debug assertion failed... Expression : 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
}

我想知道为什么会出现这个错误以及我能做些什么来解决它。

4

2 回答 2

1

直接的问题很可能是free两次调用指针。在insertRecursivePreorder中，您设置parent为newn，然后同时调用free两者。例如，以下程序失败（但如果您注释掉其中一个free(..)s 则有效）：

#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参数并使用它们而不是全局变量。）

于 2012-04-28T02:39:58.403 回答
0

问题是：你从来没有分配给'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( "Null\n" ); return; }
    printf("Key=%c\n", 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=%u\n", 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
于 2012-04-28T12:37:01.950 回答