考研专业课之统考计算机蓝宝书(20)
3.2.3 二叉树的遍历
1.二叉树的遍历方法及其递归实现
二叉树的遍历是指按照某种顺序访问二叉树中的每个结点,使每个结点被访问一次且仅被访问一次。通过一次完整的遍历,可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说,遍历操作使非线性结构线性化。
由二叉树的定义可知,一棵由根结点、根结点的左子树和根结点的右子树三部分组成。因此,只要依次遍历这三部分,就可以遍历整个二叉树。限定先左后右,只有前三种方式,即DLR(称为先序遍历)、LDR(称为中序遍历)和LRD(称为后序遍历)。
(1). 先序遍历(DLR)
先序遍历的递归过程为:若二叉树为空,遍历结束。否则,
1 访问根结点;
2 先序遍历根结点的左子树;
3 先序遍历根结点的右子树。
(2). 中序遍历(LDR)
中序遍历的递归过程为:若二叉树为空,遍历结束。否则,
1 中序遍历根结点的左子树;
2 访问根结点;
3 中序遍历根结点的右子树。
(3). 后序遍历(LRD)
后序遍历的递归过程为:若二叉树为空,遍历结束。否则,
1 后序遍历根结点的左子树;
2 后序遍历根结点的右子树。
3 访问根结点;
(4). 层次遍历
所谓二叉树的层次遍历,是指从二叉树的第一层(根结点)开始,从上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。
下面讨论层次遍历的算法。
由层次遍历的定义可以推知,在进行层次遍历时,对一层结点访问完后,再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问,这样一层一层进行,先遇到的结点先访问,这与队列的操作原则比较吻合。因此,在进行层次遍历时,可设置一个队列结构,遍历从二叉树的根结点开始,首先将根结点指针入队列,然后从对头取出一个元素,每取一个元素,执行下面两个操作:
1 访问该元素所指结点;
2 若该元素所指结点的左、右孩子结点非空,则将该元素所指结点的左孩
子指针和右孩子指针顺序入队。
此过程不断进行,当队列为空时,二叉树的层次遍历结束。
2. 二叉树遍历的非递归实现
(1). 先序遍历的非递归实现
在下面算法中,二叉树以二叉链表存放,一维数组stack[MAXNODE]用以实现栈,变量top用来表示当前栈顶的位置。
(2). 中序遍历的非递归实现
中序遍历的非递归算法的实现,只需将先序遍历的非递归算法中的Visite(p->data)移到p=stack[top]和p=p->rchild之间即可。
>" src="http://i1.w.hjfile.cn/doc/200811/32502.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/32502.gif">>" src="http://i1.w.hjfile.cn/doc/200811/26508.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/26508.gif">>" src="http://i1.w.hjfile.cn/doc/200811/52955.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/52955.gif">>" src="http://i1.w.hjfile.cn/doc/200811/71602.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/71602.gif">>" src="http://i1.w.hjfile.cn/doc/200811/11087.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/11087.gif">
猜你喜欢
- 出国留学中介前十名介绍 沪江是最好的选择
想要出国留学却没有时间没有精力去办理出国留学的手续,这个时候寻找一个好的出国留学中介就成了最好的办法,好的中介可以让自己更合理的去挑选自己喜欢的国家和学校,而且中介还有出国培训相关的内容,这...
- 日本动漫游戏:学校的圣域
feng社第9作第1弹《彼女のセイイキ(她的圣域)》,而系列的第2弹《妹的圣域》已于2015年08月28日发售,系列第3弹《学校的圣域》在2016年11月发售。
- 日本惊悚恐怖电影《裸体之夜:掠夺狂爱》
《裸体之夜2:掠夺狂爱》是由石井隆执导,竹中直人、佐藤宽子等领衔主演日本惊悚情色电影。该片讲述了主人公红次郎替年轻女孩加藤怜寻找叫“多绘”的救命恩人,结果踏入充满危机的“粉红”漩涡中。
- 秒变单身狗:哪些话不能对恋人说
恋爱初期总是美好而甜蜜的,然而两人长期处下来,就会发现对方的不足之处。生气起来口不择言,结果深深的伤害到两人的感情。这期给大家介绍一些对恋人可不能说的一些话。
- 日本礼仪:你真的会斟酒吗?
走进社会,我们不仅要在工作上努力努力再努力,还要一边学习一些社交礼仪。酒会作为一种常见的社交活动,学会其中的斟酒礼仪也是一门学问。今日,小编给大家整理了日本的斟酒礼仪供大家参考学习。
- 汉字词和成语 - 속담_뜻이 비슷한 속담
가재는 게와 생김새가 비슷하기 때문에 게 편을 든다는 말로, 서로 인연이 있는 것끼리 한편이 된다는 뜻이다. 비슷한 속담으로 '초록은 동색', … 가재는 게와 생김새가 비슷하기 때문에 게 ...