算法竞赛模板

父亲表示法是树最简单、空间效率最高的存储结构。请设计将基于父亲表示法的树转换为孩子兄弟表示法，即二叉链表结构的树的算法。在此规定任一结点的子结点按索引编号的递增序从头向尾链接。

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

/* 孩子兄弟表示法结构定义 */
typedef int TElemSet;
typedef struct BinaryTreeNode *BinaryTree;
struct BinaryTreeNode {
    TElemSet data;             /* 数据元素 */
    BinaryTree first_child;    /* 第一个子结点 */
    BinaryTree next_sibling;   /* 下一个兄弟结点 */
};
/* 孩子兄弟表示法结构定义 结束 */

/* 父亲表示法结构定义 */
typedef int Position;
#define NIL -1
typedef struct TreeNode *Tree;
struct TreeNode {
    TElemSet data;    /* 数据元素 */
    Position parent;  /* 父结点位置 */
};
/* 父亲表示法结构定义 结束 */

BinaryTree ConvertTree(Tree tree, int n);

void Visit(BinaryTree tree)
{
    printf("%d\n", tree->data);
}

void PreOrder(BinaryTree tree)
{
    if (tree != NULL) { /* 空树不做处理，直接返回 */
        Visit(tree);                  /* 先访问结点tree */
        PreOrder(tree->first_child);  /* 接下来访问tree所有子孙结点 */
        PreOrder(tree->next_sibling); /* 最后访问tree后序的兄弟结点及其子孙 */
    }
}

int main(void)
{
    int n, i;
    Tree tree;
    BinaryTree bin_tree;
    
    scanf("%d\n", &n);
    tree = (Tree)malloc(sizeof(struct TreeNode) * n);
    for (i=0; i<n; i++) {
        scanf("%d %d\n", &tree[i].data, &tree[i].parent);
    }
    bin_tree = ConvertTree(tree, n);
    PreOrder(bin_tree);
    
    return 0;
}
/* 你的代码将被嵌在这里 */

就是链式前向星啊，不过是c语言版
这里手动malloc的内存还不会自动释放

BinaryTree ConvertTree(Tree tree, int n) {
    // BinaryTree rt = malloc(sizeof(*rt));
    BinaryTree *arr = calloc(n, sizeof *arr);
    // BinaryTree root = new tmp;
    int root;

    for (int i = 0; i < n; ++i) {
        arr[i] = malloc(sizeof *arr[i]);
        if (!arr[i]) {
            return NULL;
        }
        arr[i]->data = tree[i].data;
        arr[i]->first_child = NULL;
        arr[i]->next_sibling = NULL;
    }

    for (int i = n - 1; i >= 0; i--) {
        int fa = tree[i].parent;
        if (fa == -1) {
            root = i;
        } else {
            arr[i]->next_sibling = arr[fa]->first_child;
            arr[fa]->first_child = arr[i];
        }
    }
    return arr[root];
}