二叉树（三）

二叉树的性质

1、若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^i-1^个结点

2、若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h^-1

3、对任何一棵二叉树, 如果度为0的叶结点个数为n₀，度为2的分支结点个数为n₂，则有n₀＝n₂＋1

4、若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log₂(n + 1) (ps：log₂(n + 1)是log以2为底，n+1为对数)

5、对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

• 若i>0，i位置节点的双亲序号：(i-1)/2；如果i=0，则i为根节点编号，无双亲节点
• 若2i+1<n，则节点i的左孩子序号为2i+1；如果2i+1>=n则i节点无左孩子
• 若2i+2<n，则节点i的右孩子序号为2i+2；如果2i+2>=n则节点i无右孩子

练习：

1.某二叉树共有399个结点，其中199个度为2的结点，则该二叉树中的叶子结点数为（ ）。  A.不存在这样的二叉树  B.200  C.198  D.199

解析：对任何一棵二叉树, 如果度为0的叶结点个数为n₀，度为2的分支结点个数为n₂，则有n₀＝n₂＋1，根据此性质可知叶子节点数为200，故选A。

2.下列数据结构中，不适合采用顺序存储结构的是（ ） A 非完全二叉树 B 堆 C 队列 D 栈

解析：堆、队列、栈都适合采用顺序存储结构，非完全二叉树不适合，故选A。

3.在具有2n个结点的完全二叉树中叶子结点个数为（ ）。 A.n B.n+1 C.n-1 D.n/2

解析：设叶子节点为n0，度为2的节点为n2，度为1的节点为n1，n0+n2+n1 = 2n；由n0 = n2 + 1和n0+n2+n1 = 2n这两个公式可以推出2n0 + n1 = 2n；完全二叉树中度为1的节点个数要么为0要么为1，此时为1才合法，所以n0 = n，故选A。

4.一棵完全二叉树的结点数为531，那么这棵树的高度为（ ）。  A.11  B.10  C.8  D.12

解析：完全二叉树最多情况下节点个数为2^h^-1；最少情况下节点个数为2^h-1^，当h = 10的时候节点个数在该范围内，所以这颗树的高度为10，故选B。

5.一个具有767个结点的完全二叉树，其叶子结点个数为（ ）。  A.383  B.384  C.385  D.386

解析：由上一题可以知道该完全二叉树的高度为10，那么我们先计算前9层的节点个数：2^9^ - 1 = 511，计算第10层的节点个数为：767 - 511 = 256；然后通过第10层的节点个数可以得出第9层中不是叶子节点的个数：256 / 2 = 128；再计算第9层的节点个数：2^9-1^ = 256，然后求出第9层的叶子节点个数：256 -128 = 128，加上第10层的节点个数可以得出叶子节点个数为384，故选B。

二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

链式存储

二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
};
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
};