树的遍历（递归和非递归）

二叉树的遍历

一、设计思想

二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。

递归算法：

1．先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。

2.中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。

3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。

非递归算法：

1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。

2.中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。

3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。

二、算法流程图

图1 二叉树的建立

用先序方法建立二叉树，为每个结点定义左右子，用0代表空，得到上述二叉树

图2 非递归二叉树遍历 先序

首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。

图3 非递归二叉树遍历 中序

中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。

图4 非递归二叉树遍历 后序

首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。

三、源代码

#include

#include

//用递归的方式遍历二叉树

typedef struct node //定义二叉树的结点

{ int data; //结点的数据

struct node*lChild,*rChild; //结点左右子

}Node;

int i=-1; //控制下面函数中循环的

Node *buildTree(int *b) //产生二叉树(利用先序递归产生)

{

Node *p; //创建一个根结点指针

if(b[++i]==0)p=NULL; //如果传入的当前值为0 则设其为空结点 else

{ p=(Node*)malloc(sizeof(Node)); //开辟内存

p->data=b[i]; //设置当前结点的数据

p->lChild=buildTree(b); //左子结点

p->rChild=buildTree(b); //右子

}

return p; //把创建的树的根节点返回

}

void preOrder(Node *root) //前序遍历

{

下面给出的是用递归算法实现的程序的源代码：

if(root!=0) //如果根节点不为0

{

printf("%d ",root->data); //打印当前结点

preOrder(root->lChild); //指向左子

preOrder(root->rChild); //指向右子

}

}

void inOrder(Node *root) //中序遍历

{

if(root!=0) //如果根节点不为0

{

inOrder(root->lChild); //指向左子

printf("%d ",root->data); //打印当前结点

inOrder(root->rChild); //指向右子

}

}

void postOrder(Node *root)

{

if(root!=0)

{

postOrder(root->lChild); //指向左子

postOrder(root->rChild); //指向右子

printf("%d ",root->data); //打印当前结点

}

}

void main()

{

//按先序次序输入树的结点(非0整数)来创建一个树 空结点用0表示

int a[] = {1,2,4,0,7,0,0,0,3,5,0,0,6,8,0,0,9,0,0};

int *b = a;

//将指向数组首地址的指针传给 bulidTree 函数 来创建树

Node *root = buildTree(b);

printf("用递归方法 \n\n前序遍历: "); //打印提示内容

preOrder(root); //调用前序遍历函数 printf("\n中序遍历: "); //打印提示内容

inOrder(root); //调用中序遍历函数 printf("\n后序遍历: "); //打印提示内容

postOrder(root); //调用后序遍历函数 getch();

}

下面给出的是用非递归算法实现的程序的源代码： #include #include

//用非递归的方式遍历二叉树

typedef struct node {

int data;

struct node *lChild,*rChild;

}Node;

typedef struct {

Node *bottom;

Node *top;

}Stack;

void init(Stack *s) {

s->bottom=(Node *)malloc(100*sizeof(Node));

s->top=s->bottom; }

int isEmpty(Stack s) {

if(s.top==s.bottom)

return 1;

else

return 0;

}

void push(Stack *s,Node node) {

*(s->top++)=node;

}

Node pop(Stack *s) {

Node node;

node=*(--(s->top));

return node;

}

Node peek(Stack *s) {

return *(s->top-1);

}

typedef struct {

Node *bottom;

Node *top;

}MyStack;

//定义二叉树的结点

//结点的数据

//结点左右子

//创建栈

//栈底指针

//栈顶指针

//初始化栈

//为指针开辟内存

//栈顶指针指向栈底指针

//判断栈是否为空的函数

//栈空 返回1

//不为空返回 0

//栈的push方法

//给栈顶赋值 然后top+1

//出栈函数

//声明一Node类型遍量

//node 为栈顶元素 然后top-1

//返回pop出的结点

//看栈顶元素

//返回栈顶元素

//创建栈(MyStack)结构体

//栈底指针

//栈顶指针

void init1(MyStack *s) //初始化栈

{

s->bottom=(Node *)malloc(100*sizeof(Node)); //开辟内存

s->top=s->bottom; //栈顶指针指向栈底指针 }

void push1(MyStack *s,Node node) //进栈方法

{

*(s->top++)=node; //给栈顶赋值 然后top+1 }

Node pop1(MyStack *s) //出栈函数

{

Node node; //声明一Node类型遍量

node=*(--(s->top)); //node 为栈顶元素然后top-1 return node; //返回pop出的结点 }

Node peek1(MyStack *s) //查栈顶元素

{

return *(s->top-1); //返回栈顶元素 }

int isEmpty1(MyStack s) //判断栈是否为空 {

if(s.top==s.bottom)

return 1; //栈空了 返回1 else

return 0; //不为空返回 0 }

int temp=-1;

Node *buildTree(int *b) //产生二叉树

{

Node *p; //创建一个根结点指针 if(b[++temp]==0)

p=NULL; //如果传入的当前值为0 则设其为空结点 else

{ p=(Node*)malloc(sizeof(Node)); //开辟内存

p->data=b[temp]; //设置当前结点的数据 p->lChild=buildTree(b); //左子结点

p->rChild=buildTree(b); //右子

};

return p; //把创建的树的根结点返回 }

void preOrder(Node *root) //前序遍历

{

Stack po; //声明一个栈

Node curr = *root; //当前结点为根结点

init(&po); //初始化找

while(curr.data!=0||!isEmpty(po)) //当前结点不为空 且 栈不为空 {

if(curr.data==0) //如果当前结点为空 {

curr=pop(&po); //当前结点指向 pop出栈的结点 }

if(curr.rChild!=NULL) //如果右子为空

{

push(&po,*curr.rChild); //将右子进栈

}

printf("%d ",curr.data); //打印当前结点的内容 if(curr.lChild!=NULL) //如果左子不为空 {

curr=*curr.lChild; //当前子指向左子 }else

{

curr=pop(&po); //当前子指向pop出栈结点 }

if((curr.lChild==NULL)&&(curr.rChild==NULL)) //如果左子右子都为空 {

printf("%d ",curr.data); //打印当前结点的内容 curr.data=0; //当前结点置空

}

}

}

void inOrder(Node *root) //中序遍历

{

Stack ms; //声明一个栈

Node curr = *root; //当前结点指向根结点 int flag = 0;

//设置一个标志 0:当前结点指向了右结点 1:当前结点指向了左结点

init(&ms); //初始化栈

while(curr.data!=0||isEmpty(ms)) //当前结点不为空且栈不为空 {

if(curr.lChild!=NULL&&flag==0) //左子不为空且没去过左子 {

push(&ms,curr); //当前子进栈

curr=*curr.lChild; //当前结点指向左子 }else

{

printf("%d ",curr.data); //打印当前结点的内容 if(curr.rChild!=NULL) //左子为空

{

curr=*curr.rChild; //指向左子

}

flag=0; //flag 置 0

}

if(curr.rChild==NULL&&curr.lChild==NULL) //如果左右子都为空 {

printf("%d ",curr.data); //打印当前结点的内容 if(isEmpty(ms)==1)

break; //栈空 则结束循环

curr = pop(&ms); //当前子指向pop出栈的结点

flag=1; //flag 置 1

}

}

}

void postOrder(Node *root) //后序遍历

{

//声明左右栈 如果当前结点有左子则进左栈 若没左子但是有右子则进右栈

Stack msl; //声明左栈

MyStack msr; //声明右栈

Node curr = *root; //结点指向树的根结点

int flag=0; //设置一个标志 0:进左栈 1:进右栈

//设置一个标志 0:没去过左右子树 1:去过左子树 2:去过右子树(两子树都去过)

int status=0;

init(&msl); //初始化左栈

init(&msr); //初始化右栈

while(curr.data!=0||isEmpty(msl)!=0||isEmpty1(msr)!=0) //当前结点不为空且左右栈都不为空

{

if(status==0&&curr.lChild!=NULL) //没去过左右子树 且右子不为空

{

push(&msl,curr); //当前子进左栈

curr = *curr.lChild; //当前子指向左子

flag=0; //flag置0

}

else if(status!=2&&curr.rChild!=NULL) //没去过右子树且右子不为空

{

push1(&msr,curr); //当前子进右栈

curr=*curr.rChild //当前子指向右子

flag=1; //flag置1

status=0; //status 置0

}

else

{

printf("%d ",curr.data); //打印当前结点内容

//指向右栈弹出的元素 //status标志置为2 //如果右栈为空 //指向右栈弹出的元素 //指向左栈弹出的元素 //status标志置为1 //若当前结点为空，结束循环

}

}

Void main()

{

int Tree[] = {1,2,4,0,7,0,0,0,3,5,0,0,6,8,0,0,9,0,0};

int *tree = Tree;

Node *root = buildTree(tree); //创建一个结点指向创建的树的根结点

printf("用非递归方法 \n前序遍历: "); //打印提示内容

preOrder(root); //调用前序遍历函数

printf("\n中序遍历: "); //打印提示内容

inOrder(root); //调用中序遍历函数

printf("\n后序遍历 "); //打印提示内容

postOrder(root); //调用后序遍历函数

getch();

}

curr.data=0;

}

if(curr.data==0)

if(flag==0)

{

if(isEmpty(msl)==0)

{

curr = pop(&msl);

status=1;

}

else if(isEmpty1(msr)==0)

{

curr = pop1(&msr);

status=2;

}

}

else { if(isEmpty1(msr)==0)

{

curr=pop1(&msr);

status=2;

}

else if(isEmpty(msl)==0)

{

curr=pop(&msl);

status=1;

}

}

if(curr.data==0)

break;

}

//当前结点置空 //如果当前子为空 //如果flag标志为0 //如果左栈不为空 //指向左栈弹出的元素 //status标志置为1

{

四、运行结果

图5 递归算法运行结果图

图6 非递归算法运行结果图

.

先序遍历非递归算法

void PreOrderUnrec(Bitree *t) 

{ 

Stack s; 

StackInit(s); 

Bitree *p=t; 

while (p!=NULL || !StackEmpty(s)) 

{   

while (p!=NULL)  

//遍历左子树

{  

visite(p->data);  

push(s,p); 

p=p->lchild;   

}   

if (!StackEmpty(s))   

//通过下一次循环中的内嵌while实现右子树遍历

{ 

p=pop(s);  

p=p->rchild; 

}//endif 

}//endwhile 

} 

2.中序遍历非递归算法

void InOrderUnrec(Bitree *t) 

{ 

Stack s; 

StackInit(s); 

Bitree *p=t;  

while (p!=NULL || !StackEmpty(s)) 

{ 

while (p!=NULL)  //遍历左子树

{  

push(s,p);  

p=p->lchild; 

}  

if (!StackEmpty(s))    

{ 

p=pop(s);  

visite(p->data); //访问根结点

p=p->rchild; //通过下一次循环实现右子树遍历

}//endif 

}//endwhile 

}

3.后序遍历非递归算法

typedef enum{L,R} tagtype; 

typedef struct 

{ 

Bitree ptr; 

tagtype tag; 

}stacknode; 

typedef struct 

{ 

stacknode Elem[maxsize]; 

int top; 

}SqStack; 

void PostOrderUnrec(Bitree t) 

{ 

SqStack s; 

stacknode x; 

StackInit(s); 

p=t; 

do 

{

while (p!=null) //遍历左子树

{ 

x.ptr = p;  

x.tag = L; //标记为左子树

push(s,x); 

p=p->lchild; 

}

while (!StackEmpty(s) && s.Elem[s.top].tag==R)      

{ 

x = pop(s);  

p = x.ptr; 

visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点

} 

if (!StackEmpty(s))   

{

s.Elem[s.top].tag =R;//遍历右子树

p=s.Elem[s.top].ptr->rchild; 

}

}while (!StackEmpty(s)); 

}//PostOrderUnrec

本文来源：https://www.2haoxitong.net/k/doc/11712c82f78a6529657d5316.html