数据结构考研分类复习真题 第六章 树和二叉树 (四)[5]

．在一棵表示有序集S的二叉搜索树(binary search tree)中任意一条从根到叶结点的路径将S分为部分在该路径左边结点中的元素组成的集合Sl在该路径上的结点中的元素组成的集合S在该路径右边结点中的元素组成的集合SS=S∪S∪S若对于任意的a∈Slb∈Sc∈S是否总有a≤b≤c?为什么?【清华大学 四(分)】【武汉大学 三】

．试证明在具有n(n>=)个结点的m次树中有n(m)+个指针是空的【复旦大学四(分)】

．对于任何一棵非空的二叉树假设叶子结点的个数为n而次数为的结点个数为n请给出n和n之间所满足的关系式n=f(n)要求给出推导过程【复旦大学 五 (分)】

．对于任意一棵非空的二叉树T我们用n表示T中叶子结点的个数用n表示T中有两棵非空子树的结点的个数()给出n和n所满足的关系式()证明你在()中给出的关系式成立【复旦大学 三 (分)】

．试求有n个叶结点的非满的完全二叉树的高度;【中科院计算所 五 (分)】

．对于具有n个叶子结点且所有非叶子结点都有左右孩子的二叉树

()试问这种二叉树的结点总数是多少？(分)

()试证明=其中:li表示第i个叶子结点所在的层号(设根结点所在层号为)(分)【北方交通大学 三 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []