1329_一般的树

对于一般的树（主要指非二叉树），可以转换为“孩子-兄弟链表”二叉树来处理。

假设以二元组(F,C)的形式输入树的各条边，请转换为“孩子-兄弟链表”方式存储该树。

对于一般的树，其子树是没有严格的次序之分的，因此，为了确保所得二叉树的唯一性，本题约定：按输入的先后顺序规定“第一棵子树”，“第二棵子树”... 以此类推。从而，“第一棵子树”将成为转换所得的左子树。

输入的第一行是一个整数p，表示有p-1条边，p ≥ 1 。接下来是p行，每行两个非负整数 (i, j) ，表示该树的节点的编号。

i表示父节点的编号，j表示子节点的编号。i=-1时，表示j没有父节点。

第一行输出该树原本的高度，以及该树的节点个数。

接下来每一行输出该树一条从根到叶子的路径。

从左到右输出各条路径。

7
-1 1
1 2
1 3
1 4
3 5
3 6
5 7

4 7
1 2
1 3 5 7
1 3 6
1 4

给出相关的伪代码如下：

// 创建“孩子-兄弟链表”方式存储的树
void CreatTree( )
{
   int fa, ch; // 父节点编号，子节点编号
   T = NULL;

   scanf( &p );
   for( ;  n>0;  n-- )
   {
       scanf( &fa, &ch );
       p = GetTreeNode( ch );  // 创建结点

       EnQueue( Q, p ); // 指针入队列

       if ( fa == -1 ) // 所建为根结点
           T = p;
       else // 非根结点的情况
       {
           GetHead( Q, s ); // 取队列头元素(指针值)
           while ( s->data != fa ) // 查询双亲结点
           {
               DeQueue( Q, s );
               GetHead( Q, s );
           }
           if ( !(s->firstchild) ) // 链接第一个孩子结点
           {
               s->firstchild = p;
               r = p;
           }
           else // 链接其它孩子结点
           {
               r->nextsibling = p;
               r = p;
           }
       }
   } // for
} // CreateTree

// 该树的高度
int TreeDepth( CSTree T )
{
   if(  ! T  )
       return 0;
   else
   {
       h1 = TreeDepth( T->firstchild );
       h2 = TreeDepth( T->nextsibling );
       return  max( h1+1, h2 ) ;
   }
}// TreeDepth

// 输出森林中所有从根到叶的路径
void OutPath( Bitree T, Stack  & S )
{
   while ( T )
   {
       Push( S, T->data );
       if ( !T->firstchild )
           Printstack(S);
       else
           OutPath( T->firstchild, S );
       Pop(S);
       T = T->nextsibling;
   } // while
} // OutPath