先来了解一些概念
树
树是结点的有限集合,必须符合条件
当n=0时,为空树
当n>0时,除根结点外,其他结点为m(m>0)个不相交的非空集合
树的度:所有结点的度的最大值。
树的深度:所有结点层次的最大值
二叉树
是在树的结构上建立的,比树的定义更要严密。
区别在于:二叉树只有左,右子树我们先来对比下
A)为有右子树为空的二叉树B)为左子树为空的二叉树
C)是一颗子树的树
二叉树的遍历:
深度遍历
广度遍历
非递归遍历
共同点:
都具有先序遍历。访问根结点,遍历左子树,遍历右子树
不同点:
深度遍历
也称为内部遍历,采用栈的形式,根据二叉树自身构成,访问节点和子树的不同顺序,分别先序,中序和后序遍历
实例:
如上图,它的先序遍历是怎样被访问的
A的左子树有BDGEH,根据,根,左,右的访问顺序,依次访问,最后的顺序为ABDGEHCF
广度遍历
采用队列的形式,逐层向下遍历,每层从左到右顺序访问
如下图:
访问的次序为A,B,C,D,EF,G,H
非递归遍历:
也称为外部遍历,是栈和队列的结合,和递归的不同点在于,非递归运用循环的特点,如果一测子树是否为空,直到循环为空为止才肯结束。
非递归也是分为先,中,后序遍历的。
具体的一些算法结构如下
先序遍历
对于任一结点P:
1)访问结点P,并将结点P入栈;
2)判断结点P的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点P,循环至1);若不为空,则将P的左孩子置为当前的结点P;
3)直到P为NULL并且栈为空,则遍历结束。
具体的C算法如下
void preOrder2(BinTree*root) //非递归前序遍历
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
后序与中序的遍历顺序与递归的访问基本也是相同的这里不在累述。
小结
二叉树的遍历,有深度,广度和非递归的遍历。
它们的相同点:都是按照某种顺序,访问根,左右子树
不同点:深度遍历是运用栈的特点,广度遍历是运用队列特点,而非递归是结合以上两种方式(比较繁琐)。二叉树的遍历为数据的查询提供了很大的遍历。
分享到:
相关推荐
二叉树遍历的特点
数据结构课程设计--二叉树遍历及其应用、对树的先序遍历、后序遍历、中序遍历、层序遍历、二叉树的深度及其叶子树、并打印树形。
1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;...ABCDEFG【选做内容】采用非递归算法实现二叉树遍历。
实验三 二叉树遍历与路径查找(二叉树实验) 实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树的层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树...
二叉树遍历的非递归操作二叉树遍历的非递归操作
一个实现二叉树遍历的程序代码,有先序,中序和后序。
易语言二叉树遍历源码,二叉树遍历,二叉树_取下级树,内存_读整数内存,读整数内存_
二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题...
运用C语言编写的二叉树遍历程序 先序遍历·中序遍历·后序遍历
java 写的算24程序。用两种二叉树遍历,并规整输出字符串
二叉树遍历 二叉树遍历
二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法
用堆栈实现二叉树遍历,C语言实现的数据结构
遍历二叉树 遍历二叉树的先序、中序和非递归遍历二叉树的六种算法
数据结构第七章二叉树遍历的源代码,有用有用~~按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树...
二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...
利用二叉树遍历算法的框架和思路,假设访问结点的具体操作不仅仅局限于输出结点数据域的值,而把访问延伸到对结点的判别、计数等其他操作。这样可以解决一些关于二叉树的其他实际问题。(1) 统计二叉树中结点总数m...
二叉树遍历操作.cpp
二叉树遍历问题-二叉树遍历问题