#include
#include
#include"BinaryTree.h"
using namespace std;
const int stackIncreament = 20; //栈溢出时扩展空间增量
template
class SeqStack{
public:
int top;
SeqStack(int sz=50); //建立一个空栈
~SeqStack(){delete[] elements;}
void push(const T& x); //进栈要检查栈状态
bool pop(T x); //出栈要检查栈状态
bool getTop(T& x);
bool isEmpty() const { return (top==-1)?true:false; }
bool isFull() const { return (top==maxSize-1)?true:false; }
int getSize() const { return top+1; }
void makeEmpty(){ top=-1; }
friend ostream& operator<< (ostream& os,SeqStack<T>& S); //重载<<
private:
//用顺序表的动态存储（可以扩充）P46，顺序表的两种存储表示方式
T *elements;
int maxSize;
void overflowProcess();
};
template
SeqStack::SeqStack(int sz): top(-1),maxSize(sz){
elements=new T[maxSize];
assert(elements != NULL); //断言检查动态存储是否分配成功
}
template
void SeqStack::overflowProcess(){
T *newArray=new T[maxSize+stackIncreament];
assert(newArray != NULL);
maxSize=maxSize+stackIncreament;
delete[] elements;
elements=newArray;
}
template
void SeqStack::push(const T& x){
if(isFull() == true) overflowProcess(); //栈满进行溢出处理
elements[++top] = x;
}
template
bool SeqStack::pop(T x){
if(isEmpty() == true) return false;
x=elements[top--];
return true;
}
template
bool SeqStack::getTop(T& x){
if(isEmpty()==true) return false;
x=elements[top];
return true;
}
template
ostream& operator<< (ostream& os,SeqStack& S){
os<<"top = "<<S.top<<endl;
os<<"栈中的元素为:"<<endl;
for(int i=0;i<=S.top;i++)
os<<i<<":"<<S.elements[i]<<endl;
return os;
}
****************************以上SeqStack.h*****************************************
#include
#include
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
template
struct BinTreeNode{
T data;
BinTreeNode<T> *lchild,*rchild;
BinTreeNode():lchild(NULL),rchild(NULL){ }
BinTreeNode(T x,BinTreeNode<T> *l=NULL,BinTreeNode<T> *r=NULL):lchild(l),rchild(r),data(x){ }
};
template
class BinaryTree{
private:
BinTreeNode *root;
public:
/*template
friend bool is_similar(BinTreeNode *p,BinTreeNode *q);
*/
BinaryTree():root(NULL){}//初始化一棵空树
BinaryTree(T x){ root=new BinTreeNode(x); }//初始化一棵只有一个接点的树
BinTreeNode<T> * createBinTree();
BinTreeNode<T> * preOrder(BinTreeNode<T> *p);
BinTreeNode<T> * inOrder(BinTreeNode<T> *p);
BinTreeNode<T> * postOrder(BinTreeNode<T> *p);
BinTreeNode<T> * preOrderStack(BinTreeNode<T> *p);
};
template
BinTreeNode* BinaryTree::createBinTree(){
BinTreeNodet;
/*t=root;/
T x;
cin>>x;
if(x=='#')
t=NULL;
else{
t=new BinTreeNode<T>(x);
//t=new BinTreeNode<T>;
t->lchild=createBinTree();
t->rchild=createBinTree();
}
return t;
}
template
BinTreeNode * BinaryTree::preOrder(BinTreeNode *p){
if(p==NULL)
cout<<'#';
else
cout<data;
if(p){
preOrder(p->lchild);
preOrder(p->rchild);
}
return p;
}
template
BinTreeNode * BinaryTree::inOrder(BinTreeNode *p){
if(p)
inOrder(p->lchild);
if(p==NULL)
cout<<'#';
else
cout<data;
if(p)
inOrder(p->rchild);
return p;
}
template
BinTreeNode * BinaryTree::postOrder(BinTreeNode *p){
if(p){
postOrder(p->lchild);
postOrder(p->rchild);
}
if(p==NULL)
cout<<'#';
else
cout<data;
return p;
}
template
BinTreeNode * BinaryTree::preOrderStack(BinTreeNode *p){
SeqStack> S;
if(p==NULL)
cout<<'#';
else { //p不指向空树
while(p||S.top!=-1){
if(p){
S.push(*p);
cout<<p->data;
p=p->lchild;
}
else{
S.pop(*p);
p=p->rchild;
}
}
}
return p;
}
********************************************以上BinaryTree**************************
#include
#include"SeqStack.h"
int main(){
BinTreeNode<char> *p;
/*SeqStack<BinTreeNode<char>> S;*/
BinaryTree<char> B;
cout<<"请输入一棵树B:"<<endl;
p=B.createBinTree();
cout<<endl;
cout<<"先序遍历的结果为:"<<endl;
B.preOrder(p);
cout<<endl;
cout<<"中序遍历的结果为:"<<endl;
B.inOrder(p);
cout<<endl;
cout<<"后序遍历的结果为:"<<endl;
B.postOrder(p);
cout<<endl;
cout<<"先序遍历的非递归形式结果为:"<<endl;
B.preOrderStack(p);
system("pause");
return 0;
}
**********************************************以上main函数*************************
