你指的是firstChild-nextSibling链表结构的树的创建和输出吗?
这是我写的通过广义表描述字符串s来非递归创建一棵树的代码:
这个函数你可以在GenTree<T>的带参数的构造函数里调用
/////////////////////////////////////////////////////
//CreateTree私有成员函数
//通过广义表形式的树的描述字符串建立
//树的子女-兄弟链表的存储结构(s以'#'号结尾)
/////////////////////////////////////////////////////
template<class T>
void Tree<T>::CreateTree(char* s)
{
//树的结点变量
TreeNode<T>* p=NULL;
//取出的栈顶元素
TreeNode<T>* top=NULL;
//用于保存同行前一个结点的指针
TreeNode<T>* pre=NULL;
//创建树过程中用到的堆栈,元素是结点指针
LinkedStack<TreeNode<T>*> LS;
//计数器
int i=0;
//标志是连在上个结点的firstChild域还是nextSibling域
int flag=0;//0:第一个结点 1:表示连在firstChild 2:表示连在nextSibling
while(s[i]!='#')
{
switch(s[i])
{
//如果取出的是'('左括号
case '(':
{
flag=1; //表示开始要延伸当前结点的长子结点
LS.Push(p); //当前结点入栈
break;
}
//如果取出的是','逗号
case ',':
{
pre=p; //保留当前结点
flag=2; //表示开始要延伸当前结点的兄弟结点
break;
}
//如果取出的是')'右括号
case ')':
{
LS.Pop(p); //回到父结点开始延伸
flag=2; //表示开始要延伸当前结点的兄弟结点
break;
}
//如果取出的是字母
default:
{
p=new TreeNode<T>(s[i]); //依据取出的字母新建一个结点
//表示新建的结点是上个结点的长子结点
if(flag==1)
{
LS.getTop(top); //取栈顶结点
top->firstChild=p; //挂上长子结点
}
else if(flag==2)
pre->nextSibling=p; //兄弟结点的连接
else
root=p; //第一个创建的是根结点
}
}
i++;
}
};
/////////////////////////////////CreateTree()函数结束