二叉树先序中序后序层次遍历递归非递归
#include
#include
#define NULL 0
#define LEN_T sizeof(BTNode) #define LEN_Q sizeof(QNode) #define LEN_S 100
typedef char ElemType;
typedef struct BTNode
{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,*BTree;
typedef struct QNode
{
BTree data;
struct QNode *next; }QNode,*Queue;
typedef struct StackElemType {
BTree data;
int f;//f=0：遍历左子树 f=1：遍历右子树
}StackElemType;
void CreateTree(BTree *T) {
char c;
c=getchar();
if (c=='#')
(*T)=NULL;
else
{
(*T)=(BTree)malloc(LEN_T);
CreateTree(&(*T)->lchild);
(*T)->data=c;
CreateTree(&(*T)->rchild);
}
}
void Xian(BTree T)
{
if(T)
{
printf("%2c",T->data);
Xian(T->lchild);
Xian(T->rchild);
}
}
void D_Xian(BTree T)
{
BTree p=T,Stack[LEN_S];
int top=0;
do{
while(p)
{
printf("%2c",p->data);
Stack[top++]=p;
p=p->lchild;
}
if(top>0)
{
p=Stack[--top];
p=p->rchild;
}
}while(top>0||p!=NULL); }
void Zhong(BTree T)
{
if(T)
{
Zhong(T->lchild);
printf("%2c",T->data);
Zhong(T->rchild);
}
}
void D_Zhong(BTree T)
{
BTree p=T,Stack[LEN_S];
int top=0;
do{
while(p)
{
Stack[top++]=p;
p=p->lchild;
}
if(top>0)
{
p=Stack[--top];
printf("%2c",p->data);
p=p->rchild;
}
}while(top>0 || p); }
void Hou(BTree T)
{
if(T)
{
Hou(T->lchild);
Hou(T->rchild);
printf("%2c",T->data);
}
}
void D_Hou(BTree T)
{
StackElemType Stack[LEN_S];
BTree p=T;
int top=0;
do{
while(p)
{
Stack[top].f=0;
Stack[top].data=p;
p=p->lchild;
top++;
}
if(top>0)
{
while(Stack[top-1].f==1)
{
p=Stack[--top].data;
printf("%2c",p->data);
}
if(top>0)
{
Stack[top-1].f=1;
p=Stack[top-1].data;
p=p->rchild;
}
}
}while(top>0);
}
//队列开始
void InitQueue(Queue *front,Queue *rear)
{
(*front)=(*rear)=(Queue)malloc(LEN_Q);
}
void EnQueue(Queue *rear,BTree p) {
Queue q;
q=(Queue)malloc(LEN_Q);
q->data=p;
q->next=NULL;
(*rear)->next=q;
(*rear)=q;
}
void DeQueue(Queue *front,Queue *rear,BTree *e)
{
Queue q;
q=(*front)->next;
*e=q->data;
(*front)->next=q->next;
if((*rear)==q)
(*rear)=(*front);
free(q);
}
//队列结束
int Ceng(BTree T)
{
Queue front,rear;
BTree p;
if(!T)
return 0;
InitQueue(&front,&rear);
p=T;
EnQueue(&rear,p);
while(front!=rear)
{
DeQueue(&front,&rear,&p);
printf("%2c",p->data);
if(p->lchild!=NULL)
EnQueue(&rear,p->lchild);
if(p->rchild!=NULL)
EnQueue(&rear,p->rchild);
}
return 1;
}
void S_Ceng(BTree T)
{
BTree Queue[LEN_S],p;
int front,rear;
front=rear=0;
if(T)
{
p=T;
Queue[rear++]=p;
while(front!=rear)
{
p=Queue[front++];
printf("%2c",p->data);
if(p->lchild!=NULL)
Queue[rear++]=p->lchild;
if(p->rchild!=NULL)
Queue[rear++]=p->rchild;
}
}
}
void main()
{
BTree T=NULL;
printf("先序输入二叉树:\n");
CreateTree(&T);
printf("先序遍历:\n");
Xian(T);
printf("\n先序遍历(非递归):\n");
D_Xian(T);
printf("\n中序遍历:\n");
Zhong(T);
printf("\n中序遍历(非递归):\n");
D_Zhong(T);
printf("\n后序遍历:\n");
Hou(T);
printf("\n后序遍历(非递归):\n");
D_Hou(T);
printf("\n层次遍历(链式):\n");
Ceng(T);
printf("\n层次遍历(顺序):\n");
S_Ceng(T);
本文档为【二叉树先序中序后序层次遍历递归非递归】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483