1. 前言
所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。
2. 二叉树遍历的定义
二叉树的遍历过程其实也是将二叉树的非线性序列转换成一个线性序列的过程。二叉树是一种非线性结构,通过遍历二叉树,按照某种规律对二叉树中的每个结点进行访问,且仅访问一次,得到一个顺序序列。
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
(1)访问结点本身(N),
(2)遍历该结点的左子树(L),
(3)遍历该结点的右子树(R)。
以上三种操作有六种执行次序:
NLR、LNR、LRN、NRL、RNL、RLN。
注意:
前三种次序与后三种次序对称,故只讨论先左后右的前三种次序。
根据访问结点操作发生位置命名:
① NLR:前序遍历(PreorderTraversal亦称(先序遍历))
——访问结点的操作发生在遍历其左右子树之前。
② LNR:中序遍历(InorderTraversal)
——访问结点的操作发生在遍历其左右子树之中(间)。
③ LRN:后序遍历(PostorderTraversal)
——访问结点的操作发生在遍历其左右子树之后。
注意:
由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
3. 遍历算法
① 先序遍历的递归算法定义:若二叉树非空,则依次执行如下操作:
(1) 访问根结点;
(2) 遍历左子树;
(3) 遍历右子树。
② 中序遍历的递归算法定义:若二叉树非空,则依次执行如下操作:
(1)遍历左子树;
(2)访问根结点;
(3)遍历右子树。
③ 后序遍历得递归算法定义:若二叉树非空,则依次执行如下操作:
(1)遍历左子树;
(2)遍历右子树;
(3)访问根结点。
(1)二叉树的先序遍历的递归算法如下:
void preorder(BTree *b)
{
if(b!=NULL)
{
printf("%d",b->data);
preorder(b->lchild);
preorder(b->rchild);
}
}
(2)二叉树的中序遍历的递归算法如下:
void inorder(BTree*b)
{
if(b!=NULL)
{
inorder(b->lchild);
printf("%d",b->data);
inorder(b->rchild);
}
}
(3)二叉树的后序遍历的递归算法如下:
void postorder(BTree*b)
{
if(b!=NULL)
{
postorder(b->lchild);
postorder(b->rchild);
printf("%d",b->data);
}
}
4. 遍历二叉树的执行踪迹
三种递归遍历算法的搜索路线相同(如下图虚线所示)。
具体线路为:从根结点出发,逆时针沿着二叉树外缘移动,对每个结点均途径三次,最后回到根结点。
图 遍历二叉树的搜索路径
遍历序列
(1) 中序序列(左中右)
中序遍历二叉树时,对结点的访问次序为中序序列
【例】中序遍历上图所示的二叉树时,得到的中序序列为:
D B A E C F
(2) 先序序列(中左右)
先序遍历二叉树时,对结点的访问次序为先序序列
【例】先序遍历上图所示的二叉树时,得到的先序序列为:
A B D C E F
(3) 后序序列(左右中)
后序遍历二叉树时,对结点的访问次序为后序序列
【例】后序遍历上图所示的二叉树时,得到的后序序列为:
D B E F C A
注意:
(1) 在搜索路线中,若访问结点均是第一次经过结点时进行的,则是前序遍历;若访问结点均是在第二次(或第三次)经过结点时进行的,则是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表,即可分别得到该二叉树的前序序列、中序序列和后序序列。
(2) 上述三种序列都是线性序列,有且仅有一个开始结点和一个终端结点,其余结点都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋(即双亲)结点和后继(即孩子)结点的概念,对上述三种线性序列,要在某结点的前趋和后继之前冠以其遍历次序名称。
【例】上图所示的二叉树中结点C,其前序前趋结点是D,前序后继结点是E;中序前趋结点是E,中序后继结点是F;后序前趋结点是F,后序后继结点是A。但是就该树的逻辑结构而言,C的前趋结点是A,后继结点是E和F。
5. 二叉链表的
(1)基本思想
基于先序遍历的构造,即以二叉树的先序序列为输入构造。
注意:
先序序列中必须加入虚结点以示空指针的位置。
【例】
建立上图所示二叉树,其输入的先序序列是:ABD∮∮∮CE∮∮F∮∮。
(2)构造算法
假设虚结点输入时以空格字符表示,相应的构造算法为:
void CreateBinTree (BinTree *T)
{ //构造二叉链表。T是指向根指针的指针,故修改*T就修改了实参(根指针)本身
char ch;
if((ch=getchar())=='') *T=NULL; //读人空格,将相应指针置空
else{ //读人非空格
*T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点
(*T)->data=ch;
CreateBinTree(&(*T)->lchild); //构造左子树
CreateBinTree(&(*T)->rchild); //构造右子树
}
}
注意:
调用该算法时,应将待建立的二叉链表的根指针的地址作为实参。
【例】
设root是一根指针(即它的类型是BinTree),则调用CreateBinTree(&root)后root就指向了已构造好的二叉链表的根结点。
分享到:
相关推荐
2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问结点的操作修改为叶结点计数,统计度为0的;度为1...
里面是二叉树遍历的综合,可能有点杂,但觉得可以就下
栈的应用——二叉树的前序、中序、后序非递归遍历算法
数据结构,实现二叉树的生成与遍历的算法。包含利用先序、中序、后序遍历二叉树算法,二叉树基本操作。(注意没有左子树或右子树时用@或#作为结束符号)
算法与数据结构——二叉树的建立与遍历.pdf算法与数据结构——二叉树的建立与遍历.pdf
实验要求: (1)采用链式存储结构建立...(2)二叉树的建立采用递归方式实现,先序遍历、中序遍历、后序遍历均采用非递归方式实现。 (3)在主函数中分别调用以上四个算法函数(建立二叉树,先序、中序、后序遍历二叉树)。
完成二叉树的建立然后分别先序中序后序遍历二叉树并算出二叉树的高度和叶节点的个数
花了不少时间 给整的 希望对出学者有好处 是二叉树实验经常用到的
一)建立二叉树+判空+遍历 (1)以二叉链表作为存储结构,从键盘以先序次序输入各个结点(空格字符表示空树)建立一棵二叉树; (2)对(1)中生成的二叉树进行判空; (3)对(1)中生成的二叉树进行遍历(分别实现...
以二叉链表作存储结构,试编写前序、中序、后序遍历二叉树的算法。
二叉树的中序遍历,这里不太了解的可以看看这个博客:二叉树遍历,总结了二叉树的所有遍历情况。这道题所说的中序遍历,就是按照这个顺序:左子树—> 根结点 —> 右子树的顺序来遍历的。那么递归就很好写了,我还是...
用C语言编写的遍历二叉树程序,包括先序、中序、后序、层序4总算法,完整的上机报告,报告中有程序源代码,经编译通过。
接着,通过实现三个不同的遍历方法——preOrderTraversal、inOrderTraversal和postOrderTraversal,展示了如何递归地遍历二叉树。这些遍历方法分别按照根-左-右、左-根-右和左-右-根的顺序访问节点。最后,通过main...
vs2010下运行编写,使用了STL栈,实现了基本的插入、删除、计算深度、查找,主要是遍历,包括递归遍历,以及非递归的前序中序后序遍历,每个函数都有测试用例,如果存在错误,请在给我留言。
数据结构中二叉树遍历,两种方法,递归与非递归,vs2008测试通过。
该文件包括二叉树的头文件(BitTree开头)和堆栈的头文件(Seq开头),另外还实现了编写按层次顺序(同一层自左至右)遍历二叉树的算法、后序递归遍历计算二叉树的深度的算法、判断给定二叉树是否为完全二叉树(通过...
6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树
数据结构实验报告,二叉树实验报告。采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作
建立一颗二叉树,并用递归或非递归的算法选用先序、中序和后序遍历