这个代码是老师给的,但是里面那个字符数组我不是很懂,请问这个的主函数怎么写?
3条回答 默认 最新
- weixin_40346192 2017-11-13 06:15关注
有两种方法递归和非递归
二叉树遍历递归:
=====================================main============================
#include
#include "Bitree.h"
using namespace std;
bool PrintElement(char e)
{
cout< return true;
}
int main()
{
BiTree T;
BiTNode *r=T.GetRoot();
T.CreateBiTree(r);
T.SetRoot(r);
cout<<"先序遍历序列为:";
T.PreOrderTraverse(r ,PrintElement);
cout<<"\n中序遍历序列为: ";
T.InOrderTraverse(r ,PrintElement);
cout<<"\n后序遍历序列为: ";
T.PostOrderTraverse(r ,PrintElement);
return 0;
}==================================Bitree.h===================================
#include
using namespace std;
struct BiTNode
{
char data ;
struct BiTNode lchild , *rchild ;
};
template
class BiTree
{
public:
BiTree();
void CreateBiTree(BiTNode &SubTree);
bool PreOrderTraverse(BiTNode* &SubTree,bool(* Visit)(TElemType e));
bool InOrderTraverse(BiTNode* &SubTree,bool(* Visit)(TElemType e));
bool PostOrderTraverse(BiTNode* &SubTree,bool(* Visit)(TElemType e));
BiTNode GetRoot(){ return root;}
void SetRoot(BiTNode * &SubTree){ root=SubTree;}
private:
BiTNode root;
};template
BiTree::BiTree() //建空的二叉树
{
root = NULL;
}
template
void BiTree::CreateBiTree(BiTNode* &SubTree)
{
char ch;
cin>>ch;
if(ch == '*') SubTree=NULL;
else
{
SubTree = new BiTNode;
SubTree->data=ch;
CreateBiTree( SubTree->lchild );
CreateBiTree( SubTree->rchild );
}
}template
bool BiTree:: PreOrderTraverse (BiTNode* &SubTree,bool(* Visit)(TElemType e))
{
if(SubTree){
if( Visit(SubTree->data) )
if( PreOrderTraverse( SubTree->lchild ,Visit) )
if( PreOrderTraverse( SubTree->rchild ,Visit) )
return true;
cout<<"ERROR";
}else return true;
} //PreOrderTraverse先序遍历,递归template
bool BiTree:: InOrderTraverse ( BiTNode* &SubTree,bool(* Visit)(TElemType e))
{
if( SubTree ){
if( InOrderTraverse( SubTree->lchild ,Visit) )
if( Visit(SubTree->data) )
if( InOrderTraverse( SubTree->rchild ,Visit) )
return true;
cout<<"ERROR";
}else return true;
} //InOrderTraverse中序遍历,递归template
bool BiTree:: PostOrderTraverse (BiTNode* &SubTree,bool(* Visit)(TElemType e))
{
if(SubTree){
if( PostOrderTraverse( SubTree->lchild ,Visit) )
if( PostOrderTraverse( SubTree->rchild ,Visit) )
if( Visit(SubTree->data) )
return true;
cout<<"ERROR";
}else return true;
}//PostOrderTraverse后序遍历,递归二叉树遍历非递归:
============================================main============================================
#include
#include "Bitree.h"
using namespace std;
bool PrintElement(char e)
{
cout< return true;
}
int main()
{
BiTree T;
BiTNode *r=T.Getroot();
T.CreateBiTree(r);
T.SetRoot(r);
cout<<"先序非递归遍历序列为:";
T.NonRecurPreOrder(PrintElement);
cout<<"\n中序非递归遍历序列为: ";
T.NonRecurInOrder(PrintElement);
cout<<"\n后序非递归遍历序列为: ";
T.NonRecurPostOrder(PrintElement);
return 0;
}
=======================================SqStack.h===============================
#include
using namespace std;
template
class SqStack
{
protected:
// 顺序栈的数据成员:
int count; // 元素个数
int maxSize; // 栈最大元素个数
ElemType *elems; // 元素存储空间
public:
// 抽象数据类型方法声明及重载编译系统默认方法声明:
SqStack(int size=8); // 构造函数模板
virtual ~SqStack(); // 析构函数模板
void Push(ElemType &e); // 入栈
ElemType Pop(ElemType &e); // 出栈
bool Empty();
};// 顺序栈类模板的实现部分
template
SqStack::SqStack(int size)
// 操作结果:构造一个最大元素个数为size的空栈
{
elems = NULL; // 未分配存储空间前,elems为空
maxSize = size;// 最大元素个数 // 释放存储空间
if (elems != NULL) delete []elems;
elems = new ElemType[maxSize]; // 分配存储空间
count = 0;
}template
SqStack::~SqStack()
// 操作结果:销毁栈
{
delete []elems; // 释放存储空间
}template
void SqStack::Push(ElemType &e)
// 操作结果:将元素e追加到栈顶,如成功则返加SUCCESS,如栈已满将返回OVER_FLOW
{
if (count == maxSize)
{ // 栈已满
cout<<"OVER_FLOW";
}
else
{ // 操作成功
elems[count++] = e; // 将元素e追加到栈顶
}
}template
ElemType SqStack::Pop(ElemType &e)
// 操作结果:如栈非空,删除栈顶元素,并用e返回栈顶元素,返回SUCCESS,否则
// 返回UNDER_FLOW
{
if (count == 0)
{ // 栈空
cout<<"UNDER_FLOW";
return false;
}
else
{ // 操作成功
e = elems[count - 1]; // 用e返回栈顶元素
count--;
return e;
}
}template
bool SqStack::Empty()
// 操作结果:如栈为空,则返回true,否//则返回false
{
return count == 0;
}====================================Bitree.h===================================
#include
#include "SqStack.h"
using namespace std;
struct BiTNode
{
char data ;
struct BiTNode lchild , *rchild ;
bool rightSubTreeVisited;
};
template
class BiTree
{
public:
BiTree();
void CreateBiTree(BiTNode *&SubTree);
BiTNode * Getroot(){ return root;}
void SetRoot(BiTNode * &SubTree){ root=SubTree;}
bool BiTree::NonRecurPreOrder(bool( Visit)(TElemType e));
bool BiTree::NonRecurInOrder(bool(* Visit)(TElemType e));
bool BiTree::NonRecurPostOrder(bool(* Visit)(TElemType e));
private:
BiTNode* root;
};template
BiTree::BiTree() //建空的二叉树
{
root = NULL;
}template
void BiTree::CreateBiTree(BiTNode &SubTree)
{
char ch;
cin>>ch;
if(ch == '') SubTree=NULL;
else
{
SubTree = new BiTNode;
SubTree->data=ch;
CreateBiTree( SubTree->lchild );
CreateBiTree( SubTree->rchild );
}
}template
bool BiTree::NonRecurPreOrder(bool(* Visit)(TElemType e))
{
SqStack S;
BiTNode* p;
p = root;
while( p || !S.Empty())
{
if(p)
{ //遇到一个结点if( !Visit(p->data) ) return false; //访问结点 S.Push(p); //压入堆栈 p=p->lchild; //进入左子树 } else { S.Pop(p); p=p->rchild; } } return true;
}
template
bool BiTree::NonRecurInOrder(bool(* Visit)(TElemType e))
{
SqStack S;
BiTNode* p;
p = root;while( p || !S.Empty()) { if(p) { S.Push(p); p = p->lchild; } else { S.Pop(p); if( !Visit(p->data) ) return false; //访问结点 p=p->rchild; } } //while return true;
}
template
bool BiTree::NonRecurPostOrder(bool(* Visit)(TElemType e))
{
SqStack S;
BiTNode* p;
p = root;
while( p || !S.Empty())
{
while(p)
{ //找到最左的结点
S.Push(p);
p=p->lchild;
}
S.Pop(p);
while( p->rightSubTreeVisited==true )
{ //右子树已遍历
if( !Visit(p->data) ) return false; //访问结点
if( !S.Empty() )
{
S.Pop(p);
}
else
{
return true;
}
}
//右子树未遍历,遍历右子树
p->rightSubTreeVisited=true;
S.Push(p); /*很重要*/
p=p->rchild;
}
return true;
}本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报