单项选择(2014年秋程序员软考)

已知某二叉树的先序遍历序列为ABCD,后序遍历序列为CDBA,则该二叉树为【 】。

A、

B、

C、

D、

答案解析

A对非空的二叉树进行先序遍历的过程是:先访问根结点,然后先序遍历左子树,最后先序遍历右子树。题中四个二又树的先序遍历序列分别为ABCD、ABCD、ABCD、ACBD。对非空的二叉树进行后序遍历的过程是...

查看完整答案

讨论

由二叉树的前序和后序遍历序列【 】唯一地确定这棵二叉树。

具有7个结点的互不相识的二叉树共有__________棵。

一个深度为 h 的满 m 叉树有如下性质:第 h 层上的结点都是叶结点,其各层上每个结点有 m 棵非空子树。问:(1)第 k 层最多有多少个结点?(k≤h )(2)整棵树最多有多少个结点?(3)若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,编号为 i 的结汽的双亲结点的编号是什么?编号为 i 的结点的第 j 个孩子结点(若存在)的编号是什么?

证明,由一棵二叉树的前序序列和中序序列可唯一地确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH,中序序列为DGBEAFHC,试画出该二叉树。

已知一棵二叉树的前序遍历结果是ADCEBFIHGJ,中序遍历结果是CDEBAFHGIJ,试画出这棵二叉树。

用一维数组存放的一棵完全二叉树如下:A、B、C、D、E、F、G、H、I、J、K、L写出后序遍历该二叉树时访问结点的顺序。

一棵二叉树按中序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序能否唯一确定这棵二叉树的结构?为什么?若已知一棵二叉树按先序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序,能否唯一确定这棵二叉树的结构?为什么?

对于二叉树T 的两个结点 n1 和 n2 ,我们应该选择树 T 结点的前序、中序和后序中哪两个序列来判断结点 n1 必定是结点 n2的祖先,并给出判断的方法。不需证明判断方法的正确性。

证明一棵二叉树无论进行先序、中序、后序遍历,其叶子结点的相对次序不发生改变。

对二叉排序树进行【 】遍历,可以得到该二叉树所有结点构成的排序序列。