C语言二叉树先序、中序、后序、层次遍历
C语言二叉树先序、中序、后序、层次遍历
原先看过一遍二叉树的遍历，代码也会写，但最近再次翻看原先的笔记时发现自己写相应的代码卡壳了好久，所以又重新在网上找了相关资料总结了这篇相对来说比较齐全的二叉树遍历程序。二叉树遍历无非是先序遍历(中左右)、中序遍历(左中右)、后序遍历（左右中）、层次遍历。这里对于相应的原理不做介绍，只附带程序。
树的定义
typedef struct BitreeNode
{
char data;
int index;
struct BitreeNode *lchild;
struct BitreeNode *rchild;
}BitreeNode,*Bitree; 栈的定义
typedef struct Stack
{
Bitree data[100];
int top;
}Stack; 队列的定义以及出队、入队、队空判断
typedef struct queue
{
Bitree data[100];
int front;
int rear;
}Queue;
Queue Q;
void init_Queue()
{
Q.front=0;
Q.rear=0;
}
void push(Bitree root)
{
Q.data[Q.rear++]=root;
}
Bitree pop()
{
return Q.data[Q.front++];
}
int isEmpty()
{
return Q.front==Q.rear;
} 1. 递归实现
- 先序遍历
void PreOrder(Bitree root)
{
if(root==NULL)
return;
printf("%c ",root->data);
PreOrder(root->lchild);
PreOrder(root->rchild);
} - 中序遍历
void InOrder(Bitree root)
{
if(root==NULL)
return;
InOrder(root->lchild);
printf("%c ",root->data);
InOrder(root->rchild);
} - 后序遍历
void PostOrder(Bitree root)
{
if(root==NULL)
return;
PostOrder(root->lchild);
PostOrder(root->rchild);
printf("%c ",root->data);
} 2. 非递归实现
- 先序遍历
void PreOrderNonRecursion(Bitree root)
{
Stack S;
S.top=-1;
if(root)
{
Bitree p;
S.data[++S.top]=root;
while(-1 !=S.top)
{
p=S.data[S.top--];
printf("%c ",p->data);
if(p->rchild)
S.data[++S.top]=p->rchild;
if(p->lchild)
S.data[++S.top]=p->lchild;
}
}
} - 中序遍历
void InOrderNonRecursion(Bitree root)
{
Stack s;
s.top=-1;
Bitree p=root;
while(s.top>-1 || p)
{
while(p)
{
s.data[++s.top]=p;
p=p->lchild;
}
p=s.data[s.top--];
printf("%c ",p->data);
p=p->rchild;
}
} - 后序遍历
void PostOrderNonRecursion(Bitree root)
{
Stack s;
s.top=-1;
Bitree p=root;
while(p || s.top !=-1)
{
while(p)
{
p->index=1;
s.data[++s.top]=p;
p=p->lchild;
}
if(s.top!=-1)
{
p=s.data[s.top--];
if(p->index==1) //当前节点第一次访问
{
p->index++;
s.data[++s.top]=p;
p=p->rchild;
}
else if(p->index==2)
{
printf("%c ",p->data);
p=NULL; //防止陷入死循环
}
}
}
} 3.层次遍历
void LevelTraversal(Bitree root)
{
Bitree p=root;
push(p);
while(!isEmpty())
{
p=pop();
printf("%c ",p->data);
if(p->lchild)
push(p->lchild);
if(p->rchild)
push(p->rchild);
}
} 4.完整代码
#include<stdio.h>
#include<stdlib.h>
typedef struct BitreeNode
{
char data;
int index;
struct BitreeNode *lchild;
struct BitreeNode *rchild;
}BitreeNode,*Bitree;
typedef struct Stack
{
Bitree data[100];
int top;
}Stack;
typedef struct queue
{
Bitree data[100];
int front;
int rear;
}Queue;
Queue Q;
void init_Queue()
{
Q.front=0;
Q.rear=0;
}
void push(Bitree root)
{
Q.data[Q.rear++]=root;
}
Bitree pop()
{
return Q.data[Q.front++];
}
int isEmpty()
{
return Q.front==Q.rear;
}
//input in PreOrder way
void createBitree(Bitree*root)
{
char date;
scanf("%c",&date);
if(date=='#')
*root=NULL;
else
{
*root=(Bitree)malloc(sizeof(BitreeNode)); //lchild¡¢rchildÐèÒª·ÖÅäÄÚ´æ
(*root)->data=date;
createBitree(&(*root)->lchild);
createBitree(&(*root)->rchild);
}
}
void PreOrder(Bitree root)
{
if(root==NULL)
return;
printf("%c ",root->data);
PreOrder(root->lchild);
PreOrder(root->rchild);
}
void InOrder(Bitree root)
{
if(root==NULL)
return;
InOrder(root->lchild);
printf("%c ",root->data);
InOrder(root->rchild);
}
void PostOrder(Bitree root)
{
if(root==NULL)
return;
PostOrder(root->lchild);
PostOrder(root->rchild);
printf("%c ",root->data);
}
void PreOrderNonRecursion(Bitree root)
{
Stack S;
S.top=-1;
if(root)
{
Bitree p;
S.data[++S.top]=root;
while(-1 !=S.top)
{
p=S.data[S.top--];
printf("%c ",p->data);
if(p->rchild)
S.data[++S.top]=p->rchild;
if(p->lchild)
S.data[++S.top]=p->lchild;
}
}
}
void InOrderNonRecursion(Bitree root)
{
Stack s;
s.top=-1;
Bitree p=root;
while(s.top>-1 || p)
{
while(p)
{
s.data[++s.top]=p;
p=p->lchild;
}
p=s.data[s.top--];
printf("%c ",p->data);
p=p->rchild;
}
}
void PostOrderNonRecursion(Bitree root)
{
Stack s;
s.top=-1;
Bitree p=root;
while(p || s.top !=-1)
{
while(p)
{
p->index=1;
s.data[++s.top]=p;
p=p->lchild;
}
if(s.top!=-1)
{
p=s.data[s.top--];
if(p->index==1) //当前节点第一次访问
{
p->index++;
s.data[++s.top]=p;
p=p->rchild;
}
else if(p->index==2)
{
printf("%c ",p->data);
p=NULL; //防止陷入死循环
}
}
}
}
void LevelTraversal(Bitree root)
{
Bitree p=root;
push(p);
while(!isEmpty())
{
p=pop();
printf("%c ",p->data);
if(p->lchild)
push(p->lchild);
if(p->rchild)
push(p->rchild);
}
}
int main()
{
Bitree root=(Bitree)malloc(sizeof(BitreeNode));
createBitree(&root);
init_Queue();
printf("\nPreOrder!\n");
PreOrder(root);
printf("\nNonRecursion!\n");
PreOrderNonRecursion(root);
printf("\nInOrder\n");
InOrder(root);
printf("\nInOrderNonRecursion\n");
InOrderNonRecursion(root);
printf("\nPostOrder\n");
PostOrder(root);
printf("\nPostOrderNonRecursion\n");
PostOrderNonRecursion(root);
printf("\nlevelTraversal\n");
LevelTraversal(root);
return 0;
}
3.结果
结果验证时注意，输入数据以先序遍历顺序输入，NULL以#表示，输入的数据是字符表示，所以中间不需要添加空格。
第一次写博客，有什么问题请多多包涵！
