6.2使用双亲-孩子链表表示法实现树的各算法，和树与二叉树的转换算法，写主函数测试。用C语言

以下是使用双亲-孩子链表表示法实现树的各算法，和树与二叉树的转换算法的代码，包括主函数测试： ```c #include <stdio.h> #include <stdlib.h> #define MAX_TREE_SIZE 100 // 树的最大结点数 #define MAX_QUEUE_SIZE 100 // 队列的最大容量 // 双亲-孩子链表结点结构体 typedef struct CTNode { int child; // 孩子结点的索引 struct CTNode *next; // 指向下一个孩子结点的指针 } CTNode, *ChildPtr; // 双亲-孩子链表头结点结构体 typedef struct { int data; // 结点数据 int parent; // 双亲结点的索引 ChildPtr firstChild; // 指向第一个孩子结点的指针 } CTBox; // 双亲-孩子链表树结构体 typedef struct { CTBox nodes[MAX_TREE_SIZE]; // 结点数组 int r, n; // 根结点的索引和结点数 } CTree; // 初始化双亲-孩子链表树 void InitTree(CTree *T) { int i; for (i = 0; i < MAX_TREE_SIZE; i++) { T->nodes[i].parent = -1; T->nodes[i].firstChild = NULL; } T->r = -1; T->n = 0; } // 向双亲-孩子链表树中插入结点 void InsertNode(CTree *T, int i, int j) { ChildPtr p = (ChildPtr) malloc(sizeof(CTNode)); p->child = j; p->next = T->nodes[i].firstChild; T->nodes[i].firstChild = p; T->nodes[j].parent = i; T->n++; } // 遍历双亲-孩子链表树 void TraverseTree(CTree *T) { int i, j; ChildPtr p; printf("Tree:\n"); for (i = 0; i < T->n; i++) { printf("%d: %d -> ", i, T->nodes[i].data); p = T->nodes[i].firstChild; while (p != NULL) { j = p->child; printf("%d -> ", T->nodes[j].data); p = p->next; } printf("NULL\n"); } } // 双亲-孩子链表树转换为二叉树 void CTreeToBiTree(CTree *T, int i, int *j, BiTree *p) { ChildPtr q; int k; q = T->nodes[i].firstChild; if (q == NULL) { *p = NULL; } else { CTreeToBiTree(T, q->child, &k, p); *j = k; while (q->next != NULL) { q = q->next; CTreeToBiTree(T, q->child, &k, &((*p)->rchild)); (*p)->rchild = (k == -1) ? NULL : (BiTree) k; } } } // 二叉树转换为双亲-孩子链表树 void BiTreeToCTree(BiTree T, int i, int *j, CTree *p) { if (T == NULL) { *j = -1; } else { p->nodes[i].data = T->data; p->nodes[i].parent = -1; (*j)++; BiTreeToCTree(T->lchild, *j, j, p); if (*j != -1) { InsertNode(p, i, *j); } BiTreeToCTree(T->rchild, *j, j, p); } } // 层序遍历二叉树 void LevelOrderTraverse(BiTree T) { BiTree Q[MAX_QUEUE_SIZE]; int front = 0, rear = 0; if (T != NULL) { Q[++rear] = T; } while (front != rear) { BiTree p = Q[++front]; printf("%d ", p->data); if (p->lchild != NULL) { Q[++rear] = p->lchild; } if (p->rchild != NULL) { Q[++rear] = p->rchild; } } printf("\n"); } int main() { CTree T; BiTree B; int j = -1; InitTree(&T); T.r = 0; T.n = 10; T.nodes[0].data = 0; T.nodes[1].data = 1; T.nodes[2].data = 2; T.nodes[3].data = 3; T.nodes[4].data = 4; T.nodes[5].data = 5; T.nodes[6].data = 6; T.nodes[7].data = 7; T.nodes[8].data = 8; T.nodes[9].data = 9; InsertNode(&T, 0, 1); InsertNode(&T, 0, 2); InsertNode(&T, 1, 3); InsertNode(&T, 1, 4); InsertNode(&T, 2, 5); InsertNode(&T, 3, 6); InsertNode(&T, 3, 7); InsertNode(&T, 5, 8); InsertNode(&T, 5, 9); TraverseTree(&T); CTreeToBiTree(&T, 0, &j, &B); printf("Binary Tree:\n"); LevelOrderTraverse(B); BiTreeToCTree(B, 0, &j, &T); TraverseTree(&T); return 0; } ``` 在该代码中，我们首先定义了双亲-孩子链表结点结构体 CTNode 和双亲-孩子链表头结点结构体 CTBox，然后定义了双亲-孩子链表树结构体 CTree。在 InitTree 函数中，我们将树中所有结点的双亲结点索引设置为 -1，孩子结点指针设置为 NULL，根结点的索引设置为 -1，结点数设置为 0。在 InsertNode 函数中，我们向树中插入一个孩子结点，并建立孩子结点与双亲结点之间的关系。在 TraverseTree 函数中，我们遍历整个树，输出每个结点的数据以及它的孩子结点。在 CTreeToBiTree 函数中，我们将双亲-孩子链表树转换为二叉树，首先遍历树的第一个孩子结点，得到它的索引 k，然后遍历它的兄弟结点，为每一个兄弟结点创建一个右孩子，并递归地将它的子树转换为二叉树。在 BiTreeToCTree 函数中，我们将二叉树转换为双亲-孩子链表树，首先为每个结点创建一个对应的双亲-孩子链表结点，并递归地将左子树和右子树插入到它们的双亲结点中。在 LevelOrderTraverse 函数中，我们使用队列实现层序遍历二叉树。最后，在主函数中，我们创建了一个双亲-孩子链表树，并向其中插入一些结点，然后遍历该树，将它转换为二叉树，输出二叉树，并将二叉树转换为双亲-孩子链表树，输出双亲-孩子链表树。