用树的前序遍历和中序遍历可以导出树的后序遍历

题目
判断题
用树的前序遍历和中序遍历可以导出树的后序遍历
A

B

如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

用二叉树的前序遍历和中序遍历可以导出二叉树的后序遍历。()


参考答案:错误

第2题:

已知__--X树中序遍历序列是cbade,它的后序遍历序列是cbeda,前序遍历序列是【 】。


正确答案:abcde
abcde 解析:前序遍历序列的顺序是先根,再左子树,最后右子树;中序遍历序列的顺序是先左子树,再根,最后右子树;后序遍历序列的顺序是先左子树,再右子树,最后根。后序遍历序列中最后一个是根节点(a),确定根节点后,从中序遍历序列中即可确定左子树(cb)和右子树(de),然后再从后序遍历序列中确定左子树的根(b)及其左子树(c)和右子树(空),从后序遍历序列中确定右子树的根(d)及其左子树(空)和右子树(e),描绘成图,然后求出前序遍历序列。

第3题:

● 已知一个二叉树的先序遍历序列为①、②、③、④、⑤,中序遍历序列为②、①、④、③、⑤,则该二叉树的后序遍历序列为 (57) 。对于任意一棵二叉树,叙述错误的是 (58) 。

(57)A. ②、③、①、⑤、④

B. ①、②、③、④、⑤

C. ②、④、⑤、③、①

D. ④、⑤、③、②、①

(58)A. 由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列

B. 由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列

C. 由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列

D. 由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列


正确答案:C,B
试题(57)、(58)分析
  本题考查数据结构基础知识。
  遍历运算是二叉树的基本运算,主要有先序、中序、后序和层序遍历。
  先序遍历的基本方法:对于非空二叉树,先访问根结点,然后先序遍历根的左子树,最后先序遍历根的右子树。因此,若已知某二叉树的先序遍历序列,则可直接得到其树根结点。
  中序遍历的基本方法:对于非空二叉树,先中序遍历根的左子树,然后访问根结点,最后中序遍历根的右子树。因此,若已知某二叉树的根结点,则一可根据中序遍历序列将该二叉树左右子树上的结点划分开。
  后序遍历的基本方法:对于非空二叉树,首先后序遍历根的左子树,接着后序遍历根的右子树,最后访问根结点。因此,若已知某二叉树的后序遍历序列,则可直接得到其树根结点。
  题中给出的先序遍历序列为①、②、③、④、⑤,可知树根结点是①,据此再结合中序遍历序列②、①、④、③、⑤,可知②是根结点①左子树上的结点,由于是左子树上唯一的一个结点,因此②是根结点①的左孩子。对于右子树上的结点④、③、⑤,因右子树的先序遍历序列为③、④、⑤,因此③是根结点①的右孩子。依此类推,可知④是结点③的左孩子,⑤是结点③的右孩子。该二叉树如下图所示。

 
  从二叉树的遍历过程可知,从先序遍历序列和后序遍历序列中无法将左子树和右子树上的结点区分开,因此,由某棵二叉树的先序遍历序列和后序遍历序列不能构造出该二叉树的中序遍历序列。
  层序遍历二叉树的方法:设二叉树的根结点所在层数为1,则层序遍历二叉树的操作定义为从树的根结点出发,首先访问第一层的结点(根结点),然后从左到右依次访问第二层上的结点,接着是第三层上的结点,依此类推,自上而下、自左至右逐层访问树中各层上的结点。

 

第4题:

若采用孩子兄弟链表作为树的存储结构,则树的后序遍历应采用二叉树的( )。

A.前序遍历算法

B.层次遍历算法

C.后序遍历算法

D.中序遍历算法


正确答案:D
解析:在存储结点信息的同时,附加两个分别指向该结点最左孩子和右邻兄弟的指针域,即可得树的孩子兄弟链表表示。这种存储结构的最大优点是:它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作。其后序遍历对应二叉树的中序遍历;中序遍历对应二叉树的后序遍历;前遍历对应二叉树的前序遍历。

第5题:

二叉树的遍历可以分为三种:前序遍历、_____遍历和后序遍历。


正确答案:
中序 【解析】二叉树的遍历可以分为三种:前序遍历、中序遍历和后序遍历。 前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中,首先访问根结点,然后遍历左子树,最后遍历右子树;并且遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。 中序遍历指在访问根结点、遍历左子树与遍历右子树这三者中,首先遍历左子树,然后访问根结点,最后遍历右子树;并且遍历左、右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树。 后序遍历指在访问根结点、遍历左子树与遍历右子树这三者中,首先遍历右子树,然后访问根结点,最后遍历左子树;并且遍历左、右子树时,仍然先遍历右子树,然后访问根结点,最后遍历左子树。

第6题:

某二叉树的前序遍历序列为abdgcefh,中序遍历序列为dgbaechf,则其后序遍历序列为()。

Abdgecefha

Bgdbecfha

Cbdgaechf

Dgdbehfca


参考答案:D

第7题:

用树的前序遍历和中序遍历可以导出树的【 】遍历。


正确答案:后序
后序 解析:由树的前序遍历和中序遍历可惟一确定一棵树,从而可导出树的后序遍历。基本做法是把前序序列中的第一个节点为根节点(设为R),中序序列中R以前的节点构成R的左子树,R以后的节点构成R的右子树,再对R的左右子树进行上述处理,直到树中找到每个节点为止。

第8题:

对一棵排序二叉树进行( )时,可以得到有序序列。

A)前序遍历

B)中序遍历

C)后序遍历

D)层次遍历


正确答案:B
二叉树的访问有3种方式:前序遍历、中序遍历、后序遍历,但只有中序遍历可以得到有序序列。

第9题:

前序遍历、中序遍历和后序遍历均采用“【 】”的访问顺序。


正确答案:先左后右
先左后右 解析:前序遍历、中序遍历和后序遍历均采用“先左后右”的访问顺序,在同一棵二叉树的前序遍历序列、中序遍历序列和后序遍历序列中,所有叶子结点的先后顺序完全相同。

第10题:

在一棵二叉树的前序遍历、中序遍历、后序遍历所产生的序列中,所有叶结点的先后顺序( )。A.都不相同B.完全相同C.前序和中序相同,而与后序不同D.中序和后序相同,而与前序不同


正确答案:B
无论是前序,中序,后序遍历,序列的变化只是根节点(根节点和子树的根节点)的变化,如前序遍历,先根节点,左子树,右子树,在子树里也是这样

更多相关问题