未在bst中创建根节点 [英] Root node is not being created in bst

问题描述

//以下代码不提供任何输出

//编码是否有任何缺陷。

 #include< stdio.h> 
 #include< conio.h> 
 #include< stdlib.h> 
 
 
 typedef  struct 节点
 {
  int  info; 
  struct 节点*左; 
  struct 节点*权利; 
}节点; 
 
  void  insert（node * root， int  item）
 {
 node * parent，* cur; 
 parent = NULL; 
 cur = root; 
  while （cur！= NULL）
 {
 parent = cur; 
  if （item< = cur-> info）
 cur = cur-> left; 
 其他 
 cur = cur-> right; 
} 
  if （root == NULL）
 {
 root-> info = item; 
 root-> left = NULL; 
 root-> right = NULL; 
} 
  else  
 {
 node * newNode =（int *）malloc（的sizeof （节点））; 
 newNode-> info = item; 
 newNode-> left = NULL; 
 newNode-> right = NULL; 
  if （item< parent-> info）
 parent-> left = newNode; 
  else  
 parent-> right = newNode; 
} 
} 
 
 
  int  main（）
 {
 < span class =code-keyword> int  a [] = { 5 ， 4  ， 6 ， 9 ， 21 ，< span class =code-digit> 13 ， 45 ， 2 }; 
  int  i; 
 node * root =（node *）malloc（ sizeof （node））; 
 root = NULL; 
 insert（root， 4 ）; 
 printf（ ％d，root-> info）; 
 getch（）; 
} 

解决方案

不，它完全按照你的要求去做。

只是你告诉它要做的就是垃圾，就是这样！ ：笑：



看看你的代码。

为什么你有的循环cur！= NULL 可以吗？之后你不用 cur 做任何事情！

你期望这段代码做什么？

< pre lang =c ++> if （root == NULL）
{
root-> info = item;
root-> left = NULL;
root-> right = NULL;
}

因为如果root为NULL，所有它 会崩溃！

我怀疑你需要考虑一下你想要做什么，也许先把它放在纸上，因为这看起来很混乱！

正如格里夫已经指出的那样，有几个你的代码中完全错误的东西，只要看一下就可以看到它们。让我们从您的主程序开始：

 node * root =（node *）malloc（ sizeof （节点） ））; 
 root = NULL; 
 insert（root， 4 ）; 
 

显然，你打算在第一行分配一个根节点，但只是为了测试目的，再次将root重置为NULL，在这种情况下，内存你刚刚分配了会丢失 - 内存泄漏。现在，您必须决定是否希望 insert 函数的用户始终自己分配根节点，或者是否要以NULL指针开始。我会选择第二种选择。所以抛出malloc线。



所以，我们决定在第一次调用 insert 函数时将为我们分配根节点。但它怎么能返回那个指针呢？在声明中

  void  insert（node * root， int  item）

您指定root作为按值传输的指针。这并没有让我们有机会将值返回给我们的调用者。为了解决这个问题，我们必须通过指向指针的指针传递根指针：

  void  insert（ node ** ppRoot， int  item）

