0

在下面的代码中，我正在使用插入函数创建一个二叉树，并尝试使用遵循中序遍历逻辑的中序函数显示插入的元素。当我运行它时，数字被插入但是当我尝试中序时函数（输入 3），程序继续下一个输入，不显示任何内容。我想可能有一个逻辑错误。请帮我清除它。提前致谢...

#include<stdio.h>
#include<stdlib.h>

int i;
typedef struct ll
{
  int data;
  struct ll *left;
  struct ll *right;
} node;

node *root1=NULL; // the root node

void insert(node *root,int n)
{
  if(root==NULL) //for the first(root) node
  {
    root=(node *)malloc(sizeof(node));
    root->data=n;
    root->right=NULL;
    root->left=NULL;
  }
  else
  {
    if(n<(root->data))
    {
      root->left=(node *)malloc(sizeof(node));
      insert(root->left,n);
    }
    else if(n>(root->data))
    {
      root->right=(node *)malloc(sizeof(node));
      insert(root->right,n);
    }
    else
    {
      root->data=n;
    }
  }
}

void inorder(node *root)
{
  if(root!=NULL)
  {
    inorder(root->left);
    printf("%d  ",root->data);
    inorder(root->right);
  }
}

main()
{
  int n,choice=1;
  while(choice!=0)
  {
    printf("Enter choice--- 1 for insert, 3 for inorder and 0 for exit\n");
    scanf("%d",&choice);
    switch(choice)
    {
      case 1:
        printf("Enter number to be inserted\n");
        scanf("%d",&n);
        insert(root1,n);
        break;
      case 3:
        inorder(root1);
        break;
      default:
        break;
    }
  }
}
4

3 回答 3

1

您insert接受指向 a 的指针node，该指针位于函数范围内。返回后insert，调用它的根保持不变。你得到一个泄漏。

如果您希望更改insert在其外部可见，请首先更改其签名

void insert(node **root,int n)

并这样称呼它：

void insert(&root1, n);

这样，它将修改root1而不是它的副本。

作为一个经验法则，如果一个函数需要修改某些东西，它应该被传递一个指向它的指针。你的函数需要修改 a node*，所以它应该被传递 a node**。

编辑

正如 unwind 指出的那样，您还可以返回根作为更新它的一种方式

root1 = insert(root1, n);

当然，这仅在您需要修改一个对象时才有效。

于 2013-10-31T09:45:41.850 回答
0

传递对的引用，node *以便insert()在分配新节点时对其进行适当更新。

此外，在您的insert()函数中，不要在移动到下面的树时进行分配。如果您分配，那么您的代码会尝试检查该节点上的值并再次继续，这是不正确的。

更新的代码将是：

void insert(node **root_ptr,int n)
    {
    if(root==NULL) //for the first(root) node
    {
        root=(node *)malloc(sizeof(node));
        root->data=n;
        root->right=NULL;
        root->left=NULL;
        *root_ptr = root;
    }
    else
    {
        if(n<(root->data))
        {
        //root->left=(node *)malloc(sizeof(node));
        insert(&root->left,n);
        }
        else if(n>(root->data))
        {
        //root->right=(node *)malloc(sizeof(node));
        insert(&root->right,n);
        }
        else
        {
        root->data=n;
        }
    }
    }

从main()称它为insert(&root1,n);

于 2013-10-31T09:50:27.560 回答
0

您的分配代码已关闭，root1将始终保留，NULL因为 malloc 结果仅分配给局部变量。将 root 作为指向指针的指针传入。

此外，您无条件地左右 malloc，即使那里可能已经有数据，您应该立即调用 insert 并让被调用的 insert 像 root 一样处理 malloc。当然，再次使用指向指针的指针。

最后你else root->data = n没有任何意义，它已经是n。而且我认为您不希望树中有重复项？如果你这样做，你需要更改你的代码。

于 2013-10-31T09:50:23.997 回答