#ifndef _STACK_H
#define _STACK_H
#define STACK_INIT_SIZE 100 //初始栈的最大长度
#define STACKINCREMENT 10 //每次新增的栈的长度
template <class DataType>
class Stack{
public:
Stack();
void Push(DataType e); //插入为e的新栈顶元素
int Pop(DataType &e); //删除栈顶元素
int GetTop(DataType &e); //取出栈顶元素
int StackEmpty(); //判断栈是否为空：空返回
void DestroyStack(); //栈被销毁
private:
DataType *base; //栈尾
DataType *top; //栈顶
int stacksize;
};
template <class DataType>
Stack<DataType>::Stack()
{
if(!(base=(DataType*)malloc(STACK_INIT_SIZE*sizeof(DataType)))) exit(1);
top=base;
stacksize=STACK_INIT_SIZE;
}
template <class DataType>
void Stack<DataType>::Push(DataType e)
{
if(top-base>=stacksize){
if(!(base=(DataType*)realloc(base,(stacksize+STACKINCREMENT)*sizeof(DataType)))) exit(1);
top=base+stacksize;
stacksize+=STACKINCREMENT;
}
*top++=e;
}
template <class DataType>
int Stack<DataType>::Pop(DataType &e)
{
if(top==base) return 0;
e=*--top;
return 1;
}
template <class DataType>
int Stack<DataType>::GetTop(DataType &e)
{
if(top==base) return 0;
e=*(top-1);
return 1;
}
template <class DataType>
int Stack<DataType>::StackEmpty()
{
return top==base? 1:0;
}
template <class DataType>
void Stack<DataType>::DestroyStack()
{
free(base);
}
#endif
#ifndef _BITREE_H
#define _BITREE_H
#include "Stack.h"
template <class DataType>
class BiTree; //友元类引用申明
template <class DataType>
class TreeNode
{
TreeNode():lchild(NULL),rchild(NULL){}
friend class BiTree<DataType>;
private:
DataType data;
TreeNode *lchild,*rchild;
};
template <class DataType>
class BiTree{
public:
void CreateBiTree(); //创建根节点------主过程
void CreateBiTree(TreeNode<DataType>* &p); //创建节点函数----子过程
void PosROrderTraverse(); //递归------后序遍历二叉树---主过程
void PosROrderTraverse(TreeNode<DataType>* p); //递归------后序遍历二叉树---子过程
void PosOrderTraverse(); //非递归------后序遍历二叉树
private:
TreeNode<DataType>* root; //树根
DataType temp; //代表元素为空的符号
};
template <class DataType>
void BiTree<DataType>::CreateBiTree()
{
cout<<"请输入代表元素为空的符号:";
cin>>temp; if(!(root=(TreeNode<DataType>*)malloc(sizeof(TreeNode<DataType>)))) exit(1);
cout<<"请输入数据:"<<endl;
CreateBiTree(root);
}
template <class DataType>
void BiTree<DataType>::CreateBiTree(TreeNode<DataType>* &p)
{
TreeNode<DataType>* px;
if(!(px=(TreeNode<DataType>*)malloc(sizeof(TreeNode<DataType>)))) exit(1);
cin>>px->data;
if(px->data==temp) {p=NULL;free(px);}
else{
p=px;
CreateBiTree(px->lchild);
CreateBiTree(px->rchild);
}
}
template <class DataType>
void BiTree<DataType>::PosROrderTraverse()
{
PosROrderTraverse(root);
}
template <class DataType>
void BiTree<DataType>::PosROrderTraverse(TreeNode<DataType>* p)
{
if(p){
PosROrderTraverse(p->lchild);
PosROrderTraverse(p->rchild);
cout<<p->data<<" ";
}
}
template <class DataType>
void BiTree<DataType>::PosOrderTraverse()
{
Stack<TreeNode<DataType>*> S;
TreeNode<DataType>* p;
TreeNode<DataType>* r; //使用r节点表示访问了右子树替代标志域
p=root;
while(p||!S.StackEmpty())
{
if(p){S.Push(p);p=p->lchild;}
else{
S.GetTop(p);
if(p->rchild&&p->rchild!=r){p=p->rchild;S.Push(p);p=p->lchild;}
else{S.Pop(p);cout<<p->data<<" ";r=p;p=NULL;}
}
}
S.DestroyStack();
}
#endif
#include<iostream>
#include "BiTree.h"
using namespace std;
int main()
{
BiTree<char> my;
my.CreateBiTree();
my.PosROrderTraverse();
cout<<endl;
my.PosOrderTraverse();
return 0;
}