小问题!!
完整的程序如下:
输入前序中序求后序
---------------------main.cpp------------------
#include <iostream>
#include <string>
#include "Tree.h "
using namespace std;
int main()
{
string preorder,inorder;
while(cin> > preorder> > inorder)//输入前序和中序
{
BinTree Tree(preorder,inorder);
Tree.PrintPostorder(Tree.GetRoot());
cout < <endl;
}
return 0;
}
-----------------------Tree.cpp-----------------
#include <iostream>
#include <string>
#include "Tree.h "
using namespace std;
TreeNode::TreeNode(char a)
{
data=a;
left=NULL;
right=NULL;
}
TreeNode* BinTree::create(const string& preorder,const string& inorder,int start1,int start2,int size)//start1是preorder第一个元素在初始输入的preorder的下标,start2是inorder第一个元素在初始输入的inorder的下标
{
if(size==0)
return NULL;
TreeNode* p=new TreeNode(preorder[start1]);
int i=inorder.find(preorder[start1]);//返回inorder中第一次出现preorder[start1]的位置
if(i==-1)
return NULL;
p-> left=create(preorder, inorder, start1+1, start2, i-start2);//创建左子树
p-> right=create(preorder, inorder, start1+1+i-start2, start2+1+i-start2, size-i+start2-1);//创建右子树
return p;
}
BinTree::BinTree(const string& preorder,const string& inorder)
{
root=create(preorder,inorder,0,0,preorder.size());
}
void BinTree::destroy(TreeNode* current)
{
if(current!=NULL)
{
destroy(current-> left);
destroy(current-> right);
delete current;
}
}
BinTree::~BinTree()
{
destroy(root);
}
void BinTree::PrintPostorder(TreeNode* current) const
{
if(!current)
return;
PrintPostorder(current-> left);
PrintPostorder(current-> right);
cout < <current-> data;
}
TreeNode* BinTree:: GetRoot() const
{
return root;
}
------------------------Tree.h-----------------------
#include <string>
using namespace std;
class BinTree;
class TreeNode{
friend class BinTree;
public:
TreeNode(char a);
private:
TreeNode *left,*right;
char data;
};
class BinTree{
public:
BinTree(const string& preorder,const string& inorder);
~BinTree();
void BinTree::destroy(TreeNode* q);
TreeNode* BinTree::create(const string& preorder,const string& inorder,int start1,int start2,int size);
void PrintPostorder(TreeNode* current) const;
TreeNode* GetRoot() const;
private:
TreeNode* root;
};
我如果想要使程序更加完善,如当我输入前序:ifddow,中序:fddowi
我想要提示错误,并且能再输入一次,而不是像这个程序这样直接结束,我应该怎么修改?
补充一点:当我用上面的例子试的时候,为什么程序会直接结束?
[解决办法]
TreeNode* p=new TreeNode(preorder[start1]);
int i=inorder.find(preorder[start1]);
访问字符串preorder时没有做边界检查,你可以在程序中自己检查,也可以使用现成的异常处理机制。string类中使用at()成员函数在数组索引时,可以向程序员抛出友好的异常,你只需在程序中捕获这个异常。
具体改动:
TreeNode* p=new TreeNode(preorder.at(start1));
int i=inorder.find(preorder.at(start1));
在main中添加#include <exception>
while(cin> > preorder> > inorder){
try {
BinTree Tree(preorder,inorder);
Tree.PrintPostorder(Tree.GetRoot());
cout < <endl;
}catch(exception& e){
cerr < <e.what() < <endl;
cout < < "Please try again. " < <endl;
continue;
}
}