证明任一结点个数为n的二叉树的高度至少为O（logn)。 【浙江大学2000四（5分)】

已知一棵度为M的树中有n1个度为1的结点，n2个度为2结点，…，nm个度为m的结点，证明其叶结点个数为

【中国海洋大学2004五(15分)】【山东大学1993一、2(4分)】【西安交通大学1996四、1(5分)】【东南大学1999一、4(8分)】

树中最小编号减1； (2)对T中任一顶点v，其右子树中最小编号等于其左子树中的最大编号加1。试说明对二叉树中顶点编号的规则(按何种顺序编号)。【山东大学1992一、1(3分)】

北京工业大学2000二、3(5分)】

结点的序号【中国海洋大学2006五(15分)】

计算机应用一、4(5分)】

的儿子。请问应该用何种结构来存储该二叉树?【东北大学200l一、3(3分)】

四、1(5分)】

连理工大学2005二、2(20／4分)】【江苏大学2004三、5(6分)】

I+2n，n≥0。(5分) (2)利用(1)的结果，试说明：成功查找的平均比较次数s与不成功查找的平均比较次数 u之间的关系可用公式表示s=(1+1／n)u一1，n>=1。【清华大学1998四(10分)】