algorithm - 递归创建给定深度的完整二叉树

给定树的深度，返回该深度的完整二叉树。
树结构定义为blow：

typedef int Item;
// Define binary tree node
typedef struct node {
    struct node *lchild;
    Item item;
    struct node *rchild;
} BTNode, *BTree;

我使用一个名为CreateFullBTree的函数递归地创建二叉树功能如下：

BTree CreateFullBTree(int depth)
{
    static int tag = 1;
    BTNode *node = CreateNode();
    node -> item = tag;
    tag++;

    printf("%d, %p\n",node->item, node);
    if (depth == 1) return node;
    node -> lchild = CreateFullBTree(depth-1);
    node -> rchild = CreateFullBTree(depth-1);
    return node;
}

CreateNode函数是：

BTNode* CreateNode()
{
    BTNode *node = malloc(sizeof(node));
    node -> lchild = NULL;
    node -> rchild = NULL;
    return node;
}

主要功能：

int main(int argc, const char *argv[])
{
    int depth;
    scanf("%d", &depth);
    BTree pTree = CreateFullBTree(depth);
    preOrder(pTree);
    return 0;
}

在main函数中，我调用createfullbtree得到一个完整的二叉树，然后调用preorder函数输出每个节点的标记字段，以检查树是否正确创建。预订单功能是：

void preOrder(BTree tree)
{
    if (tree) {
        printf("%d\n", tree->item);
        preOrder(tree->lchild);
        preOrder(tree->rchild);
    }
    return;
}

每次调用createfullbtree时，都会创建并标记一个新节点。然后我们检查当前深度是否达到1，这意味着我们到达了二叉树的底部如果是的话，我们就返回那个新创建的节点，什么也不做。如果不是，则节点可以有左和右子节点，然后我们让node->lchild = CreateFullBTree(depth-1)和node->rchild = CreateFullBTree(depth-1)。
但是该算法并没有达到预期的效果，当以3作为树的深度时，preOrder函数的输出很奇怪：1 2 5 6 7 7 7 4 7 7 5 6 7 7 7，似乎有些节点的lchild和rchild指针指向了错误的节点。但我找不到他们混乱的原因。
有人能帮我一下吗，谢谢。

最佳答案

您没有为节点分配足够的空间：sizeof(BTNode)，而不是sizeof(node)。