若结点x是二叉树的根结点或二叉树bt中无结点x ，则返回“空” 。
(7) LeftChild（bt ，x）：求左孩子 。
若结点x为叶子结点或x不在bt中 ，则返回“空” 。
(8) RightChild（bt ，x）：求右孩子 。
若结点x为叶子结点或x 。

8、不在bt中 ，则返回“空” 。
(9) Traverse（bt）: 遍历操作 。
按某个次序依次访问二叉树中每个结点一次且仅一次 。
(10) Clear（bt）： 清除操作 。
将二叉树bt置为空树,二叉树的性质,性质1: 在二叉树的第i层上至多有2i-1个结点(i1) 。
证明： 用数学归纳法 。
归纳基础：当i=1时 ， 整个二叉树只有一根结点 ， 此时2i-1=20=1 ， 结论成立 。
归纳假设：假设i=k时结论成立 ， 即第k层上结点总数最多为2k-1个 。
现证明当i=k+1时 ，结论成立： 因为二叉树中每个结点的度最大为2 ， 则第k+1层的结点总数最多为第k层上结点最大数的2倍 ， 即22k-1=2(k+1)-1 ， 故 。

9、结论成立,性质2: 深度为k的二叉树至多有2k-1个结点（k1） 。
证明：因为深度为k的二叉树 ， 其结点总数的最大值是将二叉树每层上结点的最大值相加 ， 所以深度为k的二叉树的结点总数至多为,故结论成立,性质3: 对任意一棵二叉树T ， 若终端结点数为n0 ， 而其度数为2的结点数为n2 ， 则n0=n2+1 。
证明：设二叉树中结点总数为n ，n1为二叉树中度为1的结点总数 。
因为二叉树中所有结点的度小于等于2 ， 所以有 n=n0+n1+n2 设二叉树中分支数目为B ，因为除根结点外 ，每个结点均对应一个进入它的分支 ， 所以有 n=B+1,又因为二叉树中的分支都是由度为1和度为2的结点发出 ，所以分支数目为 B=n 。

10、1+2n2 整理上述两式可得到 n=B+1=n1+2n2+1 将n=n0+n1+n2代入上式 ， 得出n0+n1+n2=n1+2n2+1 ， 整理后得n0=n2+1 ， 故结论成立,满二叉树,深度为k且有2k-1个结点的二叉树 。
在满二叉树中 ， 每层结点都是满的 ， 即每层结点都具有最大结点数 。
图6.3(a)所示的二叉树 ， 即为一棵满二叉树 。
满二叉树的顺序表示 ， 即从二叉树的根开始 ，层间从上到下 ，层内从左到右 ， 逐层进行编号（1 ，2 ，，n） 。
例如图6.3(a)所示的满二叉树的顺序表示为(1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，10 ，11 ，12 ，13 ，14 ，15,完全二叉树： 深度为 。

11、k ， 结点数为n的二叉树 ， 如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号一一对应 ， 则为完全二叉树 ，如图6.3(b)所示 。
满二叉树必为完全二叉树 ，而完全二叉树不一定是满二叉树,图6.3 满二叉树与完全二叉树,性质4：具有n个结点的完全二叉树的深度为log2n+1 。
证明：假设n个结点的完全二叉树的深度为k ， 根据性质2可知 ， k-1层满二叉树的结点总数为 n1=2k-1-1 k层满二叉树的结点总数为 n2=2k-1 显然有n1nn2 ， 进一步可以推出n1+1nn2+1 。
将n1=2k-1-1和n2=2k-1代入上式 ， 可得2k-1n2k ， 即k-1log2nk 。
因为k是整数 ， 所以k-1= 。

12、log2n ， k=log2n+1, 故结论成立 。
,性质5: 对于具有n个结点的完全二叉树 ，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号 ，则对于任意的序号为i的结点有： （1） 如i=1 ， 则序号为i的结点是根结点 ，无双亲结点； 如i1 ，则序号为i的结点的双亲结点序号为i/2 。
（2） 如2in ， 则序号为i的结点无左孩子；如2in ， 则序号为i的结点的左孩子结点的序号为2i 。
（3） 如2i1n ， 则序号为i的结点无右孩子；如2i1n ，则序号为i的结点的右孩子结点的序号为2i1,可以用归纳法证明其中的（2）和（3）： 当i=1时 ， 由完全二叉树的定义知 ， 如果2i=2n ， 说 。

13、明二叉树中存在两个或两个以上的结点 ， 所以其左孩子存在且序号为2； 反之 ， 如果2n ， 说明二叉树中不存在序号为2的结点 ， 其左孩子不存在 。
同理 ， 如果2i+1=3n ，说明其右孩子存在且序号为3；如果3n ， 则二叉树中不存在序号为3的结点 ，其右孩子不存在 。
假设对于序号为j(1ji)的结点 ， 当2jn时 ， 其左孩子存在且序号为2j ， 当2jn 时 ， 其左孩子不存在；当2j+1n时 ，其右孩子存在且序号为2j+1 ， 当2j+1n时 ， 其右孩子不存在,当i=j+1时 ， 根据完全二叉树的定义 ，若其左孩子存在 ，则其左孩子结点的序号一定等于序号为j的结点的右孩子的序号加1 ，即其左孩子结点的序号等于 （2j+1）+1=2 。

14、（j+1）=2i ，且有2in；如果2in ，则左孩子不存在 。
若右孩子结点存在 ， 则其右孩子结点的序号应等于其左孩子结点的序号加1 ， 即右孩子结点的序号为2i+1 ， 且有2i+1n；如果2i+1n ， 则右孩子不存在 。

来源：(未知)

【学习资料】网址：/a/2021/0323/0021754656.html

标题：概念|树的概念和定义( 二 )