• 关注优题吧，注册平台账号.

题吧，智能辅助学习中心
  2. 数据结构与算法
  3. 树和二叉树
  4. 树的概念与性质
  2. 知识库
  3. 试卷库

问答题（1998年中国科学院自动化所）

已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，...，Nm个度为m的结点。试问该树中有多少个叶子结点？

答案解析

该树中叶子结点个数为N0.

则 该树结点个数为N0+N1+...+Nm=sigma 0 m 西格马Ni

又 该树结点个数为 1+sigma 1 m 西格马iNi

所以 N0+sigma 1 m 西格马Ni=1+sigma 1 m 西格马iNi

N0=1+sigma 1 m 西格马(i-1)Ni

讨论

数据结构与算法

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

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

如果只考虑有序树的情形，那么具有7个结点的不同形态的树共有【】

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

对于前序遍历和中序遍历结果相同的二叉树为__________；对于前序遍历和后序遍历结果相同的二叉树是为__________。一般二叉树只有根结点的二叉树要结点无左孩子的二叉树根结点无右孩子的二叉树所有结点只有左子树的二叉树所有结点只有右子树的二叉树

对下列二叉树进行后序遍历的结果是【 】

支持子程序调用的数据结构是【 】。

某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是【 】。

一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有结点个数为【 】。

某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）【 】

树的概念与性质

树是结点的集合，它的根结点数目是【 】

某二又树的先序遍历序列为 ABCDFGE，中序遍历序列为 BAFDGCE。以下关于该二又树的叙述中，正确的是【 】。

对于一般的树结构，可以采用孩子-兄弟表示法，即每个结点设置两个指针域，一个指针(左指针)指示当前结点的第一个孩子结点，另一个指针(右指针)指示当前结点的下一个兄弟结点。某树的孩子-兄弟表示如下图所示。以下关于结点 D 与 E 的关系的叙述中，正确的是【 】。

对下图所示的二叉树进行中序遍历(左子树、根结点、右子树)的结果是【 】。

已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，...，Nm个度为m的结点。试问该树中有多少个叶子结点？

已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，...，Nm个度为m的结点。试问该树中有多少个叶子结点？

已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，...，Nm个度为m的结点。试问该树中有多少个叶子结点？

已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，...，Nm个度为m的结点。试问该树中有多少个叶子结点？

已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，...，Nm个度为m的结点。试问该树中有多少个叶子结点？

已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，...，Nm个度为m的结点。试问该树中有多少个叶子结点？

树和二叉树

有n个数顺序（依次）进栈，则出栈顺序有Cn种。Cn=×

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为【 】

一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 __________。

深度为5的满二叉树有__________个叶子结点。

已知一棵二叉树的树形如图，若其后序遍历为 f、d、b、e、c、a，则其先序列为【 】

某二叉树中度为2的结点有18个，则该二叉树中有__________个叶子结点。

在深度为7的满二叉树中，叶子结点的个数为【 】

啥夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

线索二叉树是一种【 】结构。

二叉树中，具有两个子女的结点的中序后继结点最多只能有一个子女。