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 参数并使用它们代替全局变量。)