给你各代码吧:
这是根据二叉树的广义表描述字符串创建的,我觉得这种方式创建是最直观的,
所以每每做二叉树的程序时,我都是用这种方式创建的:
//////////////////////////////////////////////////
//CreateBinTree()私有成员函数
//通过广义表描述字符串建立一棵二叉树,通过指针返回
//例如A(B,C(E,F))#
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::CreateBinTree(char* BinStr
,BinTreeNode<T>*& subTree)
{
//逐个读取字符串
int i=0;
//游标
int k=0;
//处理标志,0表示根结点,1表示左子树,2表示
char s;
//存放每次取出的字符
LinkedStack<BinTreeNode<char>*> LS;
//创建二叉树过程中用到的结点指针堆栈
BinTreeNode<char>* p;
//结点指针变量
BinTreeNode<char>* t;
//存放从堆栈中弹出的内容
BinTreeNode<char>* top;//用于存放从堆栈中取出的栈顶元素
while(BinStr[i]!='#')
{
s=BinStr[i];
switch(s)
{
case '(':
LS.Push(p);
//把当前p的内容入栈
k=1;
//进入左子树的处理
break;
case ',':
k=2;
//进入右子树的处理
break;
case ')':
LS.Pop(t);
//弹出堆栈的内容
break;
default:
//如果取出的字母
{
//如果处理的是根结点
if(k==0)
{
//新建一个结点
p=new BinTreeNode<char>(s);
//把该指针作为树的指针返回
subTree=p;
}
//如果处理的是右子树
else if(k==1)
{
//新建一个接点
p=new BinTreeNode<char>(s);
//取得栈顶结点
LS.getTop(top);
//把该结点挂入栈顶的左指针域
top->leftChild=p;
}
//如果处理的是左子树
else
{
//新建一个接点
p=new BinTreeNode<char>(s);
//取得栈顶结点
LS.getTop(top);
//把该结点挂入栈顶的左指针域
top->rightChild=p;
};
break;
};
};
i++;
}
};
///////////////////////////////CreateBinTree()结束
我的代码里用到一个链式堆栈,这只是BinaryTree<T>类里的一个成员函数
你可能不好直接运行,不过思想基本上已经涵盖了。