时间戳

首页 > 解决方案 > 从数组创建和打印二叉树

c - 从数组创建和打印二叉树

问题描述

我正在尝试使用函数中定义的数组创建二叉树。

然后我想按顺序打印它的元素（根，左，右）

以下代码编译但没有输入（NULL）

请告诉我我哪里错了

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

struct BST *in(int data, struct BST *p1, struct BST *p2);
struct BST *create_BST(int a[], int i, int size);
void inorder(struct BST *tree);
int  main(void){
    struct BST *root;
    int a[]={7, 10, 14, 5, 9, 11, 4, 13, 6};


    root=create_BST(a,0,9);

    printf("\nPrinting Tree:\t");
    inorder(root);
    return 0;

}
void inorder(struct BST *root){
    if(root!=NULL){
        inorder(root->left);
        printf("%d",root->data);
        inorder(root->right);
    }
}

struct BST *in(int data, struct BST *p1, struct BST *p2){
    struct BST *t;
    t=(struct BST*)malloc(sizeof(struct BST));
    t->data=data;
    t->left=p1;
    t->left=p2;
    return t;
}

struct BST *create_BST(int a[], int i, int size){

    if(i>=size){
        return NULL;
    }else{
        return(in(a[i],create_BST(a,2*i + 1,size),
            create_BST(a,2*i + 2,size)));
    }

}

标签： cdata-structuresbinary-tree

解决方案

create_BST()功能不正确。对于初学者来说，它只是在树中插入一个值。但是还有一些其他的错误。

struct BST *in(int data, struct BST *p1, struct BST *p2){
    struct BST *t;
    t=(struct BST*)malloc(sizeof(struct BST));
    t->data=data;
    t->left=p1;
    t->left=p2;    // <-- HERE, should be t->right=p2;
    return t;
}

啊，你已经纠正了%c@SteveFriedl 指出的错误。

我修改了创建过程以遍历树，在叶节点上寻找正确的插入点。

struct BST *insert( struct BST *root, int value )
{
    if ( root == NULL )
    {
        // Tree is empty, make it
        root = in( value, NULL, NULL );
        printf( "Inserted %d at the root (%p)\n", value, root );
    }
    else
    {
        // Find the location to insert the node
        int  inserted = 0;
        struct BST *ptr = root;

        // Keep walking the tree until we're inserted
        while ( !inserted )
        {
            // Does it hang off the left?
            if ( value <= ptr->data )
            {
                if ( ptr->left == NULL )
                {
                    ptr->left = in( value, NULL, NULL );
                    printf( "Inserted %d as a left-branch of %d(%p)\n", value, ptr->data, ptr );
                    inserted = 1;
                }
                else
                {
                    // branch left, cannot make a leaf here
                    ptr = ptr->left;
                }
            }
            else  // Hangs off the right  ( value > ptr->data )
            {
                if ( ptr->right == NULL )
                {
                    ptr->right = in( value, NULL, NULL );
                    printf( "Inserted %d as a right-branch of %d(%p)\n", value, ptr->data, ptr );
                    inserted = 1;
                }
                else
                {
                    // branch right, cannot make a leaf here
                    ptr = ptr->right;
                }
            }
        }
    }

    return root;
}

然后简单地迭代您的值数组，将每个轮流插入到树中。

struct BST *create_BST(int *values, int count)
{
    struct BST *tree = NULL;

    if ( values != NULL && count > 0 )
    {
        for( int i=0; i<count; i++ )
            tree = insert( tree, values[ i ] );
    }

    return tree;
}

显然您main()需要致电：

root=create_BST(a,9);

这给了我：

$ ./bst
Inserted 7 at the root (0x5568b65f32a0)
Inserted 10 as a right-branch of 7(0x5568b65f32a0)
Inserted 14 as a right-branch of 10(0x5568b65f36d0)
Inserted 5 as a left-branch of 7(0x5568b65f32a0)
Inserted 9 as a left-branch of 10(0x5568b65f36d0)
Inserted 11 as a left-branch of 14(0x5568b65f36f0)
Inserted 4 as a left-branch of 5(0x5568b65f3710)
Inserted 13 as a right-branch of 11(0x5568b65f3750)
Inserted 6 as a right-branch of 5(0x5568b65f3710)

Printing Tree:  4 5 6 7 9 10 11 13 14

inorder()功能显然没问题。

推荐阅读