5、建立树的孩子兄弟链表存储结构，求树的深度。 要求：自上而下输入树中每条边（例如#A,AB,AC,BD,##），不要转换成二叉树输入。 用C语言实现

### 创建树的孩子兄弟链表表示法 为了创建树的孩子兄弟链表表示法，定义节点结构体 `CSNode` 来存储数据以及指向第一个孩子和下一个兄弟的指针。 ```c #include <stdio.h> #include <stdlib.h> typedef struct CSNode { int data; struct CSNode *firstchild, *nextsibling; } CSNode; // 函数用于创建新节点 CSNode* createNode(int value) { CSNode* newNode = (CSNode*)malloc(sizeof(CSNode)); newNode->data = value; newNode->firstchild = NULL; newNode->nextsibling = NULL; return newNode; } ``` 通过上述代码片段实现了基本的数据结构构建[^1]。接下来展示如何基于输入来构造这样的树形结构： ```c void addSibling(CSNode* parent, int siblingValue); void addChild(CSNode* parent, int childValue); int main() { // 假设我们有一个简单的树结构作为例子 CSNode* root = createNode(1); // 创建根节点 addChild(root, 2); // 添加孩子的操作 addChild(root, 3); addSibling(root->firstchild, 4); // 给root的第一个孩子添加兄弟 addSibling(root->firstchild->nextsibling, 5); // 更多的操作可以根据具体需求继续扩展... } // 向指定父节点添加新的子节点 void addChild(CSNode* parent, int childValue) { if (!parent || !parent->firstchild) { parent->firstchild = createNode(childValue); } else { CSNode* currentChild = parent->firstchild; while (currentChild->nextsibling != NULL) { currentChild = currentChild->nextsibling; } currentChild->nextsibling = createNode(childValue); } } // 向现有节点后面追加同级的新节点（即成为该节点的兄弟） void addSibling(CSNode* node, int siblingValue) { CSNode* newSibling = createNode(siblingValue); CSNode* lastSibling = node; while (lastSibling->nextsibling != NULL) { lastSibling = lastSibling->nextsibling; } lastSibling->nextsibling = newSibling; } ``` 这段程序展示了怎样动态地向已经存在的节点添加孩子或兄弟节点的方法。 ### 计算树的最大深度 对于给定的一棵树，可以通过递归方式轻松找到它的最大深度。这里提供了一个函数用来计算任意形态下的树的高度/深度: ```c int getHeight(CSNode* tree) { if (tree == NULL) return 0; // 如果当前节点为空，则返回高度为0 int firstChildHeight = getHeight(tree->firstchild)+1; // 获取首个孩子所在分支的最大高度并加上一层 int nextSiblingHeight = getHeight(tree->nextsibling); // 查找相邻兄弟所在的分支的最大高度 return (firstChildHeight > nextSiblingHeight ? firstChildHeight : nextSiblingHeight); } ``` 此方法遵循了非空情况下取两者较大值的原则，并且当遇到叶子节点时自然终止递归过程[^2]。