使用二叉树

Question

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

typedef struct node_{
    int val;
    struct node_ *left;
    struct node_ *right;
}node;

node* insert(node* root,int val);
void inorder(node* root);
int main(void)
{
    int i;
    int item;
    node* root = NULL;

    srand(time(NULL));

    for( i = 0; i < 10; i++)
    {
        item = rand()%15;
        insert(root,item); 
    }

    inorder(root);

    return 0;    
}

node* insert(node* root,int val)
{
    if(root == NULL)
    {
        root = malloc(sizeof(node));
        if(root!= NULL)
        {
            (root)->val = val;
            (root)->left = NULL;
            (root)->right = NULL;
        }
        else 
            printf("%d not inserted. No memory available.\n",val);
    }
    else
    {
        if(val < (root)->val)
        {
            insert((root->left),val);
        }

        if(val>root->val)
        {
            insert(((root)->right),val);
        }
    }
}

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

我正在尝试创建一个二叉树并按顺序打印出值。然而，当我运行这段代码时，地址的 printf 打印出 nil 显然意味着我的树是空的，所以下面的 printf 和递归不会运行。我无法弄清楚我哪里出错了，任何建议或答案将不胜感激，因为我无法弄清楚为什么在调用 main 中的所有这些插入后根将为空。

Answer 1

在 main() 中，在声明和初始化根 (node* root = NULL;) 之后，您永远不会分配它。为了解决这个问题，您可能应该将 lin insert(root,item); 更改为 root = insert(root,item);.

另请注意，尽管 insert 被定义为 returning node *，但它没有 return 任何值。

Answer 2

您将 root 作为参数传递给 insert()（它表示它会 return 某些东西但没有）。在 insert 中，您 malloc 您的节点并将其分配给局部变量 root。您所做的任何事情都不会超出 insert 功能。

尝试 return 从 insert 获取一些东西，或者使用全局 root。

正如@JoshuaByer 在下面的评论中暗示的那样，另一种方法是使您的 insert 方法 "pass by reference" 以便它可以有效地修改传递给它的内容。

void insert(node** rootp,int val)
{
    if(*rootp == NULL)
    {
        *rootp = malloc(sizeof(node));
    }
    /* and so on */

如果您不明白这是什么意思，google "Pass by reference in C" 我相信您会得到一些有用的信息。

使用二叉树

Using a Binary Tree

c

binary-tree