现在我们可以在insert函数中分配一个根节点：

  void  insert（node ** ppRoot， int  item）
 {
 node * pRoot = * ppRoot; 
  if （pRoot == NULL）
 {
 * ppRoot = pRoot =（node *）malloc（ sizeof （node））; 
 pRoot-> item = item; 
 pRoot-> left = NULL; 
 pRoot-> right = NULL; 
} 

在主函数中，您现在可以通过以下方式调用 insert ：

 root = NULL; 
 insert（& root， 4 ）; 
 

还有一件事我会改变：插入函数中的父指针指向你必须链接新分配的节点节点。问题是您不知道是否将其链接到父节点的 left 或 right 指针。您通过再次将项目与父项的值进行比较来解决这个问题。更优雅的方法是使用指向链接必须放置的位置的指针，即（ left 或

 right 

）。

 node ** ppLink; 
 ... 
  while （cur！= NULL）
 {
  if （item< = cur-> info）
 ppLink =& cur-> left; 
  else  
 ppLink =& cur-> right; 
 cur = * ppLink; 
} 
 ... 
 {
 node * pNewNode =（node *）malloc（ sizeof （node）） ; 
 * ppLink = pNewNode; 
 ... 
 

知道了吗？



如你所见，指针指针的概念非常强大。以上解释只是为了让您走向正确的方向。它们不能解决代码中的所有问题。在任何情况下：了解如何使用调试器。这将成为你作为程序员最重要的工具！



祝你好运。

//The following code does not give any output
//Is there any flaw in its coding.

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


typedef struct Node
{
    int info;
    struct Node* left;
    struct Node* right;
}node;

void insert(node *root,int item)
{
    node *parent,*cur;
    parent=NULL;
    cur=root;
    while(cur!=NULL)
    {
        parent=cur;
        if(item<=cur->info)
        cur=cur->left;
        else
        cur=cur->right;
    }
    if(root==NULL)
    {
        root->info=item;
        root->left=NULL;
        root->right=NULL;
    }
    else
    {
        node *newNode=(int*)malloc(sizeof(node));
        newNode->info=item;
        newNode->left=NULL;
        newNode->right=NULL;
        if(item<parent->info)
        parent->left=newNode;
        else
        parent->right=newNode;
    }
}


int main()
{
    int a[]={5,4,6,9,21,13,45,2};
    int i;
    node *root=(node*)malloc(sizeof(node));
    root=NULL;
    insert(root,4);
    printf("%d",root->info);
    getch();
}

解决方案

No, it is doing exactly what you told it to do.
It's just that what you told it to do is rubbish, that's all! :laugh:

Look at your code.
Why do you have a loop for cur!=NULL at all? you don't do anything with cur after it!
What do you expect this code to do?

if(root==NULL)
{
    root->info=item;
    root->left=NULL;
    root->right=NULL;
}

Because all it will do is crash if root is NULL!
I suspect you need to think about what you are trying to do, and perhaps give it a go manually on pieces of paper first, because this looks very confused!

As Griff already pointed out there are a couple of things totally wrong in your code, and you can see them by just looking at it. Let's start with your main program:

node *root=(node*)malloc(sizeof(node));
root=NULL;
insert(root,4);

Obviously, you meant to allocate a root node in the first line, but then just for testing purposes reset root to NULL again, in which case the memory you just have allocated would be lost -- a memory leak. Now you have to decide whether you want the user of your insert function to always allocate the root node by himself, or whether you want to start with a root pointer that is NULL. I'd go for the second option. So throw that malloc line out.

So, we have decided that in the very first call the insert function is going to allocate the root node for us. But how can it return that pointer? In the declaration

void insert(node *root,int item)

you specified root as a pointer that is transferred by value. That doesn't give us a chance to return a value back to our caller. To remedy that we have to pass the root pointer via a pointer to a pointer:

void insert (node** ppRoot, int item)

And now we can allocate a root node inside the insert function:

void insert (node** ppRoot, int item)
{
  node* pRoot = *ppRoot;
  if (pRoot == NULL)
  {
    *ppRoot = pRoot = (node*) malloc (sizeof (node));
    pRoot->item = item;
    pRoot->left = NULL;
    pRoot->right = NULL;
  }

In your main function you would now call insert the following way:

root = NULL;
insert (&root, 4);

And there is one other thing that I would change: The parent pointer in your insert function points to the node to which you have to link your newly allocated node. The problem is just that you don't know whether to link it to the left or right pointer of the parent node. You solved that by comparing the item once again to the parent's value. A more elegant way is to use a pointer that point to the location into which the link has to be placed, i.e. (left or

right

).

node** ppLink;
...
while (cur != NULL)
{
  if (item <= cur->info)
    ppLink = &cur->left;
  else
    ppLink = &cur->right;
  cur = *ppLink;
}
...
{
  node* pNewNode = (node*) malloc (sizeof(node));
  *ppLink = pNewNode;
  ...

Got it?

As you see, the concept of pointers to pointers is very powerful. The above explanations were just meant to get you going into the right direction. They don't fix all the problems in your code. In any case: Learn how to use the debugger. That will become your most important tool as a programmer!

Good luck.

这篇关于未在bst中创建根节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！