堆和二叉树数据结构初阶：C/C++ 实现与理论

前言

本文讲解堆和二叉树的理论部分及习题实践。

理论部分

二叉树性质

1. 对于任意一个二叉树，度为 0 的节点比度为 2 的节点多一个。
2. 数组存储公式（根节点下标为 0）：
   • parent = (child - 1) / 2
   • leftchild = parent * 2 + 1
   • rightchild = parent * 2 + 2
3. 数组存储二叉树只适合完全二叉树，否则空间浪费较多。
4. 第 n 层有 2^(n-1) 个节点。
5. 节点个数 = 边数 + 1；边数 = 节点的度相加之和。
6. 树度：树中节点度的最大值。

堆是完全二叉树。

• 小根堆：所有父亲的值小于等于孩子（最小在根节点）。
• 大根堆：所有父亲的值大于等于孩子（最大在根节点）。
• 需与二叉搜索树区分（后者对左右孩子放置有要求）。

堆的模拟实现（以大根堆为例）

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int HPDataType;

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

void HeapInit(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
int HeapSize(HP* php);
void AdjustUp(HPDataType* a, int child);
void AdjustDown;
 ;

  {
    assert(php);
    php->a = (HPDataType*)((HPDataType) * );
     (php->a == ) {
        perror();
        ;
    }
    php->size = ;
    php->capacity = ;
}

  {
    HPDataType x = *p1;
    *p1 = *p2;
    *p2 = x;
}


  {
     parent = (child - ) / ;
     (child > ) {
         (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - ) / ;
        }  {
            ;
        }
    }
}

  {
    assert(php);
     (php->size == php->capacity) {
        HPDataType* tmp = (HPDataType*)(php->a, (HPDataType) * php->capacity * );
         (tmp == ) {
            perror();
            ;
        }
        php->a = tmp;
        php->capacity *= ;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - );
}


  {
     child = parent *  + ;
     (child < n) {
        
         (child +  < n && a[child + ] < a[child]) {
            ++child;
        }
         (a[child] < a[parent]) {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent *  + ;
        }  {
            ;
        }
    }
}

  {
    assert(php);
    
    Swap(&php->a[], &php->a[php->size - ]);
    php->size--;
    AdjustDown(php->a, php->size, );
}

  {
    assert(php);
     php->size;
}