数据结构 创建二叉树

Question

问题：创建二叉树 问题

A(B(D,F),C(H,))

碰到'(' 下一个字符在左边分支创建节点

碰到',' 下一个字符在右边分支创建节点

碰到')' 不创建

A
|
B ------- C
| |
D - F H

求思路，或者代码，呵呵

Answer 1

void GenTree :: ConstructTree ( istream& in, char& value ) {
//从输入流对象in接受用广义表表示的非空树，建立广义表的存储表示t。
Stack <GenTreeNode* > st (maxSubTreeNum); //用于建表时记忆回退地址
GenTreeNode * p, q, r; Type ch;
cin >> value; //广义树停止输入标志数据
cin >> ch; first = q = new GenTreeNode ( 0, ch ); //建立整个树的根结点
cin >> ch; if ( ch == ‘(’ ) st.Push ( q ); //接着应是‘(’, 进栈
cin >> ch;
while ( ch != value ) { //逐个结点加入
switch ( ch ) {
case ‘(’ : p = new GenTreeNode <Type> ( q ); //建立子树, p->firstChild = q
r = st.GetTop( ); st.Pop( ); //从栈中退出前一结点
r->nextSibling = p; //插在前一结点r之后
st.Push( p ); st.Push( q ); //子树结点及子树根结点进栈
break;
case ‘)’ : q->nextSibling = NULL; st.pop( ); //子树建成, 封闭链, 退到上层
if ( st.IsEmpty ( ) == 0 ) q = st.GetTop( ); //栈不空, 取上层链子树结点
else return 0; //栈空, 无上层链, 算法结束
break;
case ‘,’ : break;
default : p = q;
if ( isupper (ch) ) q = new GenTreeNode ( 0, ch ); //大写字母, 建根结点
else q = new GenTreeNode ( 1, ch ); //非大写字母, 建数据结点
p->nextSibling = q; //链接
}
cin >> ch;
}
}