有人可以告诉我为什么我在这段代码中使用它的前序和后序创建的二叉树没有以所需的方式创建吗？

Question

我编写了这段代码来使用给定的前序和中序遍历创建二叉树。根据我的试运行，没有问题，树应该正确创建。但事实并非如此。我打印了树的顺序只是为了检查树是否已创建。但打印的不是中序，而是后序。经过进一步调查，我发现树本身没有正确创建，这就是错误出现的原因。创建的根的右侧部分没有任何内容。但根据试运行来看，没有问题。有人可以帮我找出我的错误吗？

示例输入:A乙deFCGHj我kd乙FeAGC我jHk

输出:dfebgljkhca

     #include <stdio.h>

typedef struct Node
{
    int data;
    struct node *left;
    struct node *right;
}node;
typedef node *tree;
tree root=NULL;

char pre[11];
char in[11];

static int i;

void create( tree temp, int start_left, int end_left, int start_right, int end_right )
{
    if ( start_left <= end_left )
    {
        temp->left= (tree) malloc(sizeof( node ));
        temp=temp->left;
        temp->left=NULL;
        temp->right=NULL;
        int j;
        for ( j=start_left; j<=end_left; j++)
        {
            if ( pre[i]==in[j] )
            {
                temp->data=pre[i];
                break;
            }
        }
        i++;
        create( temp, start_left, j-1, j+1, end_left );

    }
    if ( start_right <= end_right )
    {
        temp->right= (tree) malloc(sizeof( node ));
        temp=temp->right;
        temp->left=NULL;
        temp->right=NULL;
        int j;
        for ( j=start_right; j<=end_right; j++)
        {
            if ( pre[i]==in [j] )
            {
           temp->data=pre[i];
                break;
            }
        }
        i++;
        create( temp, start_right, j-1, j+1, end_right );
    }
    return ;
}

void inorder_print(tree temp)
{
    if ( temp!=NULL )
    {
        inorder_print(temp->left);
        printf("%c",temp->data);
        inorder_print(temp->right);
    }
}

int main()
{

    for( i=0; i<11; i++)
    {
        scanf("%c", &pre[i]);
        fflush(stdin);
    }

    for( i=0; i<11; i++)
    {
        scanf("%c", &in[i]);
        fflush(stdin);
    }
    int j;
    for( j=0; j<11; j++)
    {
        if( pre[0]==in[j] )
        {
            root= (tree) malloc(sizeof( node ));
            root->data=pre[0];
            root->left=NULL;
            root->right=NULL;
            break;
        }
    }
    i=1;
    create( root, 0, j-1, j+1, 10);
    inorder_print(root);
    return 0;
}

Answer 1

更一般化的东西怎么样？我的建议有以下输出:

prorder:
a a b b d c c d e e f f g g h h j j l k k l 
inorder:
a a b b c c d d e e f f g g h h j j k k l l 
   [a]                            
 +--+-----+                    
[a]      [b]                   
       +--+-----------+        
      [b]            [d]       
                +-----+-----+
               [c]         [e]
             +--+--+     +--+-----+
            [c]   [d]   [e]      [f]
                               +--+-----+
                              [f]      [g]
                                     +--+-----+
                                    [g]      [h]
                                           +--+-----+
                                          [h]      [j]
                                                 +--+-----------+
                                                [j]            [l]
                                                          +-----+
                                                         [k]
                                                       +--+--+ 
                                                      [k]   [l]

代码是:

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

typedef struct      s_tree
{
    void            *content;
    size_t          content_size;
    struct s_tree   *left;
    struct s_tree   *right;
}                   t_tree;

/*
** Tree content casted to given type
*/

#define TCONT(tree, t_type) ((t_type)((tree)->content))

/*
** Helpers
*/

void    *ft_memdup(void const *ptr, size_t size)
{
    void            *result;

    result = (void*)malloc(size);
    if (result == NULL)
        return (NULL);
    memcpy(result, ptr, size);
    return (result);
}

t_tree  *ft_tree_new(void const *content, size_t content_size)
{
    t_tree  *result;

    result = (t_tree*)malloc(sizeof(t_tree));
    if (result == NULL)
        return (NULL);
    result->left = NULL;
    result->right = NULL;
    if (content == NULL)
    {
        result->content = NULL;
        result->content_size = 0;
    }
    else
    {
        result->content = ft_memdup(content, content_size);
        result->content_size = content_size;
    }
    return (result);    
}

void    ft_tree_add(
            t_tree **root,
            t_tree *new_branch,
            int (*cmp)(void*, void*))
{
    if (*root == NULL)
        *root = new_branch;
    else
    {
        if (cmp((*root)->content, new_branch->content) >= 0)
            ft_tree_add(&(*root)->left, new_branch, cmp);
        else
            ft_tree_add(&(*root)->right, new_branch, cmp);
    }
}

void    ft_tree_map(t_tree *root, void (*f)(void*), char *map)
{
    int     i;

    if (root != NULL)
        for (i = 0; map[i]; i++)
        {
            switch (map[i])
            {
                case 'R':
                    f(root->content);
                    break;
                case 'r':
                    ft_tree_map(root->right, f, map);
                    break;
                case 'l':
                    ft_tree_map(root->left, f, map);
                    break;
            }
        }
}

/*
** Print tree function
*/

int _print_t(t_tree *tree, int is_left, int offset, int depth, char s[50][256])
{
    char    b[50];
    int     width = 3;
    int     i;

    if (!tree)
        return 0;

    sprintf(b, "[%s]", TCONT(tree, char*));

    int left  = _print_t(tree->left,  1, offset,                depth + 1, s);
    int right = _print_t(tree->right, 0, offset + left + width, depth + 1, s);

    for (i = 0; i < width; i++)
        s[2 * depth][offset + left + i] = b[i];

    if (depth && is_left)
    {
        for (i = 0; i < width + right; i++)
            s[2 * depth - 1][offset + left + width/2 + i] = '-';
        s[2 * depth - 1][offset + left + width/2] = '+';
        s[2 * depth - 1][offset + left + width + right + width/2] = '+';
    } else if (depth && !is_left)
    {
        for (int i = 0; i < left + width; i++)
            s[2 * depth - 1][offset - width/2 + i] = '-';

        s[2 * depth - 1][offset + left + width/2] = '+';
        s[2 * depth - 1][offset - width/2 - 1] = '+';
    }
    return left + width + right;
}

void print_tree(t_tree *tree)
{
    char s[50][256];

    for (int i = 0; i < 50; i++)
        sprintf(s[i], "%100s", " ");

    _print_t(tree, 0, 0, 0, s);

    for (int i = 0; i < 50; i++)
        printf("%s\n", s[i]);
}

//end of print tree function

void    print_str(char *str)
{
    printf("%s ", str);
}

int     main()
{
    t_tree  *root;
    char    input[] = "abdefcghjlkdbfeagcljhk";
    char    tmp[2];
    int     i;

    tmp[1] = 0;
    root = NULL;
    for (i = 0; input[i]; i++)
    {
        tmp[0] = input[i];
        ft_tree_add(&root,
            ft_tree_new(tmp, strlen(tmp) + 10),
            (int (*)(void*, void*))(&strcmp));
    }

    //Preorder
    printf("preorder:\n");
    ft_tree_map(root, (void (*)(void*))(&print_str), "Rlr");
    printf("\n");

    //Inorder
    printf("inorder:\n");
    ft_tree_map(root, (void (*)(void*))(&print_str), "lRr");
    printf("\n");

    print_tree(root);
}

如果您想更改插入方式，请制作自己的比较函数，并将 &strcmp 更改为 &your_function。