算法第五课

作者: Stark_Dylan | 来源:发表于2016-12-30 18:00 被阅读622次

算法第五课
二叉树遍历
二叉树序列化和反序列化
画画
不适配的的训练/开发/测试集
第五课生成学习算法
2017-07-03
第五课作业
第三单元第五课 G大调正三和弦弹奏与属之属7的使用
第一单元第五课变化音(续) 切分音、五线谱上的音符与休止

title: 算法第五课
date: 2016-10-19 12:55:39
tags: 算法
thumbnail: http://img2.imgtn.bdimg.com/it/u=4054526222,762120886&fm=21&gp=0.jpg

树

什么是树，没有回路的就是树，有回路的就是图。树有很多特性：

树中的任意两个点有且仅有唯一的一条路
树中如果有n个点，那么它一定恰好有n-1条边
在树中任意两点之间加一条，就会构成回路

常见的树，有家谱、操作系统的文件夹，目录等。并且我们规定，只要是没有回路的连通无向图就是树。为了确定每一棵树的形态，我们在对一棵树进行讨论的时候，将树中每个点称为结点或者节点，在树中，我们可以指定一个特殊的节点-根。有一个根的树叫做有根树。根又叫做根节点，一棵树有且仅有一个根节点。根节点又可以被称为祖先，接下来就是父节点（没有父节点的节点就是根），子节点。如果一个节点没有子节点，这个节点被称为叶节点。如果一个节点既不是根节点也不是叶节点，也可以被称为内部节点，每个节点有深度，深度指的是从根到这个节点的层数（根为第一层）。

二叉树

二叉树是一种特殊的数，二叉树的特点是，每个节点最多有2个子节点，左边的叫做左节点，右边的叫做右节点。或者说，每个节点最多有2个子树，更加严格的递归定义是：二叉树要么为空，要么由根节点、左子树、右子树构成，而左子树，右子树分别又是一棵二叉树。

二叉树还有两种特殊定义的二叉树，叫做满二叉树（二叉树中每个内部节点都有2个子节点，严格的定义是深度为h且有2^h-1个节点的树）和完全二叉树（一棵树除了最右边的位置上有一个或是几个节点缺少外，其他是丰满的，则是完全二叉树，严格的定义是：若设二叉树的高度为h，除第h层外，其他各层的节点树都达到最大个数，第h层从右向左连续缺若干节点，一个树，有右节点必有左节点）。可以将满二叉树理解为极其完美的完全二叉树。

先想一想，一棵完全二叉树如何做存储呢？其实二叉树种，父节点与子节点有着很不错的规律，只需用一个一维数组就可以存储完全二叉树：

通过上图我们发现，如果完全二叉树的一个编号为K，那么他左子节点的编号是2*K，右子节点的编号是2*K + 1，如果已知子节点的编号为X，那么父节点的编号就是X/2。如果一个完全二叉树有N个节点，那么这个完全二叉树的高度为

logN

即最多有logN层节点。完全二叉树最典型的应用就是堆。

堆，神奇的优先队列

什么是堆，堆就是一种特殊的完全二叉树

如上图，有没有发现这棵二叉树有一个特点，就是所有的父节点都比子节点要小（圆圈里边的是值，上面的树是编号），符合这样特点的完全二叉树被我们称为最小堆，反之，如果父节点都比子节点要大，称为最大堆。

假如有14个数：

99, 5, 36, 7, 22, 17, 46, 12, 2, 19, 25, 28, 1, 92

请找出这14个数中最小的数，你可能直接想到了，一个循环不就好了么

for (int i = 1; i <= 14; i ++) {
    if (a[i] < min) {
      min = a[i];
    }
}

这种方法的时间复杂度是O(14)，也就是O(N)。假如有14次这样的操作，就是O(14^2)，有没有更好的方法呢？堆这个特殊的结构恰好能够很好的解决这个问题。首先我们把14个数字按照最小堆的要求放入一棵完全二叉树，就像下边这棵树一样：

很显然，最小的树就在堆顶，假设存储这个堆的数组叫做h的话，最小数就是h[1]。如果我们要删除最小值并增加一个数字23呢？我们将堆顶的数字移除，然后将23放入堆顶。显然加了新的数值后，已经不符合最小堆的特性了，我们需要将新加入树的节点调整到合理的位置。

当然是向下调整了，最小堆种的大数都在下边的。所以我们只需要不停的与当前节点的子节中较小的节点进行比较并且互换。

我们发现，在堆23进行调整的时候，只进行了3次比较，就恢复了最小堆的特性。现在每次删除一个最小的数的同时增加一个新的数，需要的时间复杂度是O(3)，恰好是
$$
O(log_214) 也就是 O(log_2N)，简写为 O(logN)
$$
如果只想新增一个值呢？只需要把这个值插入到末尾，然后根据情况判断新元素是否需要上移，加入我们现在需要新增一个数字3：

先将3与它的父节点比较，如果比父节点小，则更换位置，继续向上比较即可。说了这么半天，我们忽略了一个很大的问题，怎么创建一个堆呢？可以从空的堆开始，依次的读入元素。还有一种方法，那就是直接把这14个数放入一个完全二叉树中（这里依旧用一个一维数组存储完全二叉树）：

position:  1  2  3  4  5  6  7  8  9  10  11  12  13  14
data    : 99  5 36  7 22 17 92 12  2  19  25  28   1  46

我们从叶节点开始，因为叶节点没有子节点，所以所有的叶节点都符合最小堆特性，所以我们开始处理叶节点之外的点。不符合最小堆特性的都需要向下调整。说白了就2行代码：

for (int i = n / 2; i >= 1; i --) {
    siftDown(i); // 向下调整
}

二叉树还有一个特点：第n/2一定是这棵树的最后一个非叶节点。用这种方法创建堆的时间复杂度为O(N)。堆还有一个作用是排序，排序的时间复杂度也是O(NlogN)，根据我们上边的思维，堆排序就很简单了，比如我们要从小到大排序，我们先建立一个最小堆，然后堆顶的就是最小的，每次删除顶部元素并输出，直到堆空为止。

说了这么多，我们通过代码来看一下建立堆与堆排序的完整过程：

int h[101]; // 用来存放堆的数组
int n; // 用来存储堆中元素的个数，也就是堆的大小

void swap(int x, int y) {
  int temp = h[x];
  h[x] = h[y];
  h[y] = temp;
  return;
}

void siftdown(int i) { // 传入一个需要向下调整的节点编号i
  int position, flag = 0; // 使用flag来标记是否还需要继续向下调整
  
  // 当i节点有左子节点并且需要继续调整的时候
  while ( i * 2 <= n && flag == 0 ) {
    // 首先判断与左子节点的关系，用position记录比较小的结点编号
    if ( h[i] > h[i * 2] ) {
      position = i * 2;
    } else {
      position = i;
    }
    
    if ( i * 2 + 1 <= n ) {
      if ( h[position] > h[i * 2 + 1] ) { // 注意这里是 h[position]，说白了也就是3个值中的最小值
        position = i * 2 + 1;
      }
    }
    
    // 如果最小的编号不是当前编号，说明子节点小于父节点
    if ( position != i ) {
      // 交换 position 与 i 位置的数字
      swap(position, i);
      i = position; // 更新i为交换的子节点的位置，便于继续向下交换
    } else {
      flag = 1; // 意味着父节点是最小，不需要调整了
    }
  }
  return;
}

void create() {
  for (int i = n / 2; i >= 1; i --) {
    siftdown(i);
  }
  return;
}

int deleteMax() {
  int temp = h[1]; // 新建一个变量来存储堆顶的值
  h[1] = h[n]; // 将堆的最后一个元素赋值给堆顶
  n --; // 堆的元素减少1
  siftdown(1); // 将堆顶向下排序
  return temp;
}

int main(int argc, const char * argv[]) {
  
  int num; // 要排序数字的个数
  scanf("%d", &num);
  
  for (int i = 1; i <= num; i ++) {
    scanf("%d", &h[i]); // 将输入的数字顺序初始化到一维数中
  }
  
  n = num; // 表示堆中元素的个数
  
  // 创建堆
  create();
  
  // 删除顶部元素
  for (int i = 1; i <= num; i ++) {
    printf("%d ", deleteMax());
  }
  
  return 0;
}

有人说了，不是还有最大堆么？哈哈，你真聪明，接着改代码：

int h[101]; // 用来存放堆的数组
int n; // 用来存储堆中元素的个数，也就是堆的大小

void swap(int x, int y) {
  int temp = h[x];
  h[x] = h[y];
  h[y] = temp;
  return;
}

void siftdown(int i) { // 传入一个需要向下调整的节点编号i
  int position, flag = 0; // 使用flag来标记是否还需要继续向下调整
  
  // 当i节点有左子节点并且需要继续调整的时候
  while ( i * 2 <= n && flag == 0 ) {
    // 首先判断与左子节点的关系，用position记录比较大的结点编号
    if ( h[i] < h[i * 2] ) {
      position = i * 2;
    } else {
      position = i;
    }
    
    if ( i * 2 + 1 <= n ) {
      if ( h[position] < h[i * 2 + 1] ) { // 注意这里是 h[position]，说白了也就是3个值中的最大值
        position = i * 2 + 1;
      }
    }
    
    // 如果最小的编号不是当前编号，说明子节点大于父节点
    if ( position != i ) {
      // 交换 position 与 i 位置的数字
      swap(position, i);
      i = position; // 更新i为交换的子节点的位置，便于继续向下交换
    } else {
      flag = 1; // 意味着父节点是最大，不需要调整了
    }
  }
  return;
}

void create() {
  for (int i = n / 2; i >= 1; i --) {
    siftdown(i);
  }
  return;
}

int main(int argc, const char * argv[]) {
  
  int num; // 要排序数字的个数
  scanf("%d", &num);
  
  for (int i = 1; i <= num; i ++) {
    scanf("%d", &h[i]); // 将输入的数字顺序初始化到一维数中
  }
  
  n = num; // 表示堆中元素的个数
  
  // 创建堆
  create();
  
  while (n > 1) {
    swap(1, n);
    n --;
    siftdown(1);
  }
  
  // 删除顶部元素
  for (int i = 1; i <= num; i ++) {
    printf("%d ", h[i]);
  }
  
  return 0;
}

并且，堆排序的时间复杂度为
$$
O(NlogN)
$$
另外，如果求一个数列中第K小的数，只需要建立一个大小为K的最大堆，堆顶就是第K小的数字，时间复杂度为
$$
O(NlogK)
$$
树还有很多神奇的用法，比如线段树、树状数组、Trie树、二叉搜索树、红黑树等，这些结构比较复杂，大家可以多多探索。