0

我有一个 BST 的插入函数，它还调用并检查节点是否平衡。如果不是，我在节点上调用旋转函数。这就是问题所在 -> 直到那时我的程序运行良好，但是，在添加该函数后，我的程序抛出了错误。我现在只写了 leftrotate 函数，因为我正在测试一个只需要左旋转的案例，因此现在的 rightrotate 现在没有问题。这是我的插入功能

 Tnode* insertnode(Tnode* root, int key)
 {
   if (root == NULL)
    {
      Tnode* child = (Tnode*)malloc(sizeof(Tnode));
      child->left = NULL;
      child->right = NULL;
      child->key = key;
      child->balance = 0;
      return child;
    }
    if (root->key < key)
    {
      root->right = insertnode(root->right,key);
    }
    else if (root->key >= key)
    {
      root->left = insertnode(root->left,key);
    }
    if (balance(root) > 1 || balance(root)  < -1)
    {
      if (balance(root) == -2)
      {
        *edit* root = leftrotate(root);
      }
      else
      {
        //rightrotate(root);
      }
    }
    return root;
  }

平衡的标准是这样的：一个节点的左子树和右子树的绝对差不能大于1。这是我的左旋转函数：

 *edit*Tnode* leftrotate(Tnode *root)
 {
   Tnode * temproot = root;
   root = root->right;
   root->left = temproot;
   temproot->right = NULL;
   return root; *edit*
 }

这是释放树的函数：

  void freetree(Tnode * root)
  {
    if(root == NULL)
    {
      return;
    }
    freetree(root->left);
    freetree(root->right);
    free(root);
    return;

但是，所有块都没有被释放，并且树似乎没有正确地平衡自己。这是 valgrind 报告：

==3704== HEAP SUMMARY:
==3704==     in use at exit: 192 bytes in 8 blocks
==3704==   total heap usage: 11 allocs, 3 frees, 808 bytes allocated
==3704==
==3704== LEAK SUMMARY:
==3704==    definitely lost: 96 bytes in 4 blocks
==3704==    indirectly lost: 96 bytes in 4 blocks
==3704==      possibly lost: 0 bytes in 0 blocks
==3704==    still reachable: 0 bytes in 0 blocks
==3704==         suppressed: 0 bytes in 0 blocks
==3704== Rerun with --leak-check=full to see details of leaked memory
==3704==
==3704== For counts of detected and suppressed errors, rerun with: -v
==3704== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

我究竟做错了什么 ？有小费吗？编辑：最小的主要，我打开的文件是一个二进制文件。'i' 是指插入指令。

      FILE *fp2 = fopen(argv[2],"rb");
      if (fp2 == NULL)
      {
        printf("%d\n",-1);
        return EXIT_FAILURE;
      }

      int key = 0;
      char placeh;
      Tnode * root = (Tnode*)malloc(sizeof(Tnode));
      fread(&root->key,sizeof(int),1,fp2);

      root->left = NULL;
      root->right = NULL;
      root->balance = 0;
      fread(&placeh,sizeof(char),1,fp2);
      while (1)
      {
        fread(&key,sizeof(int),1,fp2);
        fread(&placeh,sizeof(char),1,fp2);
        if (feof(fp2))
        {
          break;
        }
        if (placeh == 'i')
        {
          //printf("%d ",key);
          insertnode(root,key);
        }
      }
      printtree(root);
      freetree(root);
      fclose(fp2);
    }


    return EXIT_SUCCESS;
}
4

0 回答 0