创建二叉树的指针麻烦

我从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 
}

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

来源

2012-04-28 Wasiq Kashkari

您是否尝试过使用调试器？ – huon 2012-04-28 02:17:41

yeap我有，我知道错误发生的地方，但老老实实地使用递归方法意味着它真的很难调试，因为有这么多的指针指针等指针 – 2012-04-28 02:22:27

实际上，我真的想知道为什么我不能插入＆newn->右到我的insertRecursivePreorder函数 – 2012-04-28 02:23:45

直接问题可能是在指针上调用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-28 02:39:58 huon

OMG非常感谢！弄清楚了！！对不起，我只有第二年软件学生：P – 2012-04-28 03:04:59

问题是：您从来没有分配给'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-28 12:37:01 wildplasser

创建二叉树的指针麻烦

回答

相关问题