先序遍历（ 用递归和非递归的方法一起都要）

Question

任务：
要求能够输入树的各个结点，并能够输出遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、遍历序列的函数

Answer 1

//声明类BiTree及定义结构BiNode,文件名为bitree.h
#ifndef BITREE_H
#define BITREE_H

template <class T>
struct BiNode //二叉树的结点结构
{
T data;
BiNode<T> *lchild, *rchild;
};

template <class T>
class BiTree
{
public:
BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入
~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间
BiNode<T>* Getroot(); //获得指向根结点的指针
void PreOrder(BiNode<T> *root); //前序遍历二叉树
void InOrder(BiNode<T> *root); //中序遍历二叉树
void PostOrder(BiNode<T> *root); //后序遍历二叉树
void LeverOrder(BiNode<T> *root); //层序遍历二叉树
private:
BiNode<T> *root; //指向根结点的头指针
BiNode<T> *Creat( ); //有参构造函数调用
void Release(BiNode<T> *root); //析构函数调用
};
#endif

//定义类中的成员函数，文件名为bitree.cpp
#include<iostream>
#include<string>
#include"bitree.h"
using namespace std;

/*
*前置条件：二叉树不存在
*输 入：无
*功 能：构造一棵二叉树
*输 出：无
*后置条件：产生一棵二叉树
*/
template<class T>
BiTree<T>::BiTree( )
{
this->root = Creat( );
}
/*
*前置条件：二叉树已存在
*输 入：无
*功 能：释放二叉链表中各结点的存储空间
*输 出：无
*后置条件：二叉树不存在
*/
template<class T>
BiTree<T>::~BiTree(void)
{
Release(root);
}
/*
*前置条件：二叉树已存在
*输 入：无
*功 能：获取指向二叉树根结点的指针
*输 出：指向二叉树根结点的指针
*后置条件：二叉树不变
*/
template<class T>
BiNode<T>* BiTree<T>::Getroot( )
{
return root;
}
/*
*前置条件：二叉树已存在
*输 入：无
*功 能：前序遍历二叉树
*输 出：二叉树中结点的一个线性排列
*后置条件：二叉树不变
*/
template<class T>
void BiTree<T>::PreOrder(BiNode<T> *root)
{
if(root==NULL) return;
else{
cout<<root->data<<" ";
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}

/*
*前置条件：二叉树已存在
*输 入：无
*功 能：中序遍历二叉树
*输 出：二叉树中结点的一个线性排列
*后置条件：二叉树不变
*/
template <class T>
void BiTree<T>::InOrder (BiNode<T> *root)
{
if (root==NULL) return; //递归调用的结束条件
else{
InOrder(root->lchild); //中序递归遍历root的左子树
cout<<root->data<<" "; //访问根结点的数据域
InOrder(root->rchild); //中序递归遍历root的右子树
}
}
/*
*前置条件：二叉树已存在
*输 入：无
*功 能：后序遍历二叉树
*输 出：二叉树中结点的一个线性排列
*后置条件：二叉树不变
*/
template <class T>
void BiTree<T>::PostOrder(BiNode<T> *root)
{
if (root==NULL) return; //递归调用的结束条件
else{
PostOrder(root->lchild); //后序递归遍历root的左子树
PostOrder(root->rchild); //后序递归遍历root的右子树
cout<<root->data<<" "; //访问根结点的数据域
}
}

/*
*前置条件：二叉树已存在
*输 入：无
*功 能：层序遍历二叉树
*输 出：二叉树中结点的一个线性排列
*后置条件：二叉树不变
*/
template <class T>
void BiTree<T>::LeverOrder(BiNode<T> *root)
{
const int MaxSize = 100;

int front = 0;
int rear = 0; //采用顺序队列，并假定不会发生上溢

BiNode<T>* Q[MaxSize];
BiNode<T>* q;

if (root==NULL) return;
else{
Q[rear++] = root;
while (front != rear)
{
q = Q[front++];
cout<<q->data<<" ";
if (q->lchild != NULL) Q[rear++] = q->lchild;
if (q->rchild != NULL) Q[rear++] = q->rchild;
}
}
}

/*
*前置条件：空二叉树
*输 入：数据ch;
*功 能：初始化一棵二叉树,构造函数调用
*输 出：无
*后置条件：产生一棵二叉树
*/
template <class T>
BiNode<T>* BiTree<T>::Creat( )
{
BiNode<T>* root;
T ch;
cout<<"请输入创建一棵二叉树的结点数据"<<endl;
cin>>ch;
if (ch=="#") root = NULL;
else{
root = new BiNode<T>; //生成一个结点
root->data=ch;
root->lchild = Creat( ); //递归建立左子树
root->rchild = Creat( ); //递归建立右子树
}
return root;
}

/*
*前置条件：二叉树已经存在
*输 入：无
*功 能：释放二叉树的存储空间，析构函数调用
*输 出：无
*后置条件：二叉树不存在
*/
template<class T>
void BiTree<T>::Release(BiNode<T>* root)
{
if (root != NULL){
Release(root->lchild); //释放左子树
Release(root->rchild); //释放右子树
delete root;
}
}

//二叉树的主函数，文件名为bitreemain.cpp
#include<iostream>
#include<string>
#include"bitree.cpp"
using namespace std;

void main()
{
BiTree<string> bt; //创建一棵树
BiNode<string>* root = bt.Getroot( ); //获取指向根结点的指针

cout<<"------前序遍历------ "<<endl;
bt.PreOrder(root);
cout<<endl;
cout<<"------中序遍历------ "<<endl;
bt.InOrder(root);
cout<<endl;
cout<<"------后序遍历------ "<<endl;
bt.PostOrder(root);
cout<<endl;
cout<<"------层序遍历------ "<<endl;
bt.LeverOrder(root);
cout<<endl;
}
追问

搞这么多啊，您很辛苦的，但是怎么没非递归啊？

Answer 2

//定义二叉树链式结构
typedef struct BitNode
{
char data; //数据域
struct BitNode *lchild,*rchild;//左右指针域
}BitNode,*BiTree;

//二叉树建立(递归算法)
BiTree CreatBiTree()
{
BiTree bt;
bt=(BiTree)malloc(sizeof(BitNode));
if(bt==NULL)
{
printf("声请空间错误\n!");
exit(1);
}
//按先序录入
scanf("%c",&bt->data);//输入ABD@F@@EG@@H@@C@@
if(bt->data=='@')
return NULL;
bt->lchild=CreatBiTree();//建立左子树
bt->rchild=CreatBiTree();//建立右子树
return bt;
}

//递归实现先序遍历
void Preorder(BiTree bt)
{
if(bt==NULL) return;
//如果不为空
printf("%c ",bt->data);//输出根节点值
Preorder(bt->lchild); //递归遍历左子树
Preorder(bt->rchild); //递归遍历右子树
}
//递归实现中序遍历
void Inorder(BiTree bt)
{
if(bt==NULL) return;
//如果不为空
Inorder(bt->lchild); //递归遍历左子树
printf("%c ",bt->data); //输出根节点值
Inorder(bt->rchild); //递归遍历右子树

}

//递归实现后序遍历
void Postorder(BiTree bt)
{
if(bt==NULL) return;
//如果不为空
Postorder(bt->lchild); //递归遍历左子树
Postorder(bt->rchild); //递归遍历右子树
printf("%c ",bt->data); //输出根节点值

}