-
用递归、非递归两种方法遍历二叉树
一、设计思想
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
-
上一篇:环保英语演讲稿带翻译【三篇】
下一篇:树形结构及其应用