由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。

题目

由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。

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

第1题:

试找出满足下列条件的二叉树 ① 先序序列与后序序列相同 ②中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同


参考答案:先序遍历二叉树的顺序是“根—左子树—右子树”,中序遍历“左子树—根—右子树”,后序遍历顺序是:“左子树—右子树―根",根据以上原则有
  ① 或为空树,或为只有根结点的二叉树
  ② 或为空树,或为任一结点至多只有左子树的二叉树.
  ③ 或为空树,或为任一结点至多只有右子树的二叉树.
  ④ 或为空树,或为任一结点至多只有右子树的二叉树

第2题:

树的后序遍历序列等同于该树对应的二叉树的______。

A.先序序列

B.中序序列

C.后序序列

D.不确定


正确答案:B
解析:树的后序遍历是指先依次后序遍历每棵子树,然后访问根结点。当树用二叉树表示法(也叫孩子兄弟表示法)存储时,可以找到唯一的一棵二叉树与之对应,我们称这棵二叉树为该树对应的二叉树。那么根据这个法则可知,树的后序遍历序列等同于该树对应的二叉树的中序遍历。例如,图3-80展示了一个转化实例。由图3-80可以看出,树的后序遍历和其对应的二叉树的中序遍历都是BDCEA。注意,对于树而言,没有中序遍历。

第3题:

给定二叉树的先序和后序遍历序列,可以唯一的确定这棵二叉树。()

此题为判断题(对,错)。


正确答案:错

第4题:

简述由二叉树的前序、中序和后序遍历序列如何确定二叉树。


正确答案: 在3种遍历序列中,前序序列和中序序列、中序序列和后序序列能唯一确定一棵二叉树,因为前序序列或后序序列能确定二叉树的根结点而中序序列能确定根的左、右子树。前序序列和后序序列不能唯一确定一棵二叉树,但注意树的先根序列和后根序列能唯一地确定该树,因为树的后根序列就是二叉树的中序序列。

第5题:

已知二叉树的中序序列和后序序列均为ABCDEF,则该二叉树的先序序列为 ( )

A.FEDCBA

B.ABCDEF

C.FDECBA

D.FBDCEA


正确答案:A
解析:对于前序遍历、中序遍历和后序遍历,将结点按其访问的先后次序排列起来,所得到的结点序列分别称为前序序列、中序序列和后序序列。

第6题:

二叉树结点的中序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。()


参考答案:正确

第7题:

由二叉树的先序和后序遍历序列不能唯一确定这棵二叉树。()

此题为判断题(对,错)。


参考答案:正确

第8题:

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

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

B. ①、②、③、④、⑤

C. ②、④、⑤、③、①

D. ④、⑤、③、②、①

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

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

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

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


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

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

 

第9题:

如图所示的二叉树,给出中序遍历序列、先序遍历序列和后序遍历序列。
(1)dgbaechif
(2)abdgcefhi
(3)gdbeihfca

第10题:

后序序列和中序序列能唯一确定一棵二叉树。


正确答案:正确