/*//////////////////////////////////////////////////////////////////////////////
// 名 称 (Unit Name): BiTree.h 二叉树头文件
// 备 注 ( Remarks ): 包含文件栈的地址：http://www.ourys.com/post/38.html， 包含文件队列的地址：http://www.ourys.com/post/38.html
//////////////////////////////////////////////////////////////////////////////*/
#ifndef _BITREE_H
#define _BITREE_H
#include "Stack.h"
#include "Queue.h"
template <class DataType>
class BiTree; //友元类引用申明
/*-------- 树的节点定义，将BiTree定义为友元类，便于对其操作 -----------*/
template <class DataType>
class TreeNode
{
TreeNode():lchild(NULL),rchild(NULL){}
friend class BiTree<DataType>;
private:
DataType data;
TreeNode *lchild,*rchild;
//bool tag; //后序遍历时用的标志域
};
/*-------- 二叉树树开始 -----------*/
template <class DataType>
class BiTree{
public:
void CreateBiTree(); //创建根节点------主过程
void CreateBiTree(TreeNode<DataType>* &p); //创建节点函数----子过程
void PreROrderTraverse(); //递归------先序遍历二叉树---主过程
void PreROrderTraverse(TreeNode<DataType>* p); //递归------先序遍历二叉树---子过程
void InROrderTraverse(); //递归------中序遍历二叉树---主过程
void InROrderTraverse(TreeNode<DataType>* p); //递归------中序遍历二叉树---子过程
void PosROrderTraverse(); //递归------后序遍历二叉树---主过程
void PosROrderTraverse(TreeNode<DataType>* p); //递归------后序遍历二叉树---子过程
void PreOrderTraverse(); //非递归------中序遍历二叉树
void InOrderTraverse(); //非递归------中序遍历二叉树
void PosOrderTraverse(); //非递归------后序遍历二叉树
void LevelOrderTraverse(); //非递归------层次遍历二叉树
protected:
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;
// p->tag=false; //后序遍历时用的标志域初始化
CreateBiTree(px->lchild);
CreateBiTree(px->rchild);
}
}
/*-------- 递归------先序遍历二叉树---主过程 --------------*/
template <class DataType>
void BiTree<DataType>::PreROrderTraverse()
{
PreROrderTraverse(root);
}
/*-------- 递归------先序遍历二叉树---子过程 --------------*/
template <class DataType>
void BiTree<DataType>::PreROrderTraverse(TreeNode<DataType>* p)
{
if(p){
cout<<p->data<<" ";
PreROrderTraverse(p->lchild);
PreROrderTraverse(p->rchild);
}
}
/*-------- 递归------中序遍历二叉树---主过程 --------------*/
template <class DataType>
void BiTree<DataType>::InROrderTraverse()
{
InROrderTraverse(root);
}
/*-------- 递归------中序遍历二叉树---子过程 --------------*/
template <class DataType>
void BiTree<DataType>::InROrderTraverse(TreeNode<DataType>* p)
{
if(p){
InROrderTraverse(p->lchild);
cout<<p->data<<" ";
InROrderTraverse(p->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>::PreOrderTraverse()
{
Stack<TreeNode<DataType>*> S;
TreeNode<DataType>* p;
p=root;
while(p||!S.StackEmpty()){
if(p){S.Push(p);cout<<p->data<<" "; p=p->lchild;}
else{
S.Pop(p);
p=p->rchild;
}
}
S.DestroyStack();
}
/*-------- 非递归------中序遍历二叉树--------------*/
template <class DataType>
void BiTree<DataType>::InOrderTraverse()
{
Stack<TreeNode<DataType>*> S;
TreeNode<DataType>* p;
p=root;
while(p||!S.StackEmpty()){
if(p){S.Push(p); p=p->lchild;}
else{
S.Pop(p);
cout<<p->data<<" ";
p=p->rchild;
}
}
S.DestroyStack();
}
/*--------非递归------后序遍历二叉树（没有使用标志域）--------------*/
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();
}
/*--------非递归------后序遍历二叉树（运用标志域，使用时请将有关tag的注释取消掉）--------------*/
//template <class DataType>
//void BiTree<DataType>::PosOrderTraverse()
//{
// Stack<TreeNode<DataType>*> S;
// TreeNode<DataType>* p;
// p=root;
// while(p||!S.StackEmpty())
// {
// if(p){S.Push(p); p->tag=true;p=p->lchild;}
// else{
// S.GetTop(p);
// if(p->rchild&&!p->rchild->tag){
// p=p->rchild;S.Push(p);p->tag=true;p=p->lchild;
// }
// else{S.Pop(p);cout<<p->data<<" ";p=NULL;}
// }
// }
// S.DestroyStack();
//}
/*-------- 非递归------层次遍历二叉树 --------------*/
template <class DataType>
void BiTree<DataType>::LevelOrderTraverse()
{
Queue<TreeNode<DataType>*> qu;
TreeNode<DataType>* p;
qu.EnQueue(root);
while(!qu.QueueEmpty()){
qu.DeQueue(p);
cout<<p->data<<" ";
if (p->lchild!= NULL) qu.EnQueue(p->lchild);
if (p->rchild!= NULL) qu.EnQueue(p->rchild);
}
}
#endif
// 名 称 (Unit Name): Stack.h 栈头文件
// 作 者 (Author ): Hector(张伟)
// 邮 箱 (E-mail ): ourys@qq.com
// 支 持 (Support ): http://www.ourys.com
// 备 注 (Remarks ):
//////////////////////////////////////////////////////////////////////////////*/
#ifndef _STACK_H
#define _STACK_H
#define STACK_INIT_SIZE 100 //初始栈的最大长度
#define STACKINCREMENT 10 //每次新增的栈的长度
template
class Stack{
public:
Stack();
void Push(DataType e); //插入为e的新栈顶元素
int Pop(DataType &e); //删除栈顶元素
int GetTop(DataType &e); //取出栈顶元素
int StackEmpty(); //判断栈是否为空：空返回1
~Stack(); //栈被销毁
private:
DataType *base; //栈尾
DataType *top; //栈顶
int stacksize;
};
/*———— 构造函数，创建一个新的空栈 ————–*/
template
Stack::Stack()
{
if(!(base=(DataType*)malloc(STACK_INIT_SIZE*sizeof(DataType)))) exit(1);
top=base;
stacksize=STACK_INIT_SIZE;
}
/*——– 插入为e的新栈顶元素 ————–*/
template
void Stack::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
int Stack::Pop(DataType &e)
{
if(top==base) return 0;
e=*–top;
return 1;
}
/*——– 取出栈顶元素 ————–*/
template
int Stack::GetTop(DataType &e)
{
if(top==base) return 0;
e=*(top-1);
return 1;
}
/*———— 判断栈是否为空：空返回1 ————–*/
template
int Stack::StackEmpty()
{
return top==base? 1:0;
}
/*———— 销毁栈 ————–*/
template
Stack::~Stack()
{
free(base);
}
#endif
/*//////////////////////////////////////////////////////////////////////////////
// 名 称 (Unit Name): main.cpp 栈头基本测试文件
// 作 者 (Author ): Hector(张伟)
// 邮 箱 (E-mail ): ourys@qq.com
// 支 持 (Support ): http://ourys.com
// 备 注 (Remarks ):
//////////////////////////////////////////////////////////////////////////////*/
#include
using namespace std;
#include “Stack.h”
int main()
{
Stack my;
int a;
for(int i=0;i<12;i++) my.Push(i);
for(int i=0;i<12;i++)
{
my.Pop(a);
cout<
}
return 0;
}
/*---------------- 基本测试文件 -------*/
#include<iostream>
using namespace std;
#include "BiTree.h"
int main(void)
{
BiTree<char> my;
my.CreateBiTree();
my.PreROrderTraverse();
cout<<endl;
my.PreOrderTraverse();
cout<<endl;
my.InOrderTraverse();
cout<<endl;
my.InROrderTraverse();
cout<<endl;
my.PosROrderTraverse();
cout<<endl;
my.PosOrderTraverse();
cout<<endl;
my.LevelOrderTraverse();
return 0;
}
