数据结构核心：二叉树概念、性质与堆的实现

2.4 二叉树的性质

1. 若规定根结点的层数为 1，则一棵非空二叉树的第 i 层上最多有 2^(i-1) 个结点。
2. 若规定根结点的层数为 1，则深度为 h 的二叉树的最大结点数是 2^h-1。
3. 对任何一棵二叉树，如果度为 0 其叶结点个数为 n0，度为 2 的分支结点个数为 n2，则有 n0＝n2＋1。

假设二叉树有 N 个结点： 从总结点数角度考虑：N = n0 + n1 + n2 ①//n1 为度为 1 的节点 从边的角度考虑，N 个结点的任意二叉树，总共有 N-1 条边 因为二叉树中每个结点都有双亲，根结点没有双亲，每个节点向上与其双亲之间存在一条边 因此 N 个结点的二叉树总共有 N-1 条边 因为度为 0 的结点没有孩子，故度为 0 的结点不产生边; 度为 1 的结点只有一个孩子，故每个度为 1 的结点产生一条边; 度为 2 的结点有 2 个孩子，故每个度为 2 的结点产生两条边，所以总边数为：n1+2n2 故从边的角度考虑：N-1 = n1 + 2n2 ② 结合① 和 ②得：n0 + n1 + n2 = n1 + 2*n2 - 1 即：n0 = n2 + 1

4. 若规定根结点的层数为 1，具有 n 个结点的满二叉树的深度，h=log2(n+1)，{log2（n+1）是以 2 为底，n+1 为对数}
5. 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：
   • 若 i>0，i 位置结点的双亲序号：(i-1)/2；i=0，i 为根结点编号，无双亲结点
   • 若 2i+1<n，左孩子序号：2i+1，2i+1>=n 否则无左孩子
   • 若 2i+2<n，右孩子序号：2i+2，2i+2>=n 否则无右孩子

练习

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

根据性质 3 可以得出 n0=n2+1,答案为：B

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

堆的底层是数组，栈底层是数组，队列也可以用数组来实现，而非完全二叉树不适用，满二叉树和完全二叉树可以按顺序储存，答案为：A

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

可以根据公式进行推导，假设 n0 是度为 0 的结点总数（即叶子结点数），n1 是度为 1 的结点总数，n2 是度为 2 的结点总数，则： ① n= n0+n1+n2（其中 n 为完全二叉树的结点总数）；又因为一个度为 2 的结点会有 2 个子结点，一个度为 1 的结点会有 1 个子结点，除根结点外其他结点都有父结点， ② n= 1+n1+2n2；由①、②两式把 n2 消去得：n= 2n0+n1-1，由于完全二叉树中度为 1 的结点数只有两种可能 0 或 1，由此得到 n0=n/2 或 n0=(n+1)/2。 简便来算，就是 n0=n/2，其中 n 为奇数时（n1=0）向上取整；n 为偶数时（n1=1）。可根据完全二叉树的结点总数计算出叶子结点数。所以答案为：A

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

根据性质 4 得出：答案为 B

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

简便来算，就是 n0=n/2，其中 n 为奇数时（n1=0）向上取整；n 为偶数时（n1=1）。可根据完全二叉树的结点总数计算出叶子结点数。所以答案为：B

3. 二叉树顺序结构及实现

3.1 二叉树的顺序结构

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

3.2 堆的结构及概念

堆的性质：

堆中某个结点的值总是不大于或不小于其父结点的值； 堆总是一棵完全二叉树。

练习

1. 下列关键字序列为堆的是：（） A 100,60,70,50,32,65 B 60,70,65,50,32,100 C 65,100,70,32,50,60 D 70,65,100,32,50,60 E 32,50,100,70,65,60 F 50,100,70,65,60,32

答案为：A

2. 已知小根堆为 8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（）。 A 1 B 2 C 3 D 4

8 与 12 交换位置后，12 与 15 比较，在与 10 比较，交换 10 与 12，最后 12 在与 16 比较 一共比较了 3 次 答案为 C

3.3 堆的实现

3.3.1 堆的向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};

3.3.2 堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根结点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子结点的子树开始调整，一直调整到根结点的树，就可以调整成堆。

int a[] = {1, 5, 3, 8, 7, 6};

3.3.3 堆的插入

先插入一个 10 到数组的尾上，再进行向上调整算法，直到满足堆。

3.3.4 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

3.3.5 堆的代码实现

typedef int HPDataType;

struct Heap {
    HPDataType* a;
    int size;
    int capacity;
} HP;

void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
HPDataType HPTop(HP* php);
bool HPEmpty(HP* php);

// 堆接口实现
void HPInit(HP* php) {
    assert(php);
    php->a = NULL;
    php->size = php->capacity = 0;
}

void HPDestroy(HP* php) {
    assert(php);
    free(php->a);
    php->a = NULL;
    php->size = php->capacity = 0;
}

void Swap(HPDataType* p1, HPDataType* p2) {
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void AdjustUp(HPDataType* a, int child) {
    // 初始条件
    // 中间过程
    // 结束条件
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

void HPPush(HP* php, HPDataType x) {
    assert(php);
    if (php->size == php->capacity) {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
        if (tmp == NULL) {
            perror("realloc fail");
            return;
        }
        php->a = tmp;
        php->capacity = newcapacity;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - 1);
}

void AdjustDown(HPDataType* a, int n, int parent) {
    // 先假设左孩子小
    int child = parent * 2 + 1;
    while (child < n) // child >= n 说明孩子不存在，调整到叶子了
    {
        // 找出小的那个孩子
        if (child + 1 < n && a[child + 1] > a[child]) {
            ++child;
        }
        if (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

// logN
void HPPop(HP* php) {
    assert(php);
    assert(php->size > 0);
    Swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;
    AdjustDown(php->a, php->size, 0);
}

HPDataType HPTop(HP* php) {
    assert(php);
    assert(php->size > 0);
    return php->a[0];
}

bool HPEmpty(HP* php) {
    assert(php);
    return php->size == 0;
}