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

Question

给定树深度depth，返回该深度的完整二叉树。
树结构定义如下:

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函数输出每个节点的tag字段来检查树是否正确创建。 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 4 6 7 5 6 7 7 ，似乎某些节点的 lchild 和 rchild 指针指向了错误的节点。但是我找不到它们乱七八糟的原因。

谁能帮我解决这个问题，谢谢。

Answer 1

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