设计一个按层序遍历森林的办法。解决方法

设计一个按层序遍历森林的办法。
例子如下（树以广义表的结构表示）：
森林：
(A(B,C(F),D))
(G(H))
如上所述的森林按层次遍历的顺序是AGBCDHF

(1)用C++/C定义你选择的森林的存储结构
(2)利用C++/C实现以上描述的层次遍历森利的算法。
VoidForestTraverse(Forest   T,(void)(*visit)(ElemType   d))

(3)利用C++/C实现求森林中树的最大高度的函数（如上面的森林最大高度是3）。
int   height(Forest   T)




------解决方案--------------------
1 使用链表，计算机算法C++版，中文版第45页有表述
可以使用Node类型为tag，data，link如果tag==1那么表示data有数据，如果tag==0表示data指向的是兄弟节点。
2 使用Stack作为辅助，进行层次遍历
第一层加入Stack，比如PUSH A，PUSH G
POP A，PUSH B，PUSH C， PUSH D ， POP G， PUSH H
然后POP B，POP C,PUSH F, POP D, POP H,
最后POP F

关于你的原型函数VoidForestTraverse(Forest T,(void)(*visit)(ElemType d))，没有看出来那个回调用来干什么．可能是实现譬如打印之类功能的需求．
3 对森林中每个树进行高度测量，选择最大高度

自己看法，希望能抛砖引玉
------解决方案--------------------
算法LevelOrder（t）

// 指针t指向与森林自然对应的二叉树的根

L1 [创建一个辅助队列] CREATE（Q）.

L2 [根结点入队] Q t .

L3 [利用队列进行层次遍历]

WHILE NOT（IsEmpty（Q））DO

（ p <= Q .

WHILE p≠NULL DO

（ PRINT（data（p））.

IF FirstChild（p）≠NULL

THEN Q FirstChild（p）.

p←NextBrother（p）））

实现
template <class T>

void Tree <T> ;; LevelOrder（）

{

// 按层次次序遍历以当前结点为根的树，利用

一个辅助队列

Queue q ;

if（! IsEmpty（））

// 若树不为空树，开始树的层次遍历

{

TreeNode *p = current ; //保存当前结点

q.QInsert（current）; // 当前结点入队

while（! q.QEmpty（））

{

current = q.QDelete（）;

//出队一个结点，设为当前结点

visit（）; // 访问当前结点

FirstChild（）;

// 将当前结点的所有子结点入队

while（! IsEmpty（））

{

q.QInsert（current）;

NextBrother（）;

}

}

}

current = p ; // 恢复当前结点

}



------解决方案--------------------
我用的 firstChild-nextSibling 做存储结构
由于各个Tree的根节点之间没有联系,所以算法这样:
1) 首先遍历各个Tree的根节点,同时将各个 根节点指针 入队
2) 出队一个元素q.遍历q的各个孩子(注意不是q本身),同时将这些 孩子的指针 入队
3) 队空,退出

template <typename T> class TreeNode {

public:

TreeNode(T data) { //constructor
this-> data = data;
this-> firstChild = NULL;
this-> nextSibling = NULL;
}

TreeNode(T data, TreeNode <T> *firstChild, TreeNode <T> *nextSibling) {
this-> data = data;
this-> firstChild = firstChild;
this-> nextSibling = nextSibling;
}

T getData(void) const { //accessor

return this-> data;
}

TreeNode <T> *getFirstChild(void) const {

return this-> firstChild;
}

TreeNode <T> * getNextSibling(void) const {

return this-> nextSibling;
}
..............
private:
T data;
TreeNode <T> *firstChild;
TreeNode <T> *rightSibling;
};

template <typename T> class Tree {

public:
...... //constructor
TreeNode <T> *getRoot() {

return this-> root;
}
.........

private:

TreeNode <T> *root;

};

template <typename T> class Forest {

public: