算法 6.13.txt

《数据结构及应用算法教程》一书的源代码。作者：严蔚敏

算法 6.13
void CreateTree( CSTree &T ) {
    // 按自上而下自左至右的次序输入双亲-孩子的有序对，建立树的二叉链表。
    // 输入时，以一对'#'字符作为结束标志，根结点的双亲空，亦以'#'表示之。
    T = NULL;
    for( cin>>fa>>ch;  ch!='#';  cin>>fa>>ch;) {
      p = new CSNode;  p->data = ch;  p->firstchild = p->nextsibling = NULL;
                      // 创建结点，指针域暂且先赋空
      EnQueue(Q, p);            // 指针入队列
      if (fa == '#')  T = p;        // 所建结点为根
      else {                    // 非根结点的情况
        GetHead(Q,s);           // 取队列头元素(指针值)  
        while (s->data != fa ) {    // 查询双亲结点  
          DeQueue(Q,s);  GetHead(Q,s);
        } //while
        if (!(s->firstchild)) { s->firstchild = p; r = p; }  // 链接第一个孩子结点
        else { r->nextsibling = p;  r = p;  }         // 链接其它孩子结点
      } //else
    } //for
} // CreateTree