从数组创建并打印二叉树

Question

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

然后我想按顺序打印其元素(根、左、右)

以下代码可以编译，但没有给出输入(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)));
    }

}

Answer 1

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;
}

啊，您已经纠正了 @SteveFriedl 指出的 %c bug。

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

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() 函数显然没问题。