C-使用后序遍历释放二叉树的内存 [英] C - freeing memory of a binary tree using post-order traversal

问题描述

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

  #include< stdio.h> 
 #include< stdlib.h> 
 #include< string.h> 
 #include telefonbuch.h 
 
静态内联bstree * create_node（无符号长电话，字符*名称）
 {
 bstree * newNode =（bstree *） malloc（sizeof（bstree））; 
 
 newNode-> key.phone =电话; 
 strcpy（newNode-> key.name，名称）; 
 newNode-> left = NULL; 
 newNode-> right = NULL; 
 
返回newNode; 
} 
 
 void bst_insert_node（bstree * bst，无符号长电话，char *名称）
 {
 if（bst == NULL）
 {
回报； 
} 
 
 if（bst-> key.phone> phone）
 {
 if（bst-> left == NULL）
 {
 bst-> left = create_node（电话，名称）; 
的回报； 
} 
 
 bst_insert_node（bst-> left，phone，name）; 
} 
 else 
 {
 if（bst-> right == NULL）
 {
 bst-> create = node（phone，name ）; 
的回报； 
} 
 
 bst_insert_node（bst->右侧，电话，名称）； 
 
} 
} 
 
 bst_node * find_node（bstree * bst，长号无符号电话）{
 if（bst == NULL）
 {
返回NULL; 
} 
 
 if（bst-> key.phone> phone）
 {
 return find_node（bst-> left，phone）; 
} 
 else if（bst-> key.phone< phone）
 {
 return find_node（bst-> 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级别； 
 
 while（temp< level）
 {
 printf（-）; 
 ++ temp; 
} 
 
 printf（（％ld-％s）\n，bst-> 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 *节点）{
 
…这里是什么？…
 
} 
 
 void bst_free_tree（bstree * bst）{
 if（bst == NULL）
 return; 
 bst_free_tree（bst->左）; 
 printf（正在删除％d个节点。\n，bst->键）; 
 free（bst）; 
 bst_free_tree（bst-> right）; 
} 
  

以下是结构定义：

  typedef struct _bst_node {
 char name [60]; 
个未签名的长电话； 
} bst_node; 
 
 typedef结构_bstree {
 bst_node键； 
 struct _bstree *左； 
 struct _bstree *正确； 
} bstree; 
  

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

解决方案

您有：

  void bst_free_tree（bstree * bst）{
 if（bst == NULL）
返回; 
 bst_free_tree（bst->左）; 
 printf（正在删除％d个节点。\n，bst->键）; 
 free（bst）; 
 bst_free_tree（bst-> right）; 
} 
  

这将按顺序删除当前节点，并访问释放的内存释放之后。不好！<​​/ p>

您需要亲密关系：

  void bst_free_tree （bstree * bst）
 {
如果（bst == NULL）
返回; 
 bst_free_tree（bst->左）; 
 bst_free_tree（bst-> right）; 
 printf（正在删除％d个节点。\n，bst->键）； 
 free（bst）; 
} 
  

此方法先遍历并释放左子树，然后释放右子树，然后最终释放当前节点。

我看不到需要 bst_free_subtree（）函数; bst_free_tree（）函数同样可以很好地释放子树。

I want to remove a binary tree using post-order traversal. Meaning the left part of the tree should be removed first then the right one then remove the whole tree and free memory in a second function that follows after. I'm not allowed to changed the arguments of the function and can only play with the inside of it:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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 < phone)
  {
      return find_node(bst->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 < level)
   {
       printf("-");
       ++temp;
   }

   printf(" (%ld-%s)\n", bst->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);
}  

Here are the structure definitions:

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;

Could you help me finish/correct my code?

解决方案

You have:

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);
}

This deletes the current node 'in-order', and accesses the freed memory after freeing it. Not good!

You need a close relation:

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);
}  

This traverses and releases the left sub-tree, then the right sub-tree, and then finally releases the current node.

I don't see a need for the bst_free_subtree() function; the bst_free_tree() function frees sub-trees equally well.

这篇关于C-使用后序遍历释放二叉树的内存的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！