关于一道二叉树遍历的问题帮忙找下错！
#include<iostream.h>#include<stdlib.h>
template<class T>
struct BinTreeNode{
T data;
BinTreeNode<T> *leftChild,*rightChild;
BinTreeNode():leftChild(NULL),rightChild(NULL){}
BinTreeNode(T x,BinTreeNode<T> *l=NULL,BinTreeNode<T> * r=NULL)
:data(x),leftChild(l),rightChild(r){}
};
enum Tag{L,R};
template<class T>
struct stkNode{
BinTreeNode<T> *ptr;
enum Tag tag;
stkNode(BinTreeNode<T> *N=NULL):ptr(N),tag(L){}
};
#include"03_01_089SeqStack.h"
template <class T>
class BinaryTree{
public:
BinaryTree():root(NULL){} //构造函数
BinaryTree(T value):RefValue(value),root(NULL){}//构造函数
~BinaryTree(){ if(root) destroy(root); } //析构函数
friend istream& operator>>(istream &in,BinaryTree<T> &Tree)//重载操作，输入
{ Tree.CreateBinTree(in,Tree.root); return in; }
void preOrder(void (*visit)(BinTreeNode<T> *p));//p204前序遍历，visit是访问函数
void inOrder(void (*visit)(BinTreeNode<T> *p));//p205中序遍历，visit是访问函数
void postOrder(void (*visit)(BinTreeNode<T> *p));//p206后序遍历，visit是访问函数
protected:
BinTreeNode<T> *root; //二叉树的根指针
T RefValue; //数据输入停止标志
void destroy(BinTreeNode<T> *&subTree); //p196删除二叉树使之为空树
void CreateBinTree(istream &in,BinTreeNode<T> *&BT);//P197前序遍历建立二叉树
};
template<class T>//后序遍历删除
void BinaryTree<T>::destroy(BinTreeNode<T> *&subTree){
if(subTree==NULL) return;
destroy(subTree->leftChild);
destroy(subTree->rightChild);
delete subTree; subTree=NULL;
}
//(1) CreateBinTree的实现；
template<class T>
void CreateBinTree(istream&in,BinTreeNode<T>*&BT){
SeqStack<BinTreeNode<char>*>s;
BT=NULL;
BinTreeNode<char>*p,*t;int k;
char ch;
in>>ch;
while(ch!=RefValue){
switch(ch){
case'(':s.Push(p);k=1;break;
case')':s.Pop(t);break;
case','=2;break;
default:p=new BinTreeNode(ch);
if(BT==NULL)BT=p;
else if(k==1){
s.getTop(t);t->leftChild=p;
}
else{
s.getTop(t);t->rightChild=p;
}
}
in>>ch;
}
}
//(2) preOrder的实现；
//void preOrder(void (*visit)(BinTreeNode<T> *p));//p204前序遍历，visit是访问函数
template<class T>
void BinaryTree<T>::preOrder(void (*visit)(BinTreeNode<T> *p)){
SeqStack<BinTreeNode<T>*>S;
BinTreeNode<T>*p=root;
S.Push(NULL);
while(p!=NULL){
visit(p);
if(p->rightChild!=NULL)S.Push(p->rightChild);
if(p->leftChild!=NULL)p=p->leftChild;
else S.Pop(p);
}
}
//(3) inOrder的实现；
//void inOrder(void (*visit)(BinTreeNode<T> *p));//p205中序遍历，visit是访问函数
template<class T>
void BinaryTree<T>::inOrder(void (*visit)(BinTreeNode<T> *p)){
SeqStack<BinTreeNode<T>*>S;
BinTreeNode<T>*p=root;
do{
while(p!=NULL){
S.Push(p);
p=p->leftChild;
}
if (!S.IsEmpty()){
S.Pop(p);visit(p);
p=p->rightChild;
}
}
while (p!=NULL||!S.IsEmpty());
}
//(4) postOrder的实现。
//void postOrder(void (*visit)(BinTreeNode<T> *p));//p206后序遍历，visit是访问函数
template<class T>
void BinaryTree<T>::postOrder(void (*visit)(BinTreeNode<T> *p)){
SeqStack<stkNode<T>*>S;stkNode<T> w;
BinTreeNode<T>*p=root;
do{
while(p!=NULL){
w.ptr=p; w.tag=L; S.Push(w);
p=p->leftChild;
}
int continuel=1;
while(continuel&&!S.IsEmpty()){
S.Pop(w);p=w.ptr;
switch(w.tag){
case L:w.tag=R;S.Push(w);
continuel=0;
p=p->rightChild;
break;
case R:visit(p);break;
}
}
}
while(!S.IsEmpty());
cout<<endl;
}
另外一个头函数;
#include<stdlib.h>//用于exit(1)
#include<iostream.h>
#include <assert.h>
const int stackIncreament=20;
template <class T>
class SeqStack{
public:
SeqStack(int sz=10);
~SeqStack(){ delete[]elements;}
void Push(const T &x); //新元素x进栈
bool Pop(T &x); //栈顶元素出栈，由x返回
bool getTop(T &x); //读取栈顶元素，由x返回
bool IsEmpty()const{ return top==-1; } //判断栈空否
int getSize()const{ return top+1; }//计算栈中元素个数
void MakeEmpty(){ top=-1; }//置空栈
friend ostream &operator<<(ostream &out,SeqStack<T> &s);
private:
T* elements;//存放栈中元素的栈数组
int top;//栈顶指针
int maxSize;//栈最大可容纳元素个数
void overflowProcess();//栈的溢出处理
};
//(1) 构造函数的实现；
template <class T>
SeqStack<T>::SeqStack(int sz): top(-1), maxSize(sz) {
elements = new T[maxSize];
assert(elements!=NULL);
}
//(2) 函数Push的实现；
template <class T>
void SeqStack<T>::Push(const T& x) {
if (top==maxSize-1) overflowProcess();
elements[++top] =x;
}
//(3) 函数Pop的实现；
template <class T>
bool SeqStack<T>:: Pop (T& x) {
if(IsEmpty()==true) return false;
x=elements[top--];
return true;
}
//(4) 函数getTop的实现；
template <class T>
bool SeqStack<T>::getTop(T& x) {
if (IsEmpty()==true) return false;
x= elements[top];
return true;
}
//(5) 函数operator<<的实现；
template <class T>
ostream& operator <<(ostream& os ,SeqStack<T>& s) {
os<<"top="<<s.top<<endl;
for(int i=0;i<=s.top;i++)
os<<i<<":"<<s.elements[i]<<endl;
return os;
}
//(6) 函数overflowProcess的实现。
template <class T>
void SeqStack<T>::overflowProcess( ) {
T *newArray=new T[maxSize+stackIncreament];
if(newArray==NULL) {cerr<<"存储分配失败!";exit(1); }
for(int i=0;i<=top;i++)
newArray[i]=elements[i];
maxSize=maxSize+stackIncreament;
delete []elements;
elements=newArray;
}
最后是主函数：
#include<iostream.h>
#include"stack.h"
template<class T>
void visit(BinTreeNode<T> *p){cout<<p->data;}
void main(){
BinaryTree<char> BT('#');
cout<<"\n输入二叉树的广义表(#结束)："<<endl;
cin>>BT;
cout<<"前序遍历输出二叉树：\n";
BT.preOrder(visit);
cout<<endl;
cout<<"中序遍历输出二叉树：\n";
BT.inOrder(visit);
cout<<endl;
cout<<"后序遍历输出二叉树：\n";
BT.postOrder(visit);
cout<<endl;
}
