描述

我们都知道用“左儿子右兄弟”的方法可以将一棵一般的树转换为二叉树，如：

    0                             0
  / | \                          /
 1  2  3       ===>             1
   / \                           \
  4   5                           2
                                 / \
                                4   3
                                 \
                                  5

现在请你将一些一般的树用这种方法转换为二叉树，并输出转换前和转换后树的高度。

输入

输入包括多行，最后一行以一个#表示结束。
每行是一个由“u”和“d”组成的字符串，表示一棵树的深度优先搜索信息。比如，dudduduudu可以用来表示上文中的左树，因为搜索过程为：0 Down to 1 Up to 0 Down to 2 Down to 4 Up to 2 Down to 5 Up to 2 Up to 0 Down to 3 Up to 0。
你可以认为每棵树的结点数至少为2，并且不超过10000。

样例输入

Tree 1: 2 => 4
Tree 2: 5 => 5
Tree 3: 4 => 5
Tree 4: 4 => 4

样例输出

Tree 1: 2 => 4
Tree 2: 5 => 5
Tree 3: 4 => 5
Tree 4: 4 => 4

树转换成二叉树

单树转换成二叉树：

1. 树中的所有相邻兄弟之间加一条连线；
2. 对树中的每个结点只保留它长子之间的连线，删除其它孩子之间的连线；
3. 以树的根结点为轴心，将整棵树顺时针转动45°，使之层次分明
   如:

graph TD subgraph 断线 A2((A))--只保留到长子B的连线---B2((B)) C2((C)) D2((D)) B2--只保留到长子E的连线---E2((E)) F2((F)) D2---G2((G)) B2-.-C2 C2-.-D2 E2-.-F2 end subgraph 加线 A1((A))---B1((B)) A1---C1((C)) A1---D1((D)) B1---E1((E)) B1---F1((F)) D1---G1((G)) B1-.长子B的兄弟.-C1 C1-.长子B的兄弟.-D1 E1-.长子E的兄弟.-F1 end subgraph 一棵树 A((A))---B((B)) A---C((C)) A---D((D)) B---E((E)) B---F((F)) D---G((G)) end

根据树的深度优先搜索信息建树

由于用到了树的深度优先搜索信息，为了方便回溯，需要一个栈保存搜索信息，遇到u时弹栈一个结点；在建立树时，长子不为空时优先考虑长子，即遇到一个d，建立根结点的长子root->vp;否则，早到root->vp（长子)的不为空的兄弟建立。
由于使用了孩子兄弟链存储结构，当树建立好后，只需把hv、vp看成左右孩子即可求对应二叉树的高
详细参考:
SCDN作者mach7的文章：openjudge树的转换

完整代码

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stack>
#define MAX_SIZE 20010
using namespace std;
typedef struct TNode
{
    struct TNode *hp;
    struct TNode *vp; 
}*Tree;
void NewNode(TNode *&node)
{
    node = new TNode;
    node->hp = node->vp = NULL;
}
stack <Tree> roots;
void InitRoots(Tree &tree)
{
    NewNode(tree);
    while (!roots.empty()) roots.pop();
    roots.push(tree);
}
void CreatTree(char dp_mess[MAX_SIZE], Tree &tree)
{
    Tree tem, hp_node, root;
    for (int pos = 0; pos < strlen(dp_mess); pos++) {
       if ('d' == dp_mess[pos]) {
          NewNode(tem);
          root = roots.top();
          if (NULL == root->vp) {
                root->vp = tem;
          } else {
                hp_node = root->vp;
                while (NULL!=hp_node->hp) hp_node = hp_node->hp;
                hp_node->hp = tem;
          }
          roots.push(tem);
       } else {
           roots.pop();
       }
    }
}
int GetTreeHeight(Tree tree)
{
    Tree p;
    int height, max_height = 0;
    if (NULL == tree) return 0;
    else {
        p = tree->vp;
        while (NULL != p) {
            height = GetTreeHeight(p);
            if (max_height < height) max_height = height;
            p = p->hp;
        }
        return max_height + 1;
    }
}
int GetBTreeHeight(Tree tree)
{
     if (NULL == tree) return 0;
     else {
         int lh = GetBTreeHeight(tree->vp);
         int rh  = GetBTreeHeight(tree->hp);
         return (lh > rh)?(lh + 1):(rh + 1);
     }
}
void DeleteTree(Tree tree)
{
	if (NULL != tree)
	{
		DeleteTree(tree->vp);
        DeleteTree(tree->hp);
        delete tree;
        tree = NULL;
	}
}

int main(int argc, char const *argv[])
{
    Tree tree;
    int number = 0;
    char dp_mess[MAX_SIZE];
    while (scanf("%s",&dp_mess)) {
        if (dp_mess[0] == '#') break;
        number++;
        InitRoots(tree);
        CreatTree(dp_mess,tree);
        printf("Tree %d: %d => %d\n",number,GetTreeHeight(tree)-1,GetBTreeHeight(tree)-1);
        DeleteTree(tree);
    }
    system("pause");
    return 0;
}