[CODE=cplusplus]
/*//////////////////////////////////////////////////////////////////////////////
// 名 称 (Unit Name): BiTree.h 二叉树头文件
// 作 者 ( Author ): Hector(张伟)
// 邮 箱 ( E-mail ): ourys@qq.com
// 支 持 ( Support ): http://www.ourys.com
// 备 注 ( 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 BiTree; //友元类引用申明
/*——– 树的节点定义，将BiTree定义为友元类，便于对其操作 ———–*/
template
class TreeNode
{
TreeNode():lchild(NULL),rchild(NULL){}
friend class BiTree;
private:
DataType data;
TreeNode *lchild,*rchild;
//bool tag; //后序遍历时用的标志域
};
/*——– 二叉树树开始 ———–*/
template
class BiTree{
public:
void CreateBiTree(); //创建根节点——主过程
void CreateBiTree(TreeNode* &p); //创建节点函数—-子过程
void PreROrderTraverse(); //递归——先序遍历二叉树—主过程
void PreROrderTraverse(TreeNode* p); //递归——先序遍历二叉树—子过程
void InROrderTraverse(); //递归——中序遍历二叉树—主过程
void InROrderTraverse(TreeNode* p); //递归——中序遍历二叉树—子过程
void PosROrderTraverse(); //递归——后序遍历二叉树—主过程
void PosROrderTraverse(TreeNode* p); //递归——后序遍历二叉树—子过程
void PreOrderTraverse(); //非递归——中序遍历二叉树
void InOrderTraverse(); //非递归——中序遍历二叉树
void PosOrderTraverse(); //非递归——后序遍历二叉树
void LevelOrderTraverse(); //非递归——层次遍历二叉树
protected:
TreeNode* root; //树根
DataType temp; //代表元素为空的符号
};
/*——– 创建根节点—-主过程————–*/
template
void BiTree::CreateBiTree()
{
cout<<"请输入代表元素为空的符号:";
cin>>temp; //若换输入方式，以上三句可以去掉
if(!(root=(TreeNode*)malloc(sizeof(TreeNode)))) exit(1);
cout<<"请输入数据:"< CreateBiTree(root);
}
/*——–创建节点函数—-子过程————–*/
template
void BiTree::CreateBiTree(TreeNode* &p)
{
TreeNode* px;
if(!(px=(TreeNode*)malloc(sizeof(TreeNode)))) 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
void BiTree::PreROrderTraverse()
{
PreROrderTraverse(root);
}
/*——– 递归——先序遍历二叉树—子过程 ————–*/
template
void BiTree::PreROrderTraverse(TreeNode* p)
{
if(p){
cout< data<<" ";
PreROrderTraverse(p->lchild);
PreROrderTraverse(p->rchild);
}
}
/*——– 递归——中序遍历二叉树—主过程 ————–*/
template
void BiTree::InROrderTraverse()
{
InROrderTraverse(root);
}
/*——– 递归——中序遍历二叉树—子过程 ————–*/
template
void BiTree::InROrderTraverse(TreeNode* p)
{
if(p){
InROrderTraverse(p->lchild);
cout< data<<" ";
InROrderTraverse(p->rchild);
}
}
/*——– 递归——后序遍历二叉树—主过程 ————–*/
template
void BiTree::PosROrderTraverse()
{
PosROrderTraverse(root);
}
/*——– 递归——后序遍历二叉树—子过程 ————–*/
template
void BiTree::PosROrderTraverse(TreeNode* p)
{
if(p){
PosROrderTraverse(p->lchild);
PosROrderTraverse(p->rchild);
cout< data<<" ";
}
}
/*——– 非递归——前序遍历二叉树————–*/
template
void BiTree::PreOrderTraverse()
{
Stack*> S;
TreeNode* p;
p=root;
while(p||!S.StackEmpty()){
if(p){S.Push(p);cout< data<<" "; p=p->lchild;}
else{
S.Pop(p);
p=p->rchild;
}
}
S.DestroyStack();
}
/*——– 非递归——中序遍历二叉树————–*/
template
void BiTree::InOrderTraverse()
{
Stack*> S;
TreeNode* p;
p=root;
while(p||!S.StackEmpty()){
if(p){S.Push(p); p=p->lchild;}
else{
S.Pop(p);
cout< data<<" ";
p=p->rchild;
}
}
S.DestroyStack();
}

/*——–非递归——后序遍历二叉树（没有使用标志域）————–*/
template
void BiTree::PosOrderTraverse()
{
Stack*> S;
TreeNode* p;
TreeNode* 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< data<<" ";r=p;p=NULL;}
}
}
S.DestroyStack();
}

/*——–非递归——后序遍历二叉树（运用标志域，使用时请将有关tag的注释取消掉）————–*/
//template
//void BiTree::PosOrderTraverse()
//{
// Stack*> S;
// TreeNode* 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< data<<" ";p=NULL;}
// }
// }
// S.DestroyStack();
//}
/*——– 非递归——层次遍历二叉树 ————–*/
template
void BiTree::LevelOrderTraverse()
{
Queue*> qu;
TreeNode* p;
qu.EnQueue(root);
while(!qu.QueueEmpty()){
qu.DeQueue(p);
cout< data<<" ";
if (p->lchild!= NULL) qu.EnQueue(p->lchild);
if (p->rchild!= NULL) qu.EnQueue(p->rchild);
}
}
#endif

/*—————- http://ourys.com原创，做人要厚道，转帖请标明来处 ——- Author:Hector ——-*/

/*—————- 基本测试文件 ——-*/

#include
using namespace std;
#include “BiTree.h”
int main(void)
{
BiTree my;
my.CreateBiTree();
my.PreROrderTraverse();
cout< my.PreOrderTraverse();
cout< my.InOrderTraverse();
cout< my.InROrderTraverse();
cout< my.PosROrderTraverse();
cout< my.
PosOrderTraverse();

cout< my.LevelOrderTraverse();
return 0;
}
[/CODE]