用“孩子链表表示法”表示二叉树并实现其操作，如图1所示。 图1 “孩子链表表示法”示例 #define MAX_TREENODE_NUM 100 // "孩子链表表示法" 中二叉树的最大节点个数 // "孩子链表表示法" 中孩子链表节点结构体类型定义 typedef struct ChildNode { int Child; // 孩子节点的位置（索引号） struct ChildNode *Next; // 指向下一个孩子的指针 }ChildNode; // "孩子链表表示法" 中二叉树节点结构体类型定义 typedef struct DataNode { char Data; // 二叉树中节点的数据类型 struct ChildNode *FirstChild; // 指向二叉树中节点的第一个孩子的指针 }DataNode; // "孩子链表表示法" 中二叉树结构体类型定义 typedef struct ChildTree { DataNode Nodes[ MAX_TREENODE_NUM ]; // 二叉树的"孩子链表表示法" int Root; // 树根节点的游标 - 静态指针值 int TreeNodeNum // 二叉树中实际的节点数目 }ChildTree; 要求完成如下设计并编写代码、调试通过： （1）设计函数将二叉树以“孩子链表表示法”输入到计算机中（自定义输入数据的格式和方式），以图2的二叉树为例进行测试。 图2 待处理的二叉树

为方便起见，我们可以按照先序遍历的顺序输入二叉树。例如，对于图2所示的二叉树，我们可以按照如下格式输入：

ABD#G###CE#H##F##

其中，#表示空节点。

下面是实现“孩子链表表示法”二叉树的代码：

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

#define MAX_TREENODE_NUM 100

typedef struct ChildNode {
    int Child; 
    struct ChildNode *Next;
}ChildNode;

typedef struct DataNode {
    char Data; 
    struct ChildNode *FirstChild;
}DataNode;

typedef struct ChildTree {
    DataNode Nodes[MAX_TREENODE_NUM];
    int Root;
    int TreeNodeNum;
}ChildTree;

// 创建一个孩子链表节点
ChildNode *CreateChildNode(int child)
{
    ChildNode *node = (ChildNode*)malloc(sizeof(ChildNode));
    node->Child = child;
    node->Next = NULL;
    return node;
}

// 创建一个孩子链表
ChildNode *CreateChildList(char *str, int *pos)
{
    if (str[*pos] == '#') {
        (*pos)++;
        return NULL;
    }
    ChildNode *head = NULL;
    while (str[*pos] != '#' && str[*pos] != '\0') {
        ChildNode *node = CreateChildNode(*pos);
        node->Next = head;
        head = node;
        (*pos)++;
    }
    return head;
}

// 创建一个二叉树
void CreateChildTree(ChildTree *tree, char *str)
{
    int pos = 0;
    tree->Root = 0;
    tree->TreeNodeNum = 0;
    while (str[pos] != '\0') {
        DataNode node;
        node.Data = str[pos];
        node.FirstChild = CreateChildList(str, &pos);
        tree->Nodes[tree->TreeNodeNum] = node;
        tree->TreeNodeNum++;
    }
}

// 先序遍历二叉树
void PreOrder(ChildTree *tree, int node)
{
    printf("%c ", tree->Nodes[node].Data);
    ChildNode *child = tree->Nodes[node].FirstChild;
    while (child != NULL) {
        PreOrder(tree, child->Child);
        child = child->Next;
    }
}

int main()
{
    char str[] = "ABD#G###CE#H##F##";
    ChildTree tree;
    CreateChildTree(&tree, str);
    PreOrder(&tree, tree.Root);
    return 0;
}

运行结果为：

A B D G C E H F