2020-11-16 树

树的基本概念

树是n个节点组成的有限集，n为0，则称为空树。非空树有以下特点：

• 有且仅有一个根节点（root）；
• n > 1，其余节点可分为m（m>0）个互不相交的有限集，每个集合本身又是一个棵树。

其他概念

• 叶子节点（leaf）：树的末尾，没有子节点；
• 父节点
• 孩子节点
• 兄弟节点
• 树的高度/深度：树的最大层级

二叉树

这棵树的节点最多只有2个子节点，也可能为0或1。

• 左孩子
• 右孩子
  两个孩子节点的顺序不可颠倒，是有序的。

两种特殊形态

• 满二叉树：除叶子节点外，其他节点都包含左右孩子；

  
  image.png
• 完全二叉树：从左到右，每一层级的节点编号，顺序相加，到最后一个节点的编号与满二叉树的编号相同。也就是虽然不满，但是不残
  image.png

表现形式

• 链式结构：树的节点之间的关系是指向关系，所以跟链表中的next和prev指针非常相似，用链表来实现二叉树的结构非常直观。

  
  image.png
• 数组：将二叉树的每个节点依次在数组中存放，如果某一个节点的孩子节点为空，那在数组中也需要为其留下相应的位置。对于较为稀疏的二叉树来说，这样非常浪费内存空间。
  image.png

可以得出：

• 已知父节点的索引为parent，则其左孩子索引为：2 * parent + 1；
• 已知左孩子节点索引为：child，则父节点的索引为：(child - 1) / 2。

二叉树的应用：

• 查找：
  查找二叉树：

  1. 若左子树不为空，则其值都小于根节点；
  2. 若右子树不为空，则其值都大于根节点；
  3. 左右子树也都是查找二叉树。
  image.png

  对于一个分布相对均匀的查找二叉树来说，若节点总数n，寻找一个子节点的时间复杂度为O(logn)，和树的深度一样。

  这个依靠比较大小来查找的过程与二分查找非常类似。

• 维持相对顺序：
  这个特点其实就是二叉查找树的规则，左子树值小于父节点，右子树值大于父节点。
  这样其实很容易出现一个问题，导致二叉树单边的深度越来越大，查找节点的时间复杂度也变为了O(n)：

  
  image.png

---

这时就需要二叉树的自平衡了，具体红黑树、AVL树、树堆可以实现。

二叉树的遍历

• 深度优先遍历：
  • 先序遍历：根、左、右
  • 中序遍历：左、根、右
  • 后序遍历：左、右、根
    代码实现：
  • 递归：

  class TreeNode {
    data = null;
    leftChild: TreeNode = null;
    rightChild: TreeNode = null;
  
    constructor(data) {
      this.data = data;
    }
  }
  
  function createTree(list: number[]) {
    let node: TreeNode = null;
    if (!list.length) {
      return null;
    }
    const data = list[0];
    list.splice(0, 1);
    if (data) {
      node = new TreeNode(data);
      node.leftChild = createTree(list);
      node.rightChild = createTree(list);
    }
    return node;  
  }
  
  function consoleData(node: TreeNode) {
    if (node) {
      console.log(node.data);
      consoleData(node.leftChild);
      consoleData(node.rightChild);
    }
  }
  
  function main() {
    const tree = createTree([3, 2, 9, null, null, 10, null, null, 8, null, 4]);
  /*
  * 深度优先遍历生成的二叉树：
  *                   3
  *                /     \
  *            2            8
  *          /   \         /  \
  *       9        10    null   4
  *     /   \     /  \
  *   null null null null
  * */
    consoleData(tree);
  }
  main();
  

  • 栈（用数组实现，先序遍历为例，栈内元素入队时相当于遍历一次，从左子节点开始遍历，当一个元素左右子节点均为null，则需要回溯到该节点的父节点，再遍历右子节点，以此类推，直至栈空）：

    import {createTree, TreeNode} from "./recursive";
  
  function consoleByStack(root: TreeNode) {
    const stack: TreeNode[] = [];
    let node: TreeNode = root;
    while (node || stack.length) {
      // 遍历左子树
      while (node) {
        console.log("遍历：", node.data);
        stack.push(node);
        node = node.leftChild;
      }
      // 开始遍历右子树
      if (stack.length) {
        node = stack.pop();
        node = node.rightChild;
      }
    }
  }
  
  function main() {
    consoleByStack(createTree([3, 2, 9, null, null, 10, null, null, 8, null, 4]))
  }
  main();
  

  也按照树的结构深度遍历出来了

  
  image.png

• 广度优先遍历
  横向优先，其中比较重要的概念是，在一层遍历中，当一个元素被遍历，其左右子节点优先准备在下一轮遍历（进入遍历队列）
  • 队列实现：

  function consoleByQueue(root: TreeNode) {
    const queue: TreeNode[] = [];
    queue.push(root);
    while (queue.length) {
      const node = queue.shift();
      console.log("遍历：", node.data);
      if (node.leftChild) {
        queue.push(node.leftChild);
      }
      if (node.rightChild) {
        queue.push(node.rightChild);
      }
    }
  }
  

二叉堆

什么是二叉堆

• 完全二叉树
• 最大堆：每个节点的左右子节点都小于该节点的值
• 最小堆：每个节点的左右子节点都大于该节点的值
• 堆顶：二叉堆的根节点

二叉堆的自我调整

• 插入节点（O(logn)）
  二叉堆插入节点时，插入位置是完全二叉树的最后一个节点，此时需要根据是最大堆还是最小堆，移动节点的位置（对比、上浮交换节点）使其成为一个二叉堆；
• 删除节点（O(logn)）
  二叉堆删除节点与插入相反，是从堆顶开始删除，然后将完全二叉树的最后一个位置节点移动到堆顶，再层层对比，进行位置的调整，直至形成一个二叉堆。
• 构建二叉堆（O(n)）
  一个无序二叉树，依次调节其中非叶子节点的位置，上下移动，直至形成一个二叉堆。

二叉堆的存储是顺序存储，也就是存储在数组中，通过完全二叉树的索引计算公式，知道一个父节点的索引，就能得出其左右子节点的索引，反之亦然。

优先队列

• 最大优先队列：不遵循FIFO原则，队列中每次出队都是最大的元素；
  可以利用最大堆来实现，入队操作可以看成插入节点（最后位置插入），出队操作就是删除堆顶，再自我调节。
• 最小优先队列：不遵循FIFO原则，队列中每次出队都是最小的元素；

以实现最大堆为例，代码如下：

 class PriorityQueue {
  array: number[] = [];

  public enQueue(item: number) {
    this.array.push(item);
    this.upAdjust();
  }
  public deQueue() {
    this.array[0] = this.array[this.array.length - 1];
    this.array.pop();
    this.downAdjust();
  }

  public downAdjust() {
    const size = this.array.length;
    if (size == 0) {
      return;
    }
    let parentIndex = 0;
    const target = this.array[parentIndex];
    // 最大堆应该寻找左右子节点中的较大的一方进行位置交换
    // 先左
    let childIndex = parentIndex * 2 + 1;
    while (childIndex < size) {
      // 右子节点存在，且大于左子节点
      if (childIndex + 1 < size && this.array[childIndex+1] > this.array[childIndex]) {
        childIndex += 1;
      }
      if (target >= this.array[childIndex]) {
        break;
      }
      this.array[parentIndex] = this.array[childIndex];
      parentIndex = childIndex;
      // 还是默认先左子节点
      childIndex = parentIndex * 2 + 1;
    }
    this.array[parentIndex] = target;
  }
  public upAdjust() {
    const size = this.array.length;
    let childIndex = size - 1;
    // 只有一个元素
    if (childIndex == 0) {
      return;
    }
    // 目标元素
    const target = this.array[childIndex];
    let parentIndex = Math.floor((childIndex - 1) / 2);
    while (childIndex > 0 && target > this.array[parentIndex]) {
      this.array[childIndex] = this.array[parentIndex];
      childIndex = parentIndex;
      parentIndex = Math.floor((childIndex - 1) / 2);
    }
    this.array[childIndex] = target;
  }

}

function main() {
  const queue: PriorityQueue = new PriorityQueue();
  queue.enQueue(3);
  queue.enQueue(5);
  queue.enQueue(10); 
  queue.enQueue(2);
  queue.enQueue(2);
  queue.enQueue(9);
  queue.enQueue(7);
  console.log(queue.array);
  queue.deQueue();
  console.log(queue.array);
  queue.deQueue();
  console.log(queue.array);
}
main();

输出结果：

image.png