Распечатать двоичное дерево

Question

У меня есть 2 функции для создания дерева

struct tree *createNewNode(int data){
    struct tree *newNode = malloc(sizeof(struct tree));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct tree *insert(struct tree *root, int data){
    if(root == NULL) root = createNewNode(data);
    else if(data < root->data) root->left = insert(root->left, data);
    else root->right = insert(root->right, data);
    return root;
}

и функция печати дерева

void inorder(struct tree *root){
    if(root==NULL) printf("empty\n");
    inorder(root->left);
    printf("%d", root->data);
    inorder(root->right);
}

но каждый раз, когда вызывается inorder, он печатает только "пустой" (оператор if). Похоже, мои функции по созданию дерева не работают, или это функция печати не работает. Я просто хочу напечатать все значения, которые есть в дереве.

Answer 1

Функции insert() и createNode() в порядке.

Функция inorder() печатает empty для каждого нулевого указателя в дереве. Затем происходит сбой, вероятно, потому что он пытается повторить вызов с root->left, даже если root равно нулю. Вы, вероятно, должны просто вернуться, когда root равно нулю.

Все еще трудно определить, какой узел идет с каким. Может быть, вам следует использовать код, похожий на этот:

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

struct tree
{
    int          data;
    struct tree *left;
    struct tree *right;
};

static struct tree *createNewNode(int data)
{
    struct tree *newNode = malloc(sizeof(struct tree));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

static struct tree *insert(struct tree *root, int data)
{
    if (root == NULL)
        root = createNewNode(data);
    else if (data < root->data)
        root->left = insert(root->left, data);
    else
        root->right = insert(root->right, data);
    return root;
}

static void pr_indent(int level)
{
    for (int i = 0; i < level; i++)
        printf("    ");
}

static void inorder(struct tree *root, int level)
{
    if (root != NULL)
    {
        inorder(root->left, level + 1);
        pr_indent(level);
        printf("%d\n", root->data);
        inorder(root->right, level + 1);
    }
}

static void print_inorder(const char *tag, struct tree *root)
{
    printf("%s: \n", tag);
    inorder(root, 0);
    putchar('\n');
}

static void release(struct tree *node)
{
    if (node != NULL)
    {
        release(node->left);
        release(node->right);
        free(node);
    }
}

int main(void)
{
    struct tree *root = NULL;
    int values[] = { 37, 24, 30,36, 72, 57, 32, 62 };
    enum { NUM_VALUES = sizeof(values) / sizeof(values[0]) };

    for (int i = 0; i < NUM_VALUES; i++)
    {
        root = insert(root, values[i]);
        char tag[20];
        snprintf(tag, sizeof(tag), "%d: After %d", i + 1, values[i]);
        print_inorder(tag, root);
    }

    release(root);
    return 0;
}

Пример вывода:

1: After 37: 
37

2: After 24: 
    24
37

3: After 30: 
    24
        30
37

4: After 36: 
    24
        30
            36
37

5: After 72: 
    24
        30
            36
37
    72

6: After 57: 
    24
        30
            36
37
        57
    72

7: After 32: 
    24
        30
                32
            36
37
        57
    72

8: After 62: 
    24
        30
                32
            36
37
        57
            62
    72