为什么输出会变成无穷大

Question

这是我用来在 BST.And 中添加的代码15=] 输出进入无穷大。

    void add(){
      struct node* temp=(struct node *) malloc(sizeof(struct node));
      struct node* current=root;
      printf("\nEnter the data:\n");
      scanf("%d",&temp->data);
      while(current->left!=NULL && current->right!=NULL){
            parent=current;
        if(temp->data > parent->data){
            current=current->right;
        }
        else{
            current=current->left;
        }

      }
      if(temp->data > parent->data){
            parent->right=temp;
            parent->left=NULL;
        }
        else{
            parent->left=temp;
            parent->right=temp;
        }
    }

    void preorder(struct node* node)
    {
         if (node == NULL)
              return;

         /* first print data of node */
         printf("%d ", node->data);

         /* then recur on left subtree */
         preorder(node->left);

         /* now recur on right subtree */
         preorder(node->right);
    }

Answer 1

函数 add 有未定义的行为。

对于初学者来说，root 最初可以等于 NULL。所以你可能不会使用这种方法

  struct node* current=root;
  //...
  while(current->left!=NULL && current->right!=NULL){

因为试图使用空指针访问内存。

其次这个循环

  while(current->left!=NULL && current->right!=NULL){
        parent=current;

不处理仅包含一个不等于 NULL 的子节点的节点。

此外，您没有将创建的节点 temp 左右两侧的数据成员设置为 NULL。

这些陈述中有一个错字

        parent->left=temp;
        parent->right=temp;

所以函数定义无效。

并且该函数应该只做一件事：将一个节点添加到树中。它不应提示用户输入一些数据。

考虑到对根节点使用全局变量不是一个好主意。

尽管如此，这里有一个使用您的方法的演示程序。我称这种方法为 Java-approach（在 C 中函数 add 可以写得更简单）

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

struct node
{
    int data;
    struct node *left, *right;
};

struct node *root;

_Bool add( int data )
{
    struct node *new_node = malloc( sizeof( struct node ) );
    _Bool success = new_node != NULL;

    if ( success )
    {
        new_node->data  = data;
        new_node->left  = NULL;
        new_node->right = NULL;

        if ( root == NULL )
        {
            root = new_node;
        }
        else
        {
            for ( struct node *current = root; ; )
            {
                struct node *parent = current;

                if ( data < current->data )
                {
                    current = current->left;
                    if ( current == NULL )
                    {
                        parent->left = new_node;
                        break;
                    }
                }
                else
                {
                    current = current->right;
                    if ( current == NULL )
                    {
                        parent->right = new_node;
                        break;
                    }
                }
            }
        }
    }

    return success;
}

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

int main(void) 
{
    srand( ( unsigned int )time( NULL ) );

    const int N = 10;

    for ( int i = 0; i < N; i++ ) add( rand() % N );

    preorder( root );

    putchar( '\n' );

    return 0;
}

程序输出可能看起来像

4 0 3 2 1 0 1 2 5 8

下面有一个演示程序，展示了如何使用 C 方法编写函数 add。在程序中全局变量 root 被删除并替换为局部变量 root。

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

struct node
{
    int data;
    struct node *left, *right;
};

_Bool add( struct node **root, int data )
{
    struct node *new_node = malloc( sizeof( struct node ) );
    _Bool success = new_node != NULL;

    if ( success )
    {
        new_node->data  = data;
        new_node->left  = NULL;
        new_node->right = NULL;

        while ( *root != NULL )
        {
            if ( data < ( *root )->data ) root = &( *root )->left;
            else root = &( *root )->right;
        }

        *root = new_node;
    }

    return success;
}

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

int main(void) 
{
    struct node *root = NULL;

    srand( ( unsigned int )time( NULL ) );

    const int N = 10;

    for ( int i = 0; i < N; i++ ) add( &root, rand() % N );

    preorder( root );

    putchar( '\n' );

    return 0;
}

现在研究并比较函数 add 的两个实现。

Answer 2

你必须这样重写你的添加方法，

void add()
    {
        int data;
        printf("\nEnter the data:\n");
        scanf("%d",data);
        root = insert_rec(root, data);
    }
struct node* insert_rec(struct node* current, int data)
    {


        if(current == NULL)
        {
            struct node* temp=(struct node *) malloc(sizeof(struct node));
            temp->data = data;
            current = temp;
            return current;
        }
        else
        {
            if(current->data > data)
            {
                current->left = insert_rec(current->left, data);
            }
            else
            {
                current->right = insert_rec(current->right, data);
            }
        }
        return current;
    }

这是BST插入的递归方式。希望这可能有所帮助:)

为什么输出会变成无穷大

Why is the output going into infinity

c

struct

binary-search-tree

data-structures

preorder