非递归、递归遍历二叉树！
树的先、中、后、层序的遍历，需要用到栈结构和队结构。
首先来看树本身的定义：
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
栈的定义如下：
typedef BiTree SElemType; //栈元素为二叉树指针
#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACK_INCREMENT 2 // 存储空间分配增量
struct SqStack
{
SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}; // 顺序栈
队的定义如下：
typedef BiTree QElemType//队列元素为二叉树指针;
typedef struct QNode
{
QElemType data;
QNode *next;
}*QueuePtr;
struct LinkQueue
{
QueuePtr front,rear; // 队头、队尾指针
};
先序递归：
void PreOrderTraverse(BiTree T,void(*Visit)(TElemType))
{ //递归先序
if(T) // T不空
{
Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
先序非递归：
算法描述：先序是根左右的顺序，首先每次都访问根结点并将其入栈，然后访问其左孩子，再将其左孩子看做是下一个根结点进行访问，若其左孩子的左孩子为空，则出栈（此时栈指针指向最初入栈的结点）。然后访问其右孩子，再将右孩子看做一个根结点依次按照上述方法进行访问。
}
void PreOrderTraverse1(BiTree T,void (*Visit)(TElemType))
{//非递归(利用栈)实现先序遍历
SqStack S;
InitStack(S);
while(T||!StackEmpty(S))
{
if (T)
{
Visit(T->data);//第一个访问的永远是根，只要非空就输出
Push(S,T);//入栈根结点,若分支为空，方便返回路径
T=T->lchild;//遍历左分支
}
else//左子树为空，说明已经遍历完根和左了，该右了
{
Pop(S,T);//返回到栈顶元素
T=T->rchild;//访问它的右孩子
}
}
}
中序递归：
void InOrderTraverse(BiTree T,void(*Visit)(TElemType))
{ //递归中序
if(T)
{
InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
中序非递归：
算法描述：首先入栈根结点，若根结点的左孩子不空，就入栈左孩子，依次循环入栈左孩子，若发现左孩子的左孩子为空，则出栈弹出栈顶元素（此时其实访问到了最后一个左孩子，已是叶子结点了），访问其结点的值，再继续向右走，向右走的思路和上面一样，等于是在右子树上继续进行左中右顺序的访问。直到栈空为止。
void InOrderTraverse1(BiTree T,void (*Visit)(TElemType))
{//非递归(利用栈)实现中序遍历
SqStack S;
InitStack(S);
while(T||!StackEmpty(S))
{
if (T)
{
Push(S,T);//入栈根结点
T=T->lchild;//遍历左分支
}
else
{
Pop(S,T);
Visit(T->data);
T=T->rchild;
}
}
}
后序递归：
void PostOrderTraverse(BiTree T,void(*Visit)(TElemType))
{ //递归中序
if(T)
{
PostOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
PreOrderTraverse1(T->rchild,Visit); // 最后中序遍历右子树
Visit(T->data); // 再访问根结点
}
}
后序非递归：
算法描述：为了使输出的形式保持左右根的顺序，那么必须使得所有的左子树访问完成，然后所有的右子树访问完成后再访问根。为了准确描述，需要重新定义两个记录指针，cur和pre，前者是指示当前指针，后者是指向前一次位置的指针。遍历时首先先将根节点入栈，每次取栈顶元素的指针( 即top-1)为cur。这样一来可总结为：
若，
{
1、当前左孩子和右孩子均为空（只有根节点）。
2、当前的结点已经访问过。（下面有说明）
}
{则指针访问该结点的值；}
否则（说明有左右孩子），
{哪个孩子非空就入栈哪个孩子；}
什么叫已经访问过的结点？这里说明一下。根据上述的压栈顺序，比如我们现在分别压入根a，右a，左a。假设现在左a和右a都没有孩子了，这个子树已经是树的结尾了。那么栈顶的前三个元素依次为左a，右a，根a。首先取栈顶元素左a，发现其已经是叶子节点了，没有左右孩子，直接访问，退栈到右a，发现右a也没有左右孩子，也可以访问，然后退栈到根a，这时问题就来了，根a是有孩子的啊（左a和右a），理论上是不能访问的，可是我们已经按照左右根的顺序访问过了它的孩子，应该轮到他了呀。这里就需要对已经访问的结点做出判断，即满足pre=cur->lchild ||pre=cur->rchild时也可以访问。
void PostOrderTraverse1(BiTree T,void(*Visit)(TElemType))
{//对于任意节点，先将其入栈。如果它没有左孩子和右孩子则直接访问它；若它有
// 左孩子或者右孩子，但是已经被访问过了(是否访问用两个指针之间的关系判断)也可以访问它；
//如果都不是上述两种情况，则先访问它的右孩子，再访问它的左孩子，以此来保证能够左、右、根的输出。
SqStack S;
InitStack(S);
BiTree cur;//当前指针
BiTree pre=NULL;//前一个指针
Push(S,T);//根节点入栈
while(!StackEmpty(S))//只要栈不空
{//如果当前没有左孩子和右孩子，或者说当前节点是已经访问过的
cur=GetTop(S,T);//每次都取栈顶元素
if ((cur->lchild==NULL && cur->rchild==NULL)||
(pre!=NULL && (pre==cur->lchild)|| pre==cur->rchild))
{
Visit(cur->data);
Pop(S,T);//出栈下移栈顶指针，准备下次访问
pre=cur;//记录走过的路径
}
else
{//保证压栈的顺序为先右后左，才能左根右的输出
if (cur->rchild!=NULL)
Push(S,cur->rchild);
if (cur->lchild!=NULL)
Push(S,cur->lchild);
}
}
层序遍：
算法描述：层序遍历需要用到队列，访问顺序是子根，左孩子1，右孩子1，左孩子1的左孩子和右孩子，右孩子1的左孩子和右孩子………….由于队列具有先进先出的特点，所以我们入队的顺序就是访问结点的顺序。只要哪个孩子不空就入队哪个孩子，出队时直接出队就行，顺序就会保持。
void LevelOrderTraverse(BiTree T,void(*Visit)(TElemType))
{
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(q); // 初始化队列q
EnQueue(q,T); // 根指针入队
while(!QueueEmpty(q)) // 队列不空
{
DeQueue(q,a); // 出队元素(指针),赋给a
Visit(a->data); // 访问a所指结点
if(a->lchild!=NULL) // a有左孩子
EnQueue(q,a->lchild); // 入队a的左孩子
if(a->rchild!=NULL) // a有右孩子
EnQueue(q,a->rchild); // 入队a的右孩子
}
printf(“\n”);
}
}
下面是代码的全部实现：
其中头文件head.h为如下定义：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
#include "head.h"//头文件//树结构定义typedef char TElemType;TElemType Nil=' ';typedef struct BiTNode{TElemType data;BiTNode *lchild,*rchild; // 左右孩子指针}BiTNode,*BiTree;/*-------栈操作开始-------*/typedef BiTree SElemType; //栈元素为二叉树指针#define STACK_INIT_SIZE 10 // 存储空间初始分配量#define STACK_INCREMENT 2 // 存储空间分配增量struct SqStack{SElemType *base; // 在栈构造之前和销毁之后，base的值为NULLSElemType *top; // 栈顶指针int stacksize; // 当前已分配的存储空间，以元素为单位}; // 顺序栈void InitStack(SqStack &S){ // 构造一个空栈Sif(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))))exit(OVERFLOW); // 存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;}void Push(SqStack &S,SElemType e){ // 插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize) // 栈满，追加存储空间{S.base=(SElemType *)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW); // 存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACK_INCREMENT;}*(S.top)++=e;}Status Pop(SqStack &S,SElemType &e){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top==S.base)return ERROR;e=*--S.top;return OK;}BiTree GetTop(SqStack S,SElemType &e){ // 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(S.top>S.base){e=*(S.top-1);return e;}elsereturn NULL;}Status StackEmpty(SqStack S){ // 若栈S为空栈，则返回TRUE，否则返回FALSEif(S.top==S.base)return TRUE;elsereturn FALSE;}/*---------栈操作结束--------------*//*---------队操作开始----------*/typedef BiTree QElemType;typedef struct QNode{QElemType data;QNode *next;}*QueuePtr;struct LinkQueue{QueuePtr front,rear; // 队头、队尾指针};void InitQueue(LinkQueue &Q){ // 构造一个空队列Qif(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))exit(OVERFLOW);Q.front->next=NULL;}Status QueueEmpty(LinkQueue Q){ // 若Q为空队列，则返回TRUE，否则返回FALSEif(Q.front->next==NULL)return TRUE;elsereturn FALSE;}void EnQueue(LinkQueue &Q,QElemType e){ // 插入元素e为Q的新的队尾元素QueuePtr p;if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;}Status DeQueue(LinkQueue &Q,QElemType &e){ // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERRORQueuePtr p;if(Q.front==Q.rear)return ERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return OK;}/*---------队操作结束----------*//*------二叉树操作开始------*/void visitT(TElemType e){printf("%c ",e);}void PreOrderTraverse(BiTree T,void(*Visit)(TElemType)){ //递归先序if(T) // T不空{Visit(T->data); // 先访问根结点PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树}}void PreOrderTraverse1(BiTree T,void (*Visit)(TElemType)){//非递归(利用栈)实现先序遍历SqStack S;InitStack(S);while(T||!StackEmpty(S)){if (T){Visit(T->data);//第一个访问的永远是根，只要非空就输出Push(S,T);//入栈根结点,若分支为空，方便返回路径T=T->lchild;//遍历左分支}else//左子树为空，说明已经遍历完根和左了，该右了{Pop(S,T);//返回到栈顶元素T=T->rchild;}}}void InOrderTraverse(BiTree T,void(*Visit)(TElemType)){ //递归中序if(T){InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树Visit(T->data); // 再访问根结点InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树}}void InOrderTraverse1(BiTree T,void (*Visit)(TElemType)){//非递归(利用栈)实现中序遍历SqStack S;InitStack(S);while(T||!StackEmpty(S)){if (T){Push(S,T);//入栈根结点T=T->lchild;//遍历左分支}else{Pop(S,T);Visit(T->data);T=T->rchild;}}}void PostOrderTraverse(BiTree T,void(*Visit)(TElemType)){ //递归中序if(T){PostOrderTraverse(T->lchild,Visit); // 先中序遍历左子树PostOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树Visit(T->data); // 再访问根结点}}//非递归后序遍历void PostOrderTraverse1(BiTree T,void(*Visit)(TElemType)){//对于任意节点，先将其入栈。如果它没有左孩子和右孩子则直接访问它；若它有// 左孩子或者右孩子，但是已经被访问过了(是否访问用两个指针之间的关系判断)也可以访问它；//如果都不是上述两种情况，则先访问它的右孩子，再访问它的左孩子，以此来保证能够左、右、根的输出。SqStack S;InitStack(S);BiTree cur;//当前指针BiTree pre=NULL;//前一个指针Push(S,T);//根节点入栈while(!StackEmpty(S))//只要栈不空{//如果当前没有左孩子和右孩子，或者说当前节点是已经访问过的cur=GetTop(S,T);//每次都取栈顶元素if ((cur->lchild==NULL && cur->rchild==NULL)||(pre!=NULL && (pre==cur->lchild)|| pre==cur->rchild)){Visit(cur->data);Pop(S,T);//出栈下移栈顶指针，准备下次访问pre=cur;//记录走过的路径}else{//保证压栈的顺序为先右后左，才能左右根的输出if (cur->rchild!=NULL)Push(S,cur->rchild);if (cur->lchild!=NULL)Push(S,cur->lchild);}}}void LevelOrderTraverse(BiTree T,void(*Visit)(TElemType)){LinkQueue q;QElemType a;if(T){InitQueue(q); // 初始化队列qEnQueue(q,T); // 根指针入队while(!QueueEmpty(q)) // 队列不空{DeQueue(q,a); // 出队元素(指针),赋给aVisit(a->data); // 访问a所指结点if(a->lchild!=NULL) // a有左孩子EnQueue(q,a->lchild); // 入队a的左孩子if(a->rchild!=NULL) // a有右孩子EnQueue(q,a->rchild); // 入队a的右孩子}printf("\n");}}void InitBiTree(BiTree &T){ // 操作结果：构造空二叉树TT=NULL;}void CreateBiTree(BiTree &T){ //递归先序生成二叉树TElemType ch;scanf("%c",&ch);if(ch==Nil) // 空T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点if(!T)exit(OVERFLOW);T->data=ch;CreateBiTree(T->lchild); // 构造左子树CreateBiTree(T->rchild); // 构造右子树}}/*-------二叉树操作结束----------*//************************************************************************//* 主函数开始 *//************************************************************************/void main(){BiTree T;InitBiTree(T);printf("先序输入构造二叉树:\n");CreateBiTree(T);printf("利用队----层序遍历----二叉树:\n");LevelOrderTraverse(T,visitT);printf("\n");printf("递归法---先序遍历---二叉树:\n");PreOrderTraverse(T,visitT);printf("\n");printf("非递归---先序遍历---二叉树:\n");PreOrderTraverse1(T,visitT);printf("\n");printf("递归法---中序遍历---二叉树:\n");InOrderTraverse(T,visitT);printf("\n");printf("非归法---中序遍历---二叉树:\n");InOrderTraverse(T,visitT);printf("\n");printf("递归法---后序遍历---二叉树:\n");PostOrderTraverse(T,visitT);printf("\n");printf("非递归---后序遍历---二叉树:\n");PostOrderTraverse1(T,visitT);printf("\n");}
向右看齐
太过爱你忘了你带给我的痛
迈不过友情╰
亦凉
小鱼儿![[MySQL FAQ]系列-net_buffer_length选项对数据备份及恢复影响](https://image.dandelioncloud.cn/images/20221120/d54048ba14da4535a7e4d0d10ba1a5d8.png "[MySQL FAQ]系列-net_buffer_length选项对数据备份及恢复影响")
还没有评论，来说两句吧...