数据结构中二叉树的应用

Question

这个代码是老师给的，但是里面那个字符数组我不是很懂，请问这个的主函数怎么写?

Answer 1

有两种方法递归和非递归
二叉树遍历递归:
=====================================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;

}