关键词不能为空

当前您在: 主页 > 英语 >

递归非递归两种算法遍历二叉树讲解

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2021-01-25 09:00
tags:

-

2021年1月25日发(作者:丈夫的英文)
用递归、非递归两种方法遍历二叉树

一、设计思想

1.
用递归算法遍历


设计思想:主要是通过不同程序顺序,从而实现递归的顺序遍历


前序遍历 :先判断节点是否为空,如果不为空,则输出。再判断左节点是否为空,如
果不为空,则递归调用,直到 遍历到最左边。接着再遍历最左边的右子树,如果此时右子
树不为空,则递归遍历左子树的操作,直到遍 历到叶子节点。如果右子树为空,则回溯上
次的递归调用,重复输出和遍历右子树的操作。


中序遍历:

先遍历左节点是否为空,如果不为空,则递归调用,直到遍历 到最左边
或者叶子节点,然后输出,接着再遍历最左边的右子树,如果此时右子树不为空,则递归
重复遍历左子树的操作,
直到遍历到叶子节点。
如果右子树为空,
则回溯到上次递归 调用,
重复输出和遍历右子树的操作。


后序遍历:先判断左节点是否为空 ,如果不为空则一直递归直到遍历到最左边,然后
遍历右节点,再接着遍历到左子树的最右边,直到遍历 到叶子节点。此时输出,回溯到上
次递归,继续执行后面的操作,重复,直到将整个树遍历完毕。


2.
用非递归算法遍历


设计思想:主要是通过栈的存取,判空,从而实现树的遍历


前序遍历:通 过一个循环实现。先输出节点的数值,因为栈的特性,则需要先判断右
子树是否为空,如果不为空,则将 右子树压栈。然后判断左子树是否为空,如果不为空,
则将左子树压栈。接着再将栈里面的子树弹出赋给 给当前节点变量,重复上述操作,直到
栈为空后退出循环。


中序遍历:通 过循环实现。将树一直遍历到最左端,并将中间所经过的节点保存在栈
中,当遍历到最左边的时候,则弹 出栈里面的子树。输出数值,将当前节点赋值为当前节
点的右子树,遍历右子树,即重复上述操作,直到 当前节点为空,并且栈内元素为
0



后序遍历:通过循环和标记 栈实现。将数一直遍历到最左端,并将中间的节点保存在
树栈中,同时同步的添加一个标记栈。当遍历到 最左边的时候,弹栈并赋值给当前栈,然
后判断标记栈的数值,如果数值为
0
的话则代 表当前树没有遍历过,遍历右子树。然后重
复上面的操作,如果数值为
1
的话则代表此 时数已经遍历过了,可以开始输出了,为了避
免重复输出,将当前栈赋为空。重复循环操作,直到栈内没 有元素,且当前节点为空(因
为一直左的操作并没有将右子树压栈)









- 1 -
用递归、非递归两种方法遍历二叉树

二、算法流程图

开始

Root=Tree t
Y
Root=null
N
输出数据

N

Tree=null
Y
N

Tree=null
Y
结束


1
递归算法
-
先序遍历




开始

开始

Root=Tree t
Root=Tree t
Y
Y
Root=null
Root=null
N
N
N
N


Tree=null
Tree=null
Y
Y
N
输出数据


Tree=null
N
Y

Tree=null
输出数据

Y
结束

结束


2
递归算法
-
后序遍历



3
递归算法
-
中序遍历

- 2 -


用递归、非递归两种方法遍历二叉树

开始

开始

Tree t=root
Tree t=root
N
t = null
output

N
t = null
压栈

Y
N
ee=
null
Push

t=
Y
t=current.
getLtree()

()
Y
output

N
ee=
null
Push


Y
N
t=current.
getRltree()
栈为空

t=
()
N
栈为空

Y
Y
结束

结束


4
非递归算法
-
先序遍历








5
非递归算法
-
中序遍历

- 3 -
用递归、非递归两种方法遍历二叉树

开始

Tree t=root
N
t = null
Push
标签栈压栈

Y
t=
()
t=ee()
标签栈出栈

赋值给标志位

N
判断栈是否已
经入栈过

t=ee()

标签栈压栈

Y
出栈并赋值
t
Output
Current=null
N
树栈为空且当前节点为空

Y
结束


6
非递归算法
-
后序遍历

- 4 -
用递归、非递归两种方法遍历二叉树

三、源代码

#include


#include






typedef char ElemType;


//
定义树结构



typedef struct tree


{






ElemType data;






struct tree * lchild;






struct tree * rchild;






unsigned int isOut;


//
专为后序遍历设置的,
0
为不需要被输出,
1
为需要被输出



}TreeNode, *Tree;


//
定义栈结构



typedef struct stack


{






Tree * base;






Tree * top;






int stacksize;


}SqStack;





void InitStack( SqStack &s );



void Push( SqStack &s, Tree e );


void GetTop( SqStack s, Tree &e );


void Pop( SqStack &s, Tree &e );


int StackEmpty( SqStack s );







void CreateTree(Tree &t);


void PreOrder(Tree t);


void PreOrder1(Tree t);


void InOrder(Tree t);


void InOrder1(Tree t);


void PostOrder(Tree t);


void PostOrder1(Tree t);





int main()


{






Tree T;






printf(
按先序序列输入结点序列,
'*'
代表空:



CreateTree(T);




printf(
递归先序遍历的结果:








PreOrder(T);

- 5 -
用递归、非递归两种方法遍历二叉树





printf(
非递归先序遍历的结果:







PreOrder1(T);






printf(
递归中序遍历的结果:








InOrder(T);






printf(
非递归中序遍历的结果:







InOrder1(T);






printf(
递归后序遍历的结果:








PostOrder(T);




printf(
非递归后序遍历的结果:







PostOrder1(T);








printf(



}





void InitStack( SqStack &s )

//
初始化栈

{






= (Tree *)malloc(100*sizeof(Tree));






if ( ! )






{






printf(
内存分配出错
,
程序将推出执行!
n


exit (-1);
return 0;




}










=






ize = 100;


}





void Push (SqStack &s, Tree e )

//
元素入栈


接收一个

stack
类型变量和一个

tree*
类型变量

{






if ( - >= ize )






{


















= (Tree *)realloc(,(ize+20)*sizeof(Tree));


if ( ! )


{




}

= + ize;
//

ize += 20;


printf(
内存分配出错
,
程序将退出执行
n


exit (-1);






}






e->isOut = 0;






*++ = e;


}





void GetTop( SqStack s, Tree &e ) //
获得栈顶元素

- 6 -

-


-


-


-


-


-


-


-



本文更新与2021-01-25 09:00,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/565006.html

递归非递归两种算法遍历二叉树讲解的相关文章