1. 二叉树

1.1 概念

  • 不包含任何结点的称为空树, 只包含一个结点称为单点树
  • 没有子结点的称为树叶, 非树叶结点称为分支结点, 对于二叉树有左分支, 右分支
  • 一个结点的子结点个数称为该结点的度数, 很明显度只能取 [0, 1, 2] 三个值
  • 路径: 从祖先结点到子孙结点包含的一系列边, 称为路径.
  • 二叉树是分层的, 根结点所在为第 0 层. 树中结点的最大层数称为树的高度
  • 满二叉树: 二叉树中的所有分支结点的度数都是 2
  • 扩充二叉树: 对于二叉树 T, 加入足够多的新的结点, 使 T 原有的结点的度都变成 2, 得到的这棵新树称为扩充二叉树. 扩充二叉树新加入的结点称为外部结点, 原来的结点称为内部结点
  • 完全二叉树: 对于高度为 h 的二叉树, 其 h - 1 层及到根都是满结点的, 并且在 h 层的结点是从左向右填, 数量不定. 这说明满二叉树一定是棵完全二叉树

1.2 性质

  • 在非空叉树第 i 层最多有 $2^i (i >= 0)$ 个结点
  • 高度为 h 的二叉树, 最多有 $2^{h+1} - 1 (h >= 0)$ 个结点. 这其实是上面的一个推论, 如果每层都 是满的, 那么则有 $S = 1 + 2 + 4 + … + 2^h$, 则有 $2S - S = 2^{h+1} - 1$
  • 对于任何非空二叉树 T, 如果其叶结点个数为 $n_0$, 度数为 2 的结点个数为 $n^2$, 那么有 $n_0 = n^2 + 1$
  • 满二叉树中, 分支结点比叶子结点多一个, 这是上面的推论
  • 扩充二叉树根到各个外部结点的路径和 E 与根到各个内部结点的路径和 I, 有 $E = I + 2 * n$, 其中 n 为内部结点个数
  • n 个结点的完全二叉树, 其高度 $h <= log_2 n$, 即 $h = floor(log_2N)$. 这是很容易证明, 对于一棵满二叉树, 其结点数有 $n = 2^{h + 1} - 1$, 那么对于完全二叉树则有 $2^h <= n <= 2^{h + 1} - 1$, h, n 都是整数, 则 h 是不大于 $log_2N$ 的整数
  • 在完全二叉树, 对于任意结点 $i (0 <= i <= n - 1, n 为结点总数)$, 其左子结点(如果有)为 $2 * i + 1$, 右子结点(如果有)为 $2 * i + 1$. 我们还可以算出该结点的父结点(如果有)位置为 $floor((i - 1) / 2)$. 这是由上面推出来的, 父结点位置应该在区间 $((j - 2) / 2, (j - 1) / 2)$ 并且是一个整数, 所以对这两个边界作向上或向下取整即可

1.3 遍历方式

  • 深度优先遍历, 这种遍历方法, 在使用非递归实现时, 由于先有上层才有下层, 但我们是要先访问下层, 所以是一个**后进先出(LIFO)**的栈结构.

    记忆技巧: 三种方法区别方式都是对根来说的, 对于每一棵树, 都最多只有三个结点, 就是 根, 左结点, 右结点, 对于每一棵子树, 我们都要执行一样的遍历顺序

    • 先根序遍历 Pre-order: 根 -> 左 -> 右. 在非递归的方法中, 使用一个辅助栈来保存上层的结点信息. 因为要先访问左结点要再访问右结点. 从栈内弹出结点的顺序就是我们要的遍历顺序, 当栈中为空的时候就完成遍历.

      1. 循环体外先把根结点入栈

      2. 循环判断栈是否为空, 不为空的话, 弹出栈中结点, 对该节点 node 调用访问函数

      3. 如果 node 有右结点, 则右结点入栈

      4. 如果 node 有左结点, 则左结点入栈. 回到第 2 步

      5. 一直判断栈中没有节点为止

       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
      
      void preorder(BinaryTree *tree)
      {
          if (tree == NULL || tree->root == NULL) {
              return;
          }
              
          Stack *stack = (Stack *)malloc(sizeof(Stack));
          if (stack == NULL) {
              return;
          }
          stack->push(tree->root);
          Node *node = NULL;
          while (!stack->isEmpty()) {
              node = stack->pop();
              process(node);
              if (node->right != NULL) {
                  stack->push(node->right);   
              }
                  
              if (node->left != NULL) {
                  stack->push(node->left);
              }
          }
          free(stack);
      }
      
    • 中根序遍历 In-order: 左 -> 根 -> 右. 依旧还使用一个栈作为辅助, 由于要保存父结点的信息, 所以父结点必须要入栈, 然后再向下访问左结点, 但当我们从栈中 pop 出父结点时, 处理完后, 不能再访问其左结点, 避免造成死循环

      1. 设置一个变量 node, node 首先指向树的根结点, 设置一个栈
      2. 循环判断当 栈不为空, 或者 node 指向不为 NULL
      3. 当 node 不为空, 我们把这个当作一个父结点入栈, 然后把 node 指向 node 的左结点, 回到循环条件.此时, 栈中已经有至少一个结点, 条件成立
      4. 如果 node 此时指向 NULL, 说明 node 往下再没有左子结点
      5. 处理 node , 然后把 node 指向 node 的右子结点, 回到 循环条件
      6. 这样通过两个条件先向下查找, 到底后再弹出, 弹出再查找其右结点
       1
       2
       3
       4
       5
       6
       7
       8
       9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      
      void inorder(BinaryTree *tree)
      {
          Stack *stack = (Stack *)malloc(sizeof(Stack));
          if (stack == NULL) {
              return;
          }
          Node *node = tree->root;
          while (!stack.isEmpty() || node != NULL) {
              if (node != NULL) {
                  stack->push(node);
                  node = node->left;
              } else {
                  process(node);
                  node = node->right;
              }
          }
          free(stack);
      }
      
    • 后根序遍历 Post-order: 左 -> 右 -> 根.

      • 简单方法, 使用两个栈: 我们使用容易的对 前序遍历 稍加修改便可以得到一个 根 -> 右 -> 左 访问顺序栈 s1, 然后依次把这个遍历压入另一个栈 s2 中, 当 s1 遍历完成时, 对 s2 进行遍历我们便得到一个 左 -> 右 -> 根 的遍历顺序
       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
      
      void postorder(BinaryTree *tree)
      {
          if (tree == NULL || tree->root == NULL) {
              return;
          }
              
          Stack *s1 = (Stack *)malloc(sizeof(Stack));
          Stack *s2 = (Stack *)malloc(sizeof(Stack));
          if (s1 == NULL || s2 == NULL) {
              if (s2 == NULL) {
                  free(s1);
              }
              return;
          }
              
              
          Node *node;
          s1->push(tree->root);
          while (!s1->isEmpty()) {
              node = s1->pop();
              s2->push(node);
              if (s1->left != NULL) {
                  s2->push(node->left);
              }
              if (s1->right != NULL) {
                  s2->push(node->right)
              }
          }
              
          while (!s2->isEmpty()) {
              process(s2->pop())
          }
      }
      

    当使用递归方式遍历时, 每次我们都是递归左子树再递归又子树, 所以这两次递归中, 每层函数在栈中都保存有递归节点, 不同的遍历方式只是体现在, 处理访问节点的时机不两路;

     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
    
    void preorder(Node *node)
    {
    	if (node == NULL) {
    		return;
    	}
    	process(node);
    	preorder(node->left);
    	preorder(node->right);
    }
    
    void inorder(Node *node)
    {
        if (node == NULL) {
            return;
    	}
    	inorder(node->left);
    	process(node);
    	inorder(node->right);
    }
    
    void postorder(Node *node)
    {
        if (node == NULL) {
            return;
    	}
    	postorder(node->left);
    	process(node);
    	postorder(node->right);
    }
    
  • 宽度优先遍历: 把每一层的所有结点都访问完, 再访问下层. 一般我们都从同层的左边结点开始

2. 优先队列

优先队列是一种带权值的队列, 队列总保持一种可以按优先级的访问顺序. 根据需要从高到低或从低到高

2.1 基于线性表的实现

如果基于线表来实现优先队列, 从外部使用角度看, 我们只关心每一次出队的元素都是队列中优先级最高的, 向其中插入值时, 按优先级排到队列中最合适的位置. 这样插入的话可能出产生 O(n), 取出都是 O(1). 我们也可以不保持队列的存储顺序, 在取出时再查找最优先元素. 这样插入是 O(1), 取出是 O(n)

2.2 基于树形结构的实现

  • : 堆是一种完全二叉树, 其有一个主要性质, 从任意一条根 -> 叶子结点的这条路径, 总有 父结点 > 子结点 的叫最大堆, 反之叫最小堆. 同一兄弟结点没有特定的大小关系
  • 向上筛选: 向堆中末尾插入一个结点, 这个结点跟其父结点比较大小, 根据需要来交换位置, 依次循环这两个操作, 直到确定位置, 或者到根结点
  • 向下筛选: 当我们拿走根结点后, 其两个子树依然还是两个堆, 这样我们从原堆中取出最后一个结点, 因为我们取出最后一个结点, 堆序是不变. 把这个结点当作新的根结点, 形成新的二叉树. 对比两个左右子结点, 找到最小或大(根据堆序)的, 然后跟根结点比较, 如果根结点大小不合适, 那么交换这两结点, 然后在新的子树层里, 重复上两步比较操作. 这看起来就像结点在往树底下移动.

完全二叉树可以用一个线性的结构来表示, 我们只关心其父子结点的位置, 对于一个结点 i, 其左结点就是 $2 * i + 1$, 右结点就是 $2 * i + 2$, 其父结点就是 $floor((i - 1) / 2)$. 所以用一个数组很容易的表示堆, 并且每个结点的访问都是 O(1).