創建二叉樹的指針麻煩

我從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

創建二叉樹的指針麻煩

回答

相關問題