堆和二叉树

发表于 | 更新于 | 阅读次数：

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2^k-1个叶子节点，至多有2^k-1个节点。

  1. 一般二叉树性质

    • 在非空二叉树的i层上，至多有2^i-1个节点(i>=1)。

    • 在深度为K的二叉树上最多有2^k-1个结点（k>=1)。

    • 对于任何一棵非空的二叉树,如果叶节点个数为n0，度数为2的节点个数为n2，则有: n0 = n2 + 1

  2. 完全二叉树性质

    • 具有n的结点的完全二叉树的深度为log2n+1.

    • 如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（1<=i<=n）有

    1.如果i=1，则节点是二叉树的根，无双亲，如果i>1，则其双亲节点为[i/2]，向下取整

    2.如果2i>n那么节点i没有左孩子，否则其左孩子为2i

    3.如果2i+1>n那么节点没有右孩子，否则右孩子为2i+1

  3. 二叉树遍历

    • 前序遍历

    先访问根结点，再先序遍历左子树，最后再先序遍历右子树即根—左—右。

    1
    2
    3
    4
    5
    6
    7
    void PreOrderTraverse(BiTree t) {
        if(t != NULL) {
            printf("%c ", t->data);
            PreOrderTraverse(t -> lchild);
            PreOrderTraverse(t -> rchild);
        }
    }
    • 中序遍历

    先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树即左—根—右。

    1
    2
    3
    4
    5
    6
    7
    void InOrderTraverse(BiTree t) {
        if(t != NULL) {
            InOrderTraverse(t -> lchild);
            printf("%c ", t->data);
            InOrderTraverse(t -> rchild);
        }
     }
    • 后序遍历

    先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。

    1
    2
    3
    4
    5
    6
    7
    void PostOrderTraverse(BiTree t) {
        if(t != NULL) {
            PostOrderTraverse(t -> lchild);
            PostOrderTraverse(t -> rchild);
            printf("%c ", t->data);
        }
    }

  4. 建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct node {  
    struct node *lchild;  
    struct node *rchild;  
    char data;  
}BiTreeNode, *BiTree;

void createBiTree(BiTree &T, char array[]) {  
    char c;  
    c = array[N];  
	N++;
    if('#' == c)  
        T = NULL;  
    else {
        if(T == NULL)
		    return ;
		else {
            T = new BiTreeNode;  
            T -> data = c;  
            createBiTree(T -> lchild, array);  
            createBiTree(T->rchild, array);  
		}  
	}
}

例题 YZOJ P1196 Postorder Traversal

大体思路：因为后序遍历的最后一个字母就是根结点，在中序遍历中根结点的左边就是左子树，右边就是右子树，所以可以计算出左子树的结点总数和右子树的节点总数，再用结点的总数将后序遍历中的结点分开，分开后就是两个子树的后序遍历。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

string in, after;

void search(string in,string after) {
    int len = in.size();
    if(len <= 0)
        return;
    char ch = after[len - 1];
    cout << ch;
    int k = in.find(ch);
    search(in.substr(0, k), after.substr(0, k));
    search(in.substr(k + 1), after.substr(k, len - 1 - k));
}

int main() {
    cin >> in >> after;
    search(in, after);
    return 0;
}

堆是一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。
  • 将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆主要的作用是用来实现优先队列。

堆分为大根堆和小根堆，下面用小根堆做示例。

  1. 插入操作

手写实现：

1
2
3
4
5
6
void push(int x) {//swap是交换两个数的值
    q[++sz] = x;
    int pos = sz;
    while(pos > 1 && q[pos >> 1] > q[pos])
        swap(q[pos], q[pos >> 1]), pos = pos >> 1;
}

  1. 删除操作

手写实现:

1
2
3
4
5
6
7
8
9
10
11
12
void pop() {//swap是交换两个数的值
    int rt = q[sz--], pos = 1;
    q[pos] = rt;
    while(true) {
        int lv = (pos << 1) > sz ? inf : q[pos << 1];
        int rv = (pos << 1 | 1) > sz ? inf : q[pos << 1 | 1];
        int v = min(lv, rv), nt = lv < rv ? (pos << 1) : (pos << 1 | 1);
        if(q[pos] > v)
            swap(q[pos], q[nt]), pos = nt;
        else break;
    }
}

  1. 其他操作

手写实现：

1
2
3
4
5
6
7
8
9
10
11
int top() {//返回队首元素
    return q[1];
}

int size() {//返回队列大小
    return sz;
}

bool empty() {
    return sz == 0 ? true : false;
}

STL实现优先队列

1
2
3
4
5
6
7
8
empty()//如果队列为空，则返回真
pop()//删除对顶元素，删除第一个元素
push()//加入一个元素
size()//返回优先队列中拥有的元素个数
top()//返回优先队列对顶元素，返回优先队列中有最高优先级的元素
//在默认的优先队列中，优先级高的先出队。在默认的int型中先出队的为较大的数。
//需要头文件
#include <queue>

实际上你可以去YZOJ里的AAS里有一个pb_ds库的介绍，可以实现优先队列，速度接近手写。

例题 YZOJ P2704 [NOIP 2016 四校联训 Round 4]打败黑熊

大体思路：维护一个小根堆，每个守卫机关相当于向堆中加入一个数，每个审判机关相当于删除堆中最小值，直到堆中的元素个数小于上限。最后直接把堆中所有的数加起来。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//顺便演示一下pb_ds中的priority_queue
#include <cstdio>
#include <ext/pb_ds/priority_queue.hpp>//注意要加这个头文件

using namespace std;

__gnu_pbds::priority_queue<int,greater<int> > q;//声明方式  
int n, m;
char st[6];

inline int read() {//快读
	#define in(n) n=read()
	register int x = 0; register char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar());
	for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return x;
}

int main() {
    in(n), in(m);
    for(int i = 1, t; i <= n; i++) {
        scanf("%s", &st);
        in(t);
        if(st[0] == 'd') {
            q.push(t);
            continue;
        }
        if(t <= 0) {
            puts("Rabbit can not beat bear.");
            return 0;
        }
        while(q.size() >= t)
            q.pop();
    }
    int ans = 0, sz = 0;
    while(!q.empty()) {
        ans += q.top();
		sz++;
        q.pop();
    }
    if(sz >= m)
        printf("%d\n", ans);
	else {
        puts("Rabbit can not beat bear.");
        return 0;   
    }
    return 0;
}

$\color{gray}{\mathcal{By}}$ $\color{gray}{\mathfrak{NULL}}$