text: /*=============================
   * 树的孩子链表(带双亲)的存储表示
   =============================*/
  
  #include "CTree.h"
  
  /*
   * 初始化
   *
   * 构造空树。
   */
  Status InitTree(CTree* T) {
      if(T == NULL) {
          return ERROR;
      }
      
      T->n = 0;
      
      // 所有数据清零
      memset(T->nodes, 0, sizeof(T->nodes));
      
      return OK;
  }
  
  /*
   * 销毁
   *
   * 释放树所占内存。
   *
   *【注】
   * 与置空操作是一致的
   */
  Status DestroyTree(CTree* T) {
      // 无需销毁，使用置空就可以
      return ERROR;
  }
  
  /*
   * 置空
   *
   * 清理树中的数据，使其成为空树。
   */
  Status ClearTree(CTree* T) {
      int k;
      ChildPtr p, q;
      
      if(T == NULL) {
          return ERROR;
      }
      
      // 释放孩子结点占用的空间
      for(k = T->r; k != (T->r + T->n) % MAX_TREE_SIZE; k = (k + 1) % MAX_TREE_SIZE) {
          p = T->nodes[k].firstchild;
          
          while(p != NULL) {
              q = p;
              p = p->next;
              free(q);
          }
      }
      
      // 将元素数量归零即可
      T->n = 0;
      
      // 所有数据清零
      memset(T->nodes, 0, sizeof(T->nodes));
      
      return OK;
  }
  
  /*
   * 创建
   *
   * 按照预设的定义来创建树。
   * 这里约定使用【层序序列】来创建树。
   *
   *
   *【备注】
   *
   * 教材中默认从控制台读取数据。
   * 这里为了方便测试，避免每次运行都手动输入数据，
   * 因而允许选择从预设的文件path中读取测试数据。
   *
   * 如果需要从控制台读取数据，则path为NULL或者为空串，
   * 如果需要从文件中读取数据，则需要在path中填写文件名信息。
   */
  Status CreateTree(CTree* T, char* path) {
      FILE* fp;
      int readFromConsole;    // 是否从控制台读取数据
      
      // 如果没有文件路径信息，则从控制台读取输入
      readFromConsole = path == NULL || strcmp(path, "") == 0;
      
      if(readFromConsole) {
          printf("请输入树的元素信息，对于空结点，使用^代替...\n");
          Create(T, NULL);
      } else {
          // 打开文件，准备读取测试数据
          fp = fopen(path, "r");
          if(fp == NULL) {
              return ERROR;
          }
          Create(T, fp);
          fclose(fp);
      }
      
      return OK;
  }
  
  /*
   * 判空
   *
   * 判断树是否为空树。
   */
  Status TreeEmpty(CTree T) {
      return T.n == 0 ? TRUE : FALSE;
  }
  
  /*
   * 树深
   *
   * 返回树的深度（层数）。
   */
  int TreeDepth(CTree T) {
      int k, level;
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          return 0;
      }
      
      /*
       * 将k初始化为最后一个结点的位置
       * 由于树的结点按层序存储，故最后存储的结点必定位于最大层
       */
      k = (T.r + T.n - 1) % MAX_TREE_SIZE;
      level = 0;
      
      do {
          level++;
          k = T.nodes[k].parent;
      } while(k != -1);
      
      return level;
  }
  
  /*
   * 取值
   *
   * 返回树中指定结点的值。
   */
  TElemType Value(CTree T, TElemType e) {
      int p;
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          return '\0';
      }
      
      // 获取结点e的索引
      p = EIndex(T, e);
      
      // 如果没有找到元素e
      if(p == -1) {
          return '\0';
      } else {
          return T.nodes[p].data;
      }
  }
  
  /*
   * 赋值
   *
   * 为树指定的结点赋值。
   */
  Status Assign(CTree* T, TElemType e, TElemType value) {
      int p;
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(*T)) {
          return ERROR;
      }
      
      // 获取结点e的索引
      p = EIndex(*T, e);
      
      // 如果没有找到元素e
      if(p == -1) {
          return ERROR;
      } else {
          // 进行赋值
          T->nodes[p].data = value;
          return OK;
      }
  }
  
  /*
   * 根
   *
   * 返回树的根结点。
   */
  TElemType Root(CTree T) {
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          return '\0';
      }
      
      return T.nodes[T.r].data;
  }
  
  /*
   * 双亲
   *
   * 返回树中结点e的双亲结点。
   */
  TElemType Parent(CTree T, TElemType e) {
      int p, parent;
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          return '\0';
      }
      
      // 获取结点e的索引
      p = EIndex(T, e);
      
      // 如果没有找到元素e
      if(p == -1) {
          return '\0';
      } else {
          parent = T.nodes[p].parent;
          
          // 根结点无双亲
          if(parent == -1) {
              return '\0';
          } else {
              return T.nodes[parent].data;
          }
      }
  }
  
  /*
   * 孩子数量
   *
   * 返回树T中结点e的孩子数量。
   */
  int ChildCount(CTree T, TElemType e) {
      int p, count;
      ChildPtr r;
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          return -1;
      }
      
      // 获取结点e的索引
      p = EIndex(T, e);
      // 结点e不存在
      if(p == -1) {
          return -1;
      }
      
      r = T.nodes[p].firstchild;
      count = 0;
      
      // 统计结点e的孩子数量
      while(r != NULL) {
          count++;
          r = r->next;
      }
      
      return count;
  }
  
  /*
   * 孩子
   *
   * 返回树中结点e的第i个孩子。
   */
  TElemType Child(CTree T, TElemType e, int i) {
      int p;
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          return '\0';
      }
      
      // i的范围越界
      if(i < 1 || i > MAX_CHILD_COUNT) {
          return '\0';
      }
      
      // 获取结点e的第i个孩子索引
      p = CIndex(T, e, i);
      // 结点e第i个孩子不存在
      if(p == -1) {
          return '\0';
      }
      
      return T.nodes[p].data;
  }
  
  /*
   * 左兄弟
   *
   * 返回树中结点e的左兄弟结点。
   *
   *【注】
   * 由于树的结点可能会包含多个孩子，
   * 因此这里的左兄弟特指左边紧邻该结点的兄弟。
   */
  TElemType LeftSibling(CTree T, TElemType e) {
      int p, ls;
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          return '\0';
      }
      
      // 获取结点e的索引
      p = EIndex(T, e);
      // 结点e不存在
      if(p == -1) {
          return '\0';
      }
      
      // 假设存在左兄弟
      ls = (p - 1 + MAX_TREE_SIZE) % MAX_TREE_SIZE;
      
      // 如果该结点有效，且与结点e的双亲相同，说明它是兄弟
      if(ls != p && T.nodes[ls].data != '\0' && T.nodes[ls].parent == T.nodes[p].parent) {
          return T.nodes[ls].data;
      }
      
      return '\0';
  }
  
  /*
   * 右兄弟
   *
   * 返回树中结点e的右兄弟结点。
   *
   *【注】
   * 由于树的结点可能会包含多个孩子，
   * 因此这里的右兄弟特指右边紧邻该结点的兄弟。
   */
  TElemType RightSibling(CTree T, TElemType e) {
      int p, rs;
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          return '\0';
      }
      
      // 获取结点e的索引
      p = EIndex(T, e);
      // 结点e不存在
      if(p == -1) {
          return '\0';
      }
      
      // 假设存在右兄弟
      rs = (p + 1) % MAX_TREE_SIZE;
      
      // 如果该结点有效，且与结点e的双亲相同，说明它是兄弟
      if(rs != p && T.nodes[rs].data != '\0' && T.nodes[rs].parent == T.nodes[p].parent) {
          return T.nodes[rs].data;
      }
      
      return '\0';
  }
  
  /*
   * 插入
   *
   * 将树c插入为树T中p结点的第i个孩子。
   */
  Status InsertChild(CTree* T, TElemType p, int i, CTree c) {
      Pos pt[MAX_TREE_SIZE], pc[MAX_TREE_SIZE];
      int pIndex;
      int lastChild, bound;
      int level;
      int m, n, k;
      int tCur, cCur;
      
      CTree R;
      int tParent[MAX_TREE_SIZE], cParent[MAX_TREE_SIZE];
      int x, y, z;
      
      ChildPtr cp, s;
      int count;
      
      // 如果树为空树则无需继续计算
      if(TreeEmpty(*T) || TreeEmpty(c)) {
          return ERROR;
      }
      
      // i的范围过于小
      if(i < 1) {
          return ERROR;
      }
      
      // 获取结点p的索引
      pIndex = EIndex(*T, p);
      
      // 如果p结点不存在，则返回错误提示
      if(pIndex == -1) {
          return ERROR;
      }
      
      // 计算T中结点的位置信息
      getPos(*T, pt);
      
      // 结点p最后一个孩子的索引
      lastChild = pt[pIndex].lastChild;
      
      // i的范围过大
      if(lastChild != -1 && i > pt[lastChild].childIndex + 1) {
          return ERROR;
      }
      
      if(i == 1) {
          // 结点p本身是第一个孩子
          if(pt[pIndex].childIndex == 1) {
              bound = -1;
          } else {
              // 从p的左兄弟起，向左查找
              for(k = (pIndex - 1) % MAX_TREE_SIZE; pt[k].lastChild == -1 && pt[k].childIndex != 1; k = (k - 1) % MAX_TREE_SIZE) {
                  // 查找右边界的父结点的索引
              }
              
              // 已经遍历到该层第一个结点，但该结点仍然没有孩子
              if(pt[k].lastChild == -1) {
                  bound = -1;
              } else {
                  bound = pt[k].lastChild;    // k结点最后一个孩子的索引
              }
          }
      } else {
          // 结点p没有孩子
          if(lastChild == -1) {
              return ERROR;
          } else {
              for(k = pt[pIndex].lastChild; pt[k].childIndex != i - 1; k = (k - 1) % MAX_TREE_SIZE) {
                  // 查找插入位置的前一个孩子的索引
              }
              bound = k;
          }
      }
      
      level = pt[pIndex].row + 1;   // 待插入的树的根结点所在的行
      
      // 计算c中结点的位置信息
      getPos(c, pc);
      // 处理新插入的树中各元素的行数
      for(k = c.r; k != (c.r + c.n) % MAX_TREE_SIZE; k = (k + 1) % MAX_TREE_SIZE) {
          pc[k].row += level - 1;
      }
      
      // tCur指向第level行的第一个结点
      for(tCur = pIndex; tCur != (T->r + T->n) % MAX_TREE_SIZE; tCur = (tCur + 1) % MAX_TREE_SIZE) {
          if(pt[tCur].row == level) {
              break;
          }
      }
      
      // cCur指向树c中的根结点，该根结点也应当插入到树T中的level行
      cCur = c.r;
      
      while(tCur != (T->r + T->n) % MAX_TREE_SIZE && cCur != (c.r + c.n) % MAX_TREE_SIZE) {
          // 跳过树T右界的前半部分
          if(bound != -1) {
              tCur = (bound + 1) % MAX_TREE_SIZE;
          }
          
          if(bound == -1) {
              m = 0;
          } else {
              m = pt[bound].col;
          }
          
          n = 0;
          
          // 将c插入到T的中间
          while(cCur != (c.r + c.n) % MAX_TREE_SIZE && pc[cCur].row == level) {
              // 改变列
              
              pc[cCur].col += m;
              n++;
              
              cCur++;
          }
          
          // 处理T的后半部分
          while(tCur != (T->r + T->n) % MAX_TREE_SIZE && pt[tCur].row == level) {
              
              pt[tCur].col += n;
              
              tCur++;
          }
          
          // 计算下一层的边界
          if(bound != -1) {
              // 从bound起，向左查找
              for(k = bound; pt[k].lastChild == -1 && pt[k].childIndex != 1; k = (k - 1) % MAX_TREE_SIZE) {
                  // 查找右边界的父结点的索引
              }
              
              // 已经遍历到该层第一个结点，但该结点仍然没有孩子
              if(pt[k].lastChild == -1) {
                  bound = -1;
              } else {
                  bound = pt[k].lastChild;    // k结点最后一个孩子的索引
              }
          }
          
          level++;
      }
      
      // 检验pos信息
  //    printPos(*T, pt);
  //    printPos(c, pc);
      
      InitTree(&R);
      
      R.r = T->r;
      n = 0;
      
      x = T->r;   // 遍历T的游标
      y = c.r;    // 遍历c的游标
      z = R.r;    // 遍历R的游标
      
      while(x != (T->r + T->n) % MAX_TREE_SIZE && y != (c.r + c.n) % MAX_TREE_SIZE) {
          if(pt[x].row < pc[y].row || (pt[x].row == pc[y].row && pt[x].col < pc[y].col)) {
              
              // 记录结点x的新位置
              tParent[x] = z;
              
              // 有效元素放到新位置上
              R.nodes[z] = T->nodes[x];
              
              if(R.nodes[z].parent != -1) {
                  // 更新父结点位置
                  R.nodes[z].parent = tParent[R.nodes[z].parent];
                  
                  // 指向父结点的第一个孩子
                  cp = R.nodes[R.nodes[z].parent].firstchild;
                  
                  // 如果当前结点不是第一个孩子，则需要查询正确的位置
                  if(pt[x].childIndex != 1) {
                      for(count = 1; count < pt[x].childIndex; count++) {
                          cp = cp->next;
                      }
                  }
                  
                  /*
                   * 更新当前结点在孩子链表中的位置
                   *
                   * 注：此处的更新会使其位置变大，故需要避免覆盖后面的元素值，下面的分支中以此类推
                   */
                  cp->child = z;
              }
              
              x = (x + 1) % MAX_TREE_SIZE;
          } else if(pt[x].row > pc[y].row || (pt[x].row == pc[y].row && pt[x].col > pc[y].col)) {
              // 记录结点y的新位置
              cParent[y] = z;
              
              // 有效元素放到新位置上
              R.nodes[z] = c.nodes[y];
              
              if(R.nodes[z].parent != -1) {
                  // 更新父结点位置
                  R.nodes[z].parent = cParent[R.nodes[z].parent];
                  
                  // 指向父结点的第一个孩子
                  cp = R.nodes[R.nodes[z].parent].firstchild;
                  
                  // 如果当前结点不是第一个孩子，则需要查询正确的位置
                  if(pc[y].childIndex != 1) {
                      for(count = 1; count < pc[y].childIndex; count++) {
                          cp = cp->next;
                      }
                  }
                  
                  // 更新当前结点在孩子链表中的位置
                  cp->child = z;
              } else {
                  // 将两棵树连到一起，即树c的根结点的父结点为p
                  R.nodes[z].parent = tParent[pIndex];
                  
                  // 包装当前结点
                  s = (ChildPtr) malloc(sizeof(CTNode));
                  s->child = z;
                  
                  // 指向该结点的父结点的首个孩子
                  cp = R.nodes[R.nodes[z].parent].firstchild;
                  
                  if(cp == NULL || i == 1) {
                      s->next = R.nodes[R.nodes[z].parent].firstchild;
                      R.nodes[R.nodes[z].parent].firstchild = s;
                  } else {
                      // 计数
                      count = 1;
                      
                      // 查找第i-1个结点
                      while(cp != NULL && count < i - 1) {
                          count++;
                          cp = cp->next;
                      }
                      
                      s->next = cp->next;
                      cp->next = s;
                  }
              }
              
              y = (y + 1) % MAX_TREE_SIZE;
          }
          
          z = (z + 1) % MAX_TREE_SIZE;
          n++;
      }
      
      while(x != (T->r + T->n) % MAX_TREE_SIZE) {
          // 记录结点k的新位置
          tParent[x] = z;
          
          // 有效元素放到新位置上
          R.nodes[z] = T->nodes[x];
          
          if(R.nodes[z].parent != -1) {
              // 更新父结点位置
              R.nodes[z].parent = tParent[R.nodes[z].parent];
              
              // 指向父结点的首个孩子
              cp = R.nodes[R.nodes[z].parent].firstchild;
              
              // 如果当前结点不是第一个孩子，则需要查询正确的位置
              if(pt[x].childIndex != 1) {
                  for(count = 1; count < pt[x].childIndex; count++) {
                      cp = cp->next;
                  }
              }
              
              // 更新当前结点在孩子链表中的位置
              cp->child = z;
          }
          
          x = (x + 1) % MAX_TREE_SIZE;
          z = (z + 1) % MAX_TREE_SIZE;
          n++;
      }
      
      while(y != (c.r + c.n) % MAX_TREE_SIZE) {
          // 记录结点k的新位置
          cParent[y] = z;
          
          // 有效元素放到新位置上
          R.nodes[z] = c.nodes[y];
          
          if(R.nodes[z].parent != -1) {
              // 更新父结点位置
              R.nodes[z].parent = cParent[R.nodes[z].parent];
              
              // 指向父结点的首个孩子
              cp = R.nodes[R.nodes[z].parent].firstchild;
              
              // 如果当前结点不是第一个孩子，则需要查询正确的位置
              if(pc[y].childIndex != 1) {
                  for(count = 1; count < pc[y].childIndex; count++) {
                      cp = cp->next;
                  }
              }
              
              // 更新当前结点在孩子链表中的位置
              cp->child = z;
          } else {
              // 将两棵树连到一起，即树c的根结点的父结点为p
              R.nodes[z].parent = tParent[pIndex];
              
              // 包装当前结点
              s = (ChildPtr) malloc(sizeof(CTNode));
              s->child = z;
              
              // 指向该结点的父结点的首个孩子
              cp = R.nodes[R.nodes[z].parent].firstchild;
              
              if(cp == NULL || i == 1) {
                  s->next = R.nodes[R.nodes[z].parent].firstchild;
                  R.nodes[R.nodes[z].parent].firstchild = s;
              } else {
                  // 计数
                  count = 1;
                  
                  // 查找第i-1个结点
                  while(cp != NULL && count < i - 1) {
                      count++;
                      cp = cp->next;
                  }
                  
                  s->next = cp->next;
                  cp->next = s;
              }
          }
          
          y = (y + 1) % MAX_TREE_SIZE;
          z = (z + 1) % MAX_TREE_SIZE;
          n++;
      }
      
      R.n = n;
      *T = R;
      
      return OK;
  }
  
  /*
   * 删除
   *
   * 删除树T中p结点的第i个孩子。
   */
  Status DeleteChild(CTree* T, TElemType p, int i) {
      LinkQueue Q;
      QElemType e;    // 队列元素指示结点的位置
      
      int index;
      int k, m, n;
      
      CTree R;
      int parent[MAX_TREE_SIZE];
      ChildPtr cp, q, s;
      
      // 如果待删除的树为空树则无需继续计算
      if(TreeEmpty(*T)) {
          return ERROR;
      }
      
      // i的范围越界（初步判断）
      if(i < 1 || i > MAX_CHILD_COUNT) {
          return ERROR;
      }
      
      // 获取结点p的第i个孩子索引
      index = CIndex(*T, p, i);
      
      // 如果待删除结点不存在，则返回错误提示
      if(index == -1) {
          return ERROR;
      }
      
      // 指向当前结点的父结点的第一个孩子
      cp = T->nodes[T->nodes[index].parent].firstchild;
      
      // 在父结点中找到了当前孩子并移除它
      if(cp->child==index) {
          T->nodes[T->nodes[index].parent].firstchild = cp->next;
      } else {
          // 在父结点中查找当前孩子并移除它（一定能找到）
          while(cp != NULL && cp->child!=index) {
              s = cp;
              cp = cp->next;
          }
          
          s->next = cp->next;
      }
      free(cp);
      
      InitQueue(&Q);
      
      // 待删除的子树的根结点入队
      EnQueue(&Q, index);
      
      while(!QueueEmpty(Q)) {
          DeQueue(&Q, &e);    // 父结点的位置出队
          
          // 抹掉当前结点
          T->nodes[e].data = '\0';
          
          // 指向该结点的孩子链表
          cp = T->nodes[e].firstchild;
      
          // 释放该结点处的孩子链表所占内存
          while(cp != NULL) {
              EnQueue(&Q, cp->child); // 当前结点位置入队
              
              q = cp;
              cp = cp->next;
              free(q);
          }
          
          T->nodes[e].firstchild = NULL;
      }
      
      InitTree(&R);
      
      R.r = T->r;
      n = 0;
      
      m = R.r;    // 遍历R的游标
      
      for(k = T->r; k != (T->r + T->n) % MAX_TREE_SIZE; k = (k + 1) % MAX_TREE_SIZE) {
          if(T->nodes[k].data != '\0') {
              // 记录结点k的新位置
              parent[k] = m;
              
              // 有效元素放到新位置上
              R.nodes[m] = T->nodes[k];
              
              if(R.nodes[m].parent!=-1) {
                  // 更新父结点位置
                  R.nodes[m].parent = parent[R.nodes[m].parent];
      
                  // 指向父结点的首个孩子
                  cp = R.nodes[R.nodes[m].parent].firstchild;
      
                  // 在父结点的孩子链表中查找当前结点
                  while(cp->child != k) {
                      cp = cp->next;
                  }
                  
                  /*
                   * 更新当前结点在孩子链表中的位置
                   *
                   * 注：这里的值位置只会更新到更小，所以不用担心覆盖后面的元素位置
                   * 否则，在查找该孩子时，就要采取InsertChild中的策略了
                   */
                  cp->child = m;
              }
              
              m = (m + 1) % MAX_TREE_SIZE;
              n++;
          }
      }
      
      R.n = n;
      *T = R;
      
      return OK;
  }
  
  /*
   * 先序遍历
   */
  Status PreOrderTraverse(CTree T, Status(Visit)(TElemType)) {
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          printf("\n");
          return ERROR;
      }
      
      PreTraverse(T, T.r, Visit);
      
      printf("\n");
      
      return OK;
  }
  
  /*
   * 后序遍历
   */
  Status PostOrderTraverse(CTree T, Status(Visit)(TElemType)) {
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          printf("\n");
          return ERROR;
      }
      
      PostTraverse(T, T.r, Visit);
      
      printf("\n");
      
      return OK;
  }
  
  /*
   * 层序遍历
   */
  Status LevelOrderTraverse(CTree T, Status(Visit)(TElemType)) {
      int i;
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          printf("\n");
          return ERROR;
      }
      
      // 顺次遍历所有元素
      for(i = T.r; i != (T.r + T.n) % MAX_TREE_SIZE; i = (i + 1) % MAX_TREE_SIZE) {
          if(!Visit(T.nodes[i].data)) {
              return ERROR;
          }
      }
      
      printf("\n");
      
      return OK;
  }
  
  
  /*━━━━━━━━━━━━━━━━━━━━━━ 仅限内部使用的函数 ━━━━━━━━━━━━━━━━━━━━━━*/
  
  // 创建树的内部函数
  static void Create(CTree* T, FILE* fp) {
      int r;          // 树的根结点的位置（索引）
      int n;          // 记录元素数量
      int cur;        // 游标
      TElemType ch;
      LinkQueue Q;
      QElemType e;    // 队列元素指示结点的位置
      char s[MAX_CHILD_COUNT + 1];
      int i;
      ChildPtr p, pc;
      
      InitQueue(&Q);
      
      n = 0;
      
      // 读取根结点的位置
      if(fp == NULL) {
          printf("请输入根结点的位置(0~%d)：", MAX_TREE_SIZE - 1);
          scanf("%d", &r);
          cur = r;
          
          printf("请输入根结点的值：");
          scanf("%s", s);
          ch = s[0];
          
          // 树根入队
          EnQueue(&Q, cur);
          T->nodes[cur].data = ch;
          T->nodes[cur].parent = -1;
          T->nodes[cur].firstchild = NULL;
          cur = (cur + 1) % MAX_TREE_SIZE;
          n++;
          
          while(!QueueEmpty(Q)) {
              DeQueue(&Q, &e);    // 父结点的位置出队
              
              printf("请依次输入 %c 的孩子结点，不存在孩子时输入一个^：", T->nodes[e].data);
              scanf("%s", s);
              for(i = 0; i < strlen(s); i++) {
                  if(s[i] == '^') {
                      break;
                  }
                  
                  EnQueue(&Q, cur); // 当前结点位置入队
                  T->nodes[cur].data = s[i];
                  T->nodes[cur].parent = e;
                  T->nodes[cur].firstchild = NULL;
                  
                  // 父结点的长子
                  p = T->nodes[e].firstchild;
                  
                  // 包装当前结点
                  pc = (ChildPtr) malloc(sizeof(CTNode));
                  pc->child = cur;
                  pc->next = NULL;
                  
                  // 将当前结点添加到父结点的孩子链表中
                  if(p == NULL) {
                      T->nodes[e].firstchild = pc;
                  } else {
                      // 找到链表尾部
                      while(p->next != NULL) {
                          p = p->next;
                      }
                      
                      p->next = pc;
                  }
                  
                  cur = (cur + 1) % MAX_TREE_SIZE;
                  n++;
              }
          }
      } else {
          // 录入根结点的位置
          ReadData(fp, "%d", &r);
          cur = r;
          
          // 录入根结点的值
          ReadData(fp, "%s", s);
          ch = s[0];
          printf("录入根结点的值：%c\n", ch);
          
          // 树根入队
          EnQueue(&Q, cur);
          T->nodes[cur].data = ch;
          T->nodes[cur].parent = -1;
          T->nodes[cur].firstchild = NULL;
          cur = (cur + 1) % MAX_TREE_SIZE;
          n++;
          
          while(!QueueEmpty(Q)) {
              ReadData(fp, "%s", s);
              ch = s[0];
              printf("依次录入 %c 结点的孩子：", ch);
              
              // 录入孩子结点
              ReadData(fp, "%s", s);
              printf("%s\n", s);
              
              DeQueue(&Q, &e);    // 父结点位置出队
              
              // 遍历孩子
              for(i = 0; i < strlen(s); i++) {
                  if(s[i] == '^') {
                      break;
                  }
                  
                  EnQueue(&Q, cur); // 当前结点位置入队
                  T->nodes[cur].data = s[i];
                  T->nodes[cur].parent = e;
                  T->nodes[cur].firstchild = NULL;
                  
                  // 包装当前结点
                  pc = (ChildPtr) malloc(sizeof(CTNode));
                  pc->child = cur;
                  pc->next = NULL;
                  
                  // 父结点的长子
                  p = T->nodes[e].firstchild;
                  
                  // 将当前结点添加到父结点的孩子链表中
                  if(p == NULL) {
                      T->nodes[e].firstchild = pc;
                  } else {
                      // 找到链表尾部
                      while(p->next != NULL) {
                          p = p->next;
                      }
                      
                      p->next = pc;
                  }
                  
                  cur = (cur + 1) % MAX_TREE_SIZE;
                  n++;
              }
          }
      }
      
      T->r = r;
      T->n = n;
  }
  
  // 返回树结点e的索引，如果不存在，返回-1
  static int EIndex(CTree T, TElemType e) {
      int i = T.r;    // 指向根结点
      int p = -1;
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          return -1;
      }
      
      // 在树中查找结点e
      while(i != (T.r + T.n) % MAX_TREE_SIZE) {
          if(T.nodes[i].data == e) {
              p = i;
              break;
          }
          
          i = (i + 1) % MAX_TREE_SIZE;
      }
      
      return p;
  }
  
  // 返回树结点e的第i个孩子索引，如果不存在，返回-1
  static int CIndex(CTree T, TElemType e, int i) {
      int p, count;
      ChildPtr s;
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          return -1;
      }
      
      // i的范围越界
      if(i < 1 || i > MAX_CHILD_COUNT) {
          return -1;
      }
      
      // 获取结点e的索引
      p = EIndex(T, e);
      // 结点e不存在
      if(p == -1) {
          return -1;
      }
      
      // 指向该结点的首个孩子
      s = T.nodes[p].firstchild;
      // 计数
      count = 1;
      
      while(s != NULL && count < i) {
          count++;
          s = s->next;
      }
      
      if(s != NULL) {
          return s->child;
      } else {
          return -1;
      }
  }
  
  // 获取树T的结点信息，具体包含哪些信息，请参照Pos类型的定义
  static void getPos(CTree T, Pos pt[]) {
      LinkQueue Q;
      QElemType e;
      ChildPtr cp;
      
      int level, n, count;
      
      memset(pt, 0, MAX_TREE_SIZE * sizeof(Pos));
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          return;
      }
      
      InitQueue(&Q);
      
      // 根结点的位置入队
      EnQueue(&Q, T.r);
      pt[T.r].row = 1;
      pt[T.r].col = 1;
      pt[T.r].childIndex = 1;
      
      // 父结点所在的层
      level = 0;
      
      while(!QueueEmpty(Q)) {
          DeQueue(&Q, &e);
          
          // 如果行数发生了改变
          if(pt[e].row != level) {
              count = 0;
              level = pt[e].row;
          }
          
          n = 0;  // 结点e的孩子计数归0
          
          // 每个结点出队时，先设置其最后一个孩子信息为无效，因为不是每个结点都有孩子结点
          pt[e].lastChild = -1;
          
          // 指向该结点的孩子链表
          cp = T.nodes[e].firstchild;
          
          // 释放该结点处的孩子链表所占内存
          while(cp != NULL) {
              // 当前结点位置入队
              EnQueue(&Q, cp->child);
              
              // 记录行数
              pt[cp->child].row = pt[e].row + 1;
              
              // 记录列数
              pt[cp->child].col = ++count;
              
              // 记录当前结点是第几个孩子
              pt[cp->child].childIndex = ++n;
              
              // 为父结点跟新最后一个孩子的信息
              pt[e].lastChild = cp->child;
              
              cp = cp->next;
          }
      }
  }
  
  // 先序遍历的内部实现
  static Status PreTraverse(CTree T, int i, Status(Visit)(TElemType)) {
      int firstChild = -1;    // 初始化为无效的索引
      int rightBrother;
      
      // 访问当前结点
      if(!Visit(T.nodes[i].data)) {
          return ERROR;
      }
      
      // 相比双亲表存储结构，求长子更容易了
      if(T.nodes[i].firstchild!=NULL) {
          firstChild = T.nodes[i].firstchild->child;
      }
      
      // 遍历长子（需要先确定长子的身份）
      if(firstChild != -1 && !PreTraverse(T, firstChild, Visit)) {
          return ERROR;
      }
      
      rightBrother = (i + 1) % MAX_TREE_SIZE;
      
      // 遍历右兄弟（需要先确定右兄弟的身份）
      if(T.nodes[i].parent == T.nodes[rightBrother].parent && !PreTraverse(T, rightBrother, Visit)) {
          return ERROR;
      }
      
      return OK;
  }
  
  // 后序遍历的内部实现
  static Status PostTraverse(CTree T, int i, Status(Visit)(TElemType)) {
      int firstChild = -1;    // 初始化为无效的索引
      int rightBrother;
      
      // 相比双亲表存储结构，求长子更容易了
      if(T.nodes[i].firstchild!=NULL) {
          firstChild = T.nodes[i].firstchild->child;
      }
      
      // 遍历长子（需要先确定长子的身份）
      if(firstChild != -1 && !PostTraverse(T, firstChild, Visit)) {
          return ERROR;
      }
      
      // 访问当前结点
      if(!Visit(T.nodes[i].data)) {
          return ERROR;
      }
      
      rightBrother = (i + 1) % MAX_TREE_SIZE;
      
      // 遍历右兄弟（需要先确定右兄弟的身份）
      if(T.nodes[i].parent == T.nodes[rightBrother].parent && !PostTraverse(T, rightBrother, Visit)) {
          return ERROR;
      }
      
      return OK;
  }
  
  // 输出pos信息，仅限内部测试使用
  static void printPos(CTree T, Pos pt[]) {
      int i;
      
      for(i = T.r; i != (T.r + T.n) % MAX_TREE_SIZE; i = (i + 1) % MAX_TREE_SIZE) {
          printf("%2c ", T.nodes[i].data);
      }
      printf("\n");
      
      for(i = T.r; i != (T.r + T.n) % MAX_TREE_SIZE; i = (i + 1) % MAX_TREE_SIZE) {
          printf("%2d ", pt[i].row);
      }
      printf("\n");
      
      for(i = T.r; i != (T.r + T.n) % MAX_TREE_SIZE; i = (i + 1) % MAX_TREE_SIZE) {
          printf("%2d ", pt[i].col);
      }
      printf("\n");
      
      for(i = T.r; i != (T.r + T.n) % MAX_TREE_SIZE; i = (i + 1) % MAX_TREE_SIZE) {
          printf("%2d ", pt[i].childIndex);
      }
      printf("\n");
      
  }
  
  
  /*━━━━━━━━━━━━━━━━━━━━━━ 图形化输出 ━━━━━━━━━━━━━━━━━━━━━━*/
  
  // 以图形化形式输出当前结构
  void PrintTree(CTree T) {
      Pos pt[MAX_TREE_SIZE];
      
      // 遇到空树则无需继续计算
      if(TreeEmpty(T)) {
          printf("\n");
          return;
      }
      
      // 计算T中结点的位置信息
      getPos(T, pt);
      
      Print(T, pt, T.r);
      
      printf("\n");
      
      printf("存储结构：\n");
      PrintFramework(T);
  }
  
  // 图形化输出当前结构内部实现
  static void Print(CTree T, Pos pt[], int i) {
      int firstChild = -1;    // 初始化为无效的索引
      int rightBrother;
      int k;
      
      // 访问当前结点
      printf("%c ", T.nodes[i].data);
      
      // 相比双亲表存储结构，求长子更容易了
      if(T.nodes[i].firstchild!=NULL) {
          firstChild = T.nodes[i].firstchild->child;
      }
      
      // 遍历长子（需要先确定长子的身份）
      if(firstChild != -1) {
          Print(T, pt, firstChild);
      }
      
      rightBrother = (i + 1) % MAX_TREE_SIZE;
      
      // 遍历右兄弟（需要先确定右兄弟的身份）
      if(rightBrother != (T.r + T.n) % MAX_TREE_SIZE && T.nodes[i].parent == T.nodes[rightBrother].parent) {
          // 访问当前结点的右兄弟前，如果当前结点不是最后一个孩子，则进行一次换行
          if(pt[T.nodes[i].parent].lastChild != i) {
              printf("\n");
              
              for(k = 0; k < pt[rightBrother].row - 1; k++) {
                  printf(". ");
              }
          }
          
          Print(T, pt, rightBrother);
      }
  }
  
  // 图形化输出树的排列结构，仅限内部测试使用
  static void PrintFramework(CTree T) {
      int k;
      ChildPtr cp;
      
      if(T.n == 0) {
          return;
      }
      
      printf("+---------+-----------\n");
      printf("|  i e  p | child list\n");
      printf("+---------+-----------\n");
      
      for(k = T.r; k != (T.r + T.n) % MAX_TREE_SIZE; k = (k + 1) % MAX_TREE_SIZE) {
          
          printf("| %2d %c %2d", k, T.nodes[k].data, T.nodes[k].parent);
          
          cp = T.nodes[k].firstchild;
          if(cp != NULL) {
              printf(" ->");
          } else {
              printf(" | ");
          }
          
          while(cp != NULL) {
              printf(" %2d", cp->child);
              cp = cp->next;
          }
          
          printf("\n");
      }
      
      printf("+---------+-----------\n");
  }
  