#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define MAXLEN 100
#define ERROR 0
#define OVERFLOW -2
typedef enum{Link,Thread} PointerTag;
typedef char TElemType;
typedef int Status;
typedef struct BiTNode
{ // 结点结构
TElemType data;
PointerTag ltag,rtag;
struct BiTNode *lchild, *rchild;// 左右孩子指针
}
BiTNode,*BiTree; //以下是建立二叉树存储结构
Status CreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch=='#') T=NULL;
else{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}return OK;
} // CreateBiTree
void Preorder(BiTree T)
{
if(T)
{
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
//非递归先序遍历
void pre_order(BiTree b)
{
BiTree stack[100],p;
int top;
if (b!=NULL)
{
top=1; //根结点入栈
stack[top]=b;
while (top>0) //栈不为空时循环
{
p=stack[top]; //退栈并访问该结点
top--;
printf("%c",p->data);
if (p->rchild!=NULL) //右孩子入栈
{
top++;
stack[top]=p->rchild;
}
if (p->lchild!=NULL) //左孩子入栈
{
top++;
stack[top]=p->lchild;
}
}
}
}
void Inorder(BiTree T)
{ // 中序遍历二叉树
if(T)
{
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
void in_order( BiTree b)
{
BiTree stack[100],p;
int top=0;
p=b;
do
{
while(p!=NULL) //扫描所有左结点
{
top++;
stack[top]=p;
p=p->lchild;
}
if (top>0)
{
p=stack[top];
//p所指结点为无左子树的结点或其左子树已遍历过
top--;
printf("%c",p->data); //访问结点
p=p->rchild; //扫描右子树
}
} while (p!=NULL || top!=0);
}
void Postorder(BiTree T)
{ // 后序遍历二叉树
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}
void post_order(BiTree b)
{
BiTree stack[100],p;
int tag[100],top=0;
p=b;
do
{
while(p!=NULL) //扫描左结点
{
top++;
stack[top]=p;
tag[top]=0;
p=p->lchild;
}
//p所指结点为无左子树的结点或其左子树已遍历过
while((top>0) && tag[top]==1)
{
printf("%c",stack[top]->data); //访问结点
top--;
}
p=stack[top];
if((top>0)&&(tag[top]==0))
{
p=p->rchild; //扫描右子树
tag[top]=1; //表示当前结点的右子树已访问过
}
} while(p!=NULL || top!=0);
}
void levelorder(BiTree b)
{
struct nodeq
{
BiTree vec[100];
int f,r;
}q;
q.f=0;
q.r=0;
if (b!=NULL)
printf("%c",b->data);
q.vec[q.r]=b;
q.r=q.r+1;
while (q.f<q.r)
{
b=q.vec[q.f];
q.f=q.f+1;
if (b->lchild!=NULL)
{
printf("%c",b->lchild->data);
q.vec[q.r]=b->lchild;
q.r=q.r+1;
}
if (b->rchild!=NULL)
{
printf("%c",b->rchild->data);
q.vec[q.r]=b->rchild;
q.r=q.r+1;
}
}
}
//以下是求二叉树的深度
int Depth(BiTree T )
{
int depthval,depthLeft,depthRight;
if(!T) depthval=0;
else
{
depthLeft = Depth(T->lchild);
depthRight = Depth(T->rchild);
if(depthLeft>depthRight)
depthval = 1+depthLeft;
else depthval = 1+depthRight;
}
return depthval;
}
int main()
{
int s=0,d;
BiTree T=NULL;
printf("按先序扩展序列建立二叉树:");
CreateBiTree(T);
printf("\n 树的深度为:%d\n",Depth(T));
printf("\n");
printf("层序遍历:");
levelorder(T);
printf("\n");
printf("先序遍历(递归):");
Preorder(T);
printf("\n");
printf("先序遍历(非递归):");
pre_order(T);
printf("\n");
printf("中序遍历(递归):");
Inorder(T);
printf("\n");
printf("中序遍历(非递归):");
in_order(T);
printf("\n");
printf("后序遍历(递归):");
Postorder(T);
printf("\n");
printf("后序遍历(非递归):");
post_order(T);
system("pause");
return 0;
}
erchashu.rar_层序遍历算法
版权申诉
181 浏览量
2022-09-20
19:59:45
上传
评论
收藏 2KB RAR 举报
weixin_42651887
- 粉丝: 77
- 资源: 1万+