C – 使用后序遍历释放二叉树的内存

我想使用后序遍历删除二叉树 。 这意味着应首先删除树的左侧部分， 然后删除右侧的树，然后在后面的第二个函数中删除整个树并释放内存 。 我不允许更改函数的参数，只能使用它的内部：

#include  #include  #include  #include "telefonbuch.h" static inline bstree * create_node(unsigned long phone, char * name) { bstree * newNode = (bstree *) malloc(sizeof(bstree)); newNode->key.phone = phone; strcpy(newNode->key.name, name); newNode->left = NULL; newNode->right = NULL; return newNode; } void bst_insert_node(bstree * bst, unsigned long phone, char * name) { if (bst == NULL) { return; } if (bst->key.phone > phone) { if (bst->left == NULL) { bst->left = create_node(phone, name); return; } bst_insert_node(bst->left, phone, name); } else { if (bst->right == NULL) { bst->right = create_node(phone, name); return; } bst_insert_node(bst->right, phone, name); } } bst_node * find_node(bstree* bst, unsigned long phone) { if (bst == NULL) { return NULL; } if(bst->key.phone > phone) { return find_node(bst->left, phone); } else if (bst->key.phone right, phone); } return &(bst->key); } void bst_in_order_walk_node(bst_node* node) { } void bst_in_order_walk(bstree* bst) { int temp = 0; int level; while(temp key.phone, bst->key.name); if (bst->left != NULL) { print_tree(bst->left, level + 1); } if (bst->right != NULL) { print_tree(bst->right, level + 1); } } void bst_free_subtree(bst_node* node) { …what goes here?… } void bst_free_tree(bstree* bst) { if(bst==NULL) return; bst_free_tree(bst->left); printf("Deleting %d node.\n",bst->key); free(bst); bst_free_tree(bst->right); } 

以下是结构定义：

 typedef struct _bst_node { char name[60]; unsigned long phone; } bst_node; typedef struct _bstree { bst_node key; struct _bstree * left; struct _bstree * right; } bstree; 

你能帮我完成/更正我的代码吗？

Answer 1

你有：

 void bst_free_tree(bstree* bst) { if(bst==NULL) return; bst_free_tree(bst->left); printf("Deleting %d node.\n",bst->key); free(bst); bst_free_tree(bst->right); } 

这将删除当前节点“按顺序”，并在释放后访问释放的内存。 不好！

你需要一个密切的关系：

 void bst_free_tree(bstree* bst) { if (bst == NULL) return; bst_free_tree(bst->left); bst_free_tree(bst->right); printf("Deleting %d node.\n", bst->key); free(bst); } 

这将遍历并释放左子树，然后释放右子树，最后释放当前节点。

我认为不需要bst_free_subtree()函数; bst_free_tree()函数可以很好地释放子树。