[详细完整版]数据结构07.doc

第七章 树和二叉树习题 7.1画出由4个结点所构成的所有形态的树（假设是无序树）。 7.2已知一棵树的度为4，其中度为4的结点的数目为3，度为3的结点的数目为4，度为 2的结点的数目为5，度为1的结点的数目为2，请求出该树中的叶子结点的数目。 7.3如果已知一棵二叉树有20个叶子结点，有10个结点仅有左孩子，15个结点仅有右 孩子，求出该二叉树的结点数目。 7.4已知某完全二叉树有100个结点，试用三种不同的方法求出该二叉树的叶子结点数 。 7.5如果已知完全二叉树的第6层有5个叶子，试画出所有满足这一条件的完全二叉树 ，并指出结点数目最多的那棵完全二叉树的叶子结点数目。 7.6在编号的完全二叉树中，判断编号为i和j的两个结点在同一层的条件是什么？ 7.7设计算法以求解编号为i和j的两个结点的最近的公共祖先结点的编号。 7.8分别求出下图中二叉树的三种遍历序列。 7.9分别描述满足下面条件的二叉树的特征： （1）先序序列和中序序列相同。 （2）先序序列和后序序列相反。 7.10证明：由二叉树的先序序列和中序序列能唯一确定一棵二叉树，并分别由下面的 两个序列构造出相应的二叉树： 先序：A