/*实验三：二叉树遍历操作验证*/
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<map>
#include<queue>
#include<math.h>
using namespace std;
#define OK 1
createBiTree(T->lchild);//构造左子树
createBiTree(T->rchild);//构造右子树
}
}
//递归方法先序遍历二叉树
void preOrderTraverse(BiTree T)
{
if(T)//若非空
{
if(T->data)
{//输出
printf("%c",T->data);
}
preOrderTraversFra bibliotek(T->lchild);
preOrderTraverse(T->rchild);
}
}
//递归方法中序遍历二叉树
void inOrderTraverse(BiTree T)
{
if(T)//若非空
{
preOrderTraverse(T->lchild);
if(T->data)
{
if(T)//若非空
{
preOrderTraverse(T->lchild);
preOrderTraverse(T->rchild);
if(T->data)
{//输出
printf("%c",T->data);
}
}
}
//层序遍历二叉树
void LevelTraverse(BiTree T)
{
queue<BiTree> q;//建队
inOrderTraverse(T);
cout<<endl;
cout<<"递归后序遍历:";
postOrderTraverse(T);
cout<<endl;
cout<<"层序遍历：";
LevelTraverse(T);
cout<<endl;
cout<<"非递归先序遍历：";
stackPreOrderTraverse(T);
#include<stdlib.h>
#include<stack>
#include<map>
#include<queue>
#include<math.h>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
int LeafNum;//叶子结点个数
{
BiTree T;//定义结点
int layer=0;//层数
while(true)
{
cout<<"输入二叉树结点值空格表示空树："<<endl;
createBiTree(T);
cout<<"递归先序遍历:";
preOrderTraverse(T);
cout<<endl;
cout<<"递归中序遍历:";
{
stack<BiTree> s;//建栈
map<BiTree,bool> m;//标记结点是否已经输出
BiTree p;//栈首元素
if(T)//若不是空树
{
s.push(T);//根结点入栈
}
while(!s.empty())
{
while(true)
{//目的：找到后序遍历要输出的结点
while((p=s.top())&&p->lchild&&!m[p->lchild])
if(!T)//分配失败
{
exit(OVERFLOW);
}
T->data=ch;//生成根结点
createBiTree(T->lchild);//构造左子树
createBiTree(T->rchild);//构造右子树
}
}
//递归方法先序遍历二叉树
void preOrderTraverse(BiTree T)
//先序输入二叉树结点的值，空格表示空树
void createBiTree(BiTree &T)
{
char ch;//输入结点时用
scanf("%c",&ch);
if(ch==' ')//若输入空格，该值为空,且没有左右孩子
{
T=NULL;
}else{
T=(BiTNode *)malloc(sizeof(BiTNode));//分配结点空间
}
if(p->rchild!=NULL)//若结点的右孩子不空
{
q.push(p->rchild);
}
}
}
//非递归方法前序遍历二叉树
void stackPreOrderTraverse(BiTree T)
{
stack<BiTree> s;//建栈
s.push(T);//根结点入栈
BiTree p;//栈首元素
hl=PostTreeDepth(T->lchild); //求左子树的深度
hr=PostTreeDepth(T->rchild); //求右子树的深度
max=hl>hr?hl:hr; //得到左、右子树深度较大者
return(max+1); //返回树的深度
}
else
return(0); //如果是空树，则返回0
void stackPreOrderTraverse(BiTree T)
q.pop(); //首元素出队
cout<<p->data<<" "; //输出结点的值
if(p->lchild!=NULL) //若结点的左孩子不空
{
q.push(p->lchild);
}
if(p->rchild!=NULL)//若结点的右孩子不空
{
q.push(p->rchild);
}
}
}
//非递归方法前序遍历二叉树
{//若左孩子未输出，将左孩子入栈，直到尽头，不包括空指针
s.push(p->lchild);
}
if((p=s.top())&&p->rchild&&!m[p->rchild])
{//若最左孩子的右孩子未输出且非空，则入栈
s.push(p->rchild);
}else{
break;//找到结点跳出循环
{
int i;
if(T==NULL) return;
PrintTree(T->rchild,nLayer+1);
for(i=0;i<nLayer;i++)
printf(" ");
printf("%c\n",T->data);
PrintTree(T->lchild,nLayer+1);
}
//叶子结点的个数以及元素
}
}
if((p=s.top())&&!m[p])
{
printf("%c",p->data);
m[p]=true;//标记已经输出
s.pop();//退栈
}
}
}
//后序遍历求二叉树的高度递归算法
int PostTreeDepth(BiTree T)
{
int hl,hr,max;
if(T!=NULL)
{
scanf("%c",&ch);
if(ch==' ')//若输入空格，该值为空,且没有左右孩子
{
T=NULL;
}else{
T=(BiTNode *)malloc(sizeof(BiTNode));//分配结点空间
if(!T)//分配失败
{
exit(OVERFLOW);
}
T->data=ch;//生成根结点
{//输出
printf("%c",T->data);
}
preOrderTraverse(T->rchild);
}
}
//递归方法后序遍历二叉树
void postOrderTraverse(BiTree T)
{
if(T)//若非空
{
preOrderTraverse(T->lchild);
preOrderTraverse(T->rchild);
while(!s.empty())
{
while((p=s.top())&&p)
{
printf("%c",p->data);
s.push(p->lchild);//左孩子入栈,直到走到尽头