数据结构二叉树的递归遍历算法与非递归遍历算法-创新互联
先来了解一下二叉树的基本定义与性质:
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 。
首先来看看二叉树的数据结构
typedef struct Tree{
char data;
struct Tree* LChild;
struct Tree* RChild;
}Tree,*LpTree;
接下来看看代码
一：递归算法
代码如下
#include#includetypedef struct Tree{
char data;
struct Tree* LChild;
struct Tree* RChild;
}Tree,*LpTree;
LpTree createNode(){
char data;
LpTree T;
scanf("%c",&data);
if(data=='*'){
return NULL;
}
else{
T=(LpTree)malloc(sizeof(Tree));
T->data=data;
T->LChild=createNode();
T->RChild=createNode();
return T;
}
}
//打印节点中的元素
void printCurNodeData(LpTree curData){
printf("%c\t",curData->data);
}
//递归法遍历 先序遍历
void xianXuBianLi(LpTree L){
if(L!=NULL){
printCurNodeData(L);
xianXuBianLi(L->LChild);
xianXuBianLi(L->RChild);
}
}
//递归法遍历 中序遍历
void zhongXuBianLi(LpTree L){
if(L!=NULL){
zhongXuBianLi(L->LChild);
printCurNodeData(L);
zhongXuBianLi(L->RChild);
}
}
//递归法遍历 后序遍历
void houXuBianLi(LpTree L){
if(L!=NULL){
houXuBianLi(L->LChild);
houXuBianLi(L->RChild);
printCurNodeData(L);
}
}
int main()
{
LpTree T;
T=createNode();
printf("先序遍历:");
xianXuBianLi(T);
printf("\n中序遍历:");
zhongXuBianLi(T);
printf("\n后序遍历:");
houXuBianLi(T);
return 0;
} 递归遍历算法结果如图所示：
输入ABC**DE*G**F***（其中*表示空子树）若有不同需求，可将代码中的*替换为其他
二：非递归算法
代码如下
#include#includetypedef struct Tree{
char data;
struct Tree* LChild;
struct Tree* RChild;
}Tree,*LpTree;
LpTree createNode(){
char data;
LpTree T;
scanf("%c",&data);
if(data=='*'){
return NULL;
}
else{
T=(LpTree)malloc(sizeof(Tree));
T->data=data;
T->LChild=createNode();
T->RChild=createNode();
return T;
}
}
//非递归先序遍历
void xianXuBianLi(LpTree L){
if(L!=NULL){
//准备栈
struct Tree* stack[10];//存储每次打印节点的位置
int stackTop=-1;//栈顶标记
LpTree pMove=L;
while(stackTop!=-1||pMove){
while(pMove){
//把路径入栈+打印走过的节点
printf("%c\t",pMove->data);
stack[++stackTop]=pMove;
pMove=pMove->LChild;
}
if(stackTop!=-1){
pMove=stack[stackTop];//获取栈顶元素
stackTop--;
pMove=pMove->RChild;
}
}
}
else{
return;
}
}
//非递归中序遍历
void zhongXuBianLi(LpTree L){
if(L!=NULL){
//准备栈
struct Tree* stack[10];//存储每次打印节点的位置
int stackTop=-1;//栈顶标记
LpTree pMove=L;
while(stackTop!=-1||pMove){
while(pMove){
stack[++stackTop]=pMove;
pMove=pMove->LChild;
}
//出栈
if(stackTop!=-1){
pMove=stack[stackTop--];
printf("%c\t",pMove->data);
pMove=pMove->RChild;
}
}
}
else{
return;
}
}
//非递归后序遍历
void houXuBianLi(LpTree L){
if(L!=NULL){
//准备栈
struct Tree* stack[10];//存储每次打印节点的位置
int stackTop=-1;//栈顶标记
LpTree pMove=L;
LpTree plastVisit=NULL;
while(pMove){
stack[++stackTop]=pMove;
pMove=pMove->LChild;
}
//出栈
while(stackTop!=-1){
pMove=stack[stackTop--];
if(pMove->RChild==NULL||pMove->RChild==plastVisit)
{
printf("%c\t",pMove->data);
plastVisit=pMove;
}
else
{
//右边未被访问
stack[++stackTop]=pMove;
pMove=pMove->RChild;
while(pMove){
stack[++stackTop]=pMove;
pMove=pMove->LChild;
}
}
}
}
else{
return;
}
}
int main()
{
LpTree T;
T=createNode();
printf("先序遍历:");
xianXuBianLi(T);
printf("\n中序遍历:");
zhongXuBianLi(T);
printf("\n后序遍历:");
houXuBianLi(T);
return 0;
} 非递归遍历算法结果如图所示：
输入ABC**DE*G**F***（其中*表示空子树）若有不同需求，可将代码中的*替换为其他
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前标题：数据结构二叉树的递归遍历算法与非递归遍历算法-创新互联
文章路径：http://cdiso.cn/article/deciho.html
