无法打印二叉搜索树中的元素

Question

我的代码没有打印二叉搜索树的元素：

//x is the element to be inserted
//structure of program
 typedef struct BST
  {
  int info;
  struct  BST *left;
//pointer to left node

 struct BST *right;
//pointer to right node

 }
 bst;
//global root variable

bst *root;
void insert(int x)
{
    bst *ptr,*sptr=root;
    ptr=(bst*)malloc(sizeof(bst));
    ptr->info=x;
    if(root==NULL)
    {
        ptr->left=ptr->right=NULL;
        root=ptr;
    }
    while(sptr!=NULL)
    {
        if(x<sptr->info)
        {
            sptr=sptr->left;
        }
        else
            sptr=sptr->right;
    }
    sptr=ptr;
}

编辑：

 //following is the show function

   void show()
   {
    bst *ptr=root;
    while(ptr!=NULL)
    {

    //it will print untill the ptr is null

      printf("%d",ptr->info);
      ptr=ptr->left;
      ptr=ptr->right;
    }
  }

Answer 1

root 的值从何而来？你没有在任何地方传递价值？此外，当我们不知道类型 bst.

的设计时很难提供帮助

看来你的想法是对的。创建一个节点，并给它一些数据。如果根为空，则新值是 BST 的根。之后，您继续使用标准 BST 行为在根的左子树或右子树中找到第一个空节点。最后，当你到达终点时，你继续将最后一个节点插入到适当的位置。

void insert(int x)
{
    bst *ptr, *sptr=root; //<-- the value right here?
    ptr = malloc(sizeof(bst));
    ptr->info = x;
    if(root == NULL)
    {
        ptr->left=ptr->right=NULL;
        root=ptr;
    }

    while(sptr!=NULL)
    {
        if(x<sptr->info)
        {
            sptr=sptr->left;
        }
        else
            sptr=sptr->right;
    }
    sptr=ptr; // <-- What is this line trying to do?
}

但是，你更新的树去哪儿了？

因为在 C 中一切都是按值传递的，所以您运行遇到了在离开此函数后看不到更新的树的问题。您需要继续将函数更改为 return a bst* 类型，并在整个函数期间保持根节点。现在第一行代码 (*sptr = root) 更有意义了！最后，您没有将 ptr 的左右字段设置为 NULL。这意味着您跳过了 if 语句。

bst* insert(int x, bst *root)
{
    bst *ptr, *sptr=root;
    ptr = malloc(sizeof(bst));

    ptr->left = NULL;
    ptr->right = NULL;

    ptr->info = x;
    if(root == NULL)
    {
        ptr->left=ptr->right=NULL;
        root=ptr;
        return root;
    }

    while(sptr!=NULL)
    {
        if(x<sptr->info)
        {
            sptr=sptr->left;
        }
        else
            sptr=sptr->right;
    }
    sptr=ptr;
    return root;
}

下一个函数呢？

我也刚开始看这个。我不习惯c中的全局变量，所以我会继续进行两个修改。让我们使其递归，并传入根的值而不是使用全局值。

void show(bst *root)
{
    if(root == NULL){
         return;
    }
    printf("%d",root->info);
    show(root->left);
    show(root->right);
 }

这将接受一些值，递归地求解树，并在到达每个节点时打印。因此，它将打印根节点（如果存在），然后在打印右子树之前打印整个左子树。

最后看看你的主

我添加了局部变量 root，因此您必须在主函数之外删除名为 root 的全局变量。我还将它的值设置为 null 以便您的第一个插入将正确触发。

int main()
{
  int i,n,x;
  bst *root = NULL; //<-- I added this line of code to remove the global
  puts("Enter number of elements");
  scanf("%d",&x);

  for(i=0;i<x;i++)
  {
      puts("Enter elements");
      scanf("%d",&n);
      root = insert(n, root);
  }
show(root);
return 0;
}

希望对您有所帮助！

无法打印二叉搜索树中的元素

Unable to print elements in binary search tree

c

binary-search-tree

data-structures