1. 认识树结构

什么是树？

在真实生活中的树：

通常有一个根，连着根的是树干
树干到上面之后会进行分叉成树枝，树枝还会分叉成更小的树枝
在树枝的最后是叶子

在数据结构中的树正是由真实生活中的树抽象而来，一个模拟树结构的例子：

在上图中，我们可以把

总经理看成是树干
每一个部门看成树枝
部门下更小的部门可以看成树叶

总结：

树是一种分层数据的抽象模型，js 中没有树，但是我们可以用 Object 来构建树

2. 树结构的优点和术语

在说树结构的优点时，我们先来回顾一下之前将的数组/链表/哈希表 这几种数据结构

结构	优点	缺点
数组	根据下标访问值效率很高	1. 查找效率低，需要对数组进行排序生成有序数组，才能提高查找效率。2. 另外，插入和删除数据时，需要有大量的位移操作，效率很低
链表	插入和删除效率很高	1. 查找效率低，需要从头开始一次访问链表中的每个数据项，直到找到。2. 如果插入和删除中间位置的数据，还是需要重头先找到对应的数据
哈希表	插入、查询、删除效率都是非常高的	1. 空间利用率不高，底层使用的是数组，并且某些单元是没有被利用的。2. 哈希表中元素是无序的，不能按照固定的顺序来遍历哈希表中的元素。3. 不能快速找出哈希表的最大值或者最小值这些特殊值

树结构：

我们不能说树结构比其他结构都要好，因为每种数据结构都有自己特定的应用场景
但是树确实也综合了上面的数据结构的优点（当然优点不足以盖过其他数据结构，比如效率一般情况下没有哈希表高）
并且也弥补了上面数据结构的缺点

树的术语：

节点的度（Degree）：节点的子树个数.
树的度（Degree）：树的所有节点中最大的度数. (树的度通常为节点的个数 N-1)
叶节点（Leaf）：度为 0 的节点. (也称为叶子节点)
父节点（Parent）：有子树的节点是其子树的根节点的父节点
子节点（Child）：若 A 节点是 B 节点的父节点，则称 B 节点是 A 节点的子节点；子节点也称孩子节点。
兄弟节点（Sibling）：具有同一父节点的各节点彼此是兄弟节点。
路径和路径长度：从节点 n1到 nk 的路径为一个节点序列 n1 , n2,… , nk, ni是 ni+1 的父节点。路径所包含边的个数为路径的长度。
节点的层次（Level）：规定根节点在 1 层，其它任一节点的层数是其父节点的层数加1。
树的深度（Depth）：树中所有节点中的最大层次是这棵树的深度。

3. 认识二叉树

如果树中的每个节点最多只能有两个子节点，这样的树就称为二叉树

二叉树的定义：

二叉树可以为空，也就是没有节点
若不为空，则它是由根节点和称为其 左子树(Left Tree) 和 右子树（Right Tree） 的两个不相交的二叉树组成

二叉树几个比较重要的特性：

一颗二叉树第 i 层的最大节点数为：2^(i-1), i >= 1;
深度为 k 的二叉树有最大节点总数为： 2^k - 1, k >= 1;
对任何非空二叉树 T，若 n0 表示叶节点(度为 0 的节点)的个数、n2 是度为 2 的非叶节点个数，那么两者满足关系 n0 = n2 + 1。

特殊的二叉树

完美二叉树(Perfect Binary Tree) , 也称为满二叉树(Full Binary Tree）
- 在二叉树中, 除了最下一层的叶结点外, 每层节点都有 2 个子节点, 就构成了满二叉树.

完全二叉树(Complete Binary Tree)
1. 除二叉树最后一层外, 其他各层的节点数都达到最大个数.
2. 且最后一层从左向右的叶节点连续存在, 只缺右侧若干节点.
3. 完美二叉树是特殊的完全二叉树.

下面不是完全二叉树, 因为 D 节点还没有节点, 但是 E 节点就有了左右节点.

4. 二叉树常见存储方式

二叉树的存储常见的方式是数组和链表

4.1 使用数组的方式

完全二叉树：从上至下，从左到右顺序存储

非完全二叉树：要转换成完全二叉树才可以按照上面的方案存储，而且会造成很大的空间浪费

4.2 使用链表的方式：

二叉树最常见的方式还是使用链表存储（我们之后的封装也会基于链表）：每个节点封装成一个 Node，Node 中包含存储的数据，左节点的引用，右节点的引用。

5. 认识二叉搜索树

二叉搜索树（BST，Binary Search Tree），也称为二叉排序树或二叉查找树

二叉搜索树是一棵二叉树，可以为空：

如果不为空，需要满足一下性质：

非空左子树的所有键值小于其根节点的键值
非空右子树的所有键值大于其根节点的键值
左右子树本身也都是二叉搜索树

二叉搜索树的特点：

相对较小的值总是保存在左节点上，相对较大的值总是保存在右节点上
查找效率非常高，这也是二叉搜索树中，搜索的来源

6. 二叉搜索树的封装

一个二叉搜索树的常见操作应该包含以下：

插入操作：
1. insert(value)：向树中插入一个新的数据
查找操作
1. search(value)：在树中查找一个数据，如果节点存在，则返回 true；如果不存在，则返回 false
2. min：返回树中最小的值
3. max：返回树中最大的值
遍历操作：
1. inOrderTraverse：通过中序遍历方式遍历所有节点
2. preOrderTraverse：通过先序遍历方式遍历所有节点
3. postOrderTraverse：通过后序遍历方式遍历所有节点
4. levelOrderTraverse：通过层序遍历方式遍历所有节点
删除操作
1. remove(value)：从树中移除某个数据

6.1 基础架构 v1 版本

ts
class TreeNode<T> {
  value: T;
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

class BSTree<T> {
  root: TreeNode<T> | null = null;
}

代码解析：

封装一个用于保存每一个节点的类 TreeNode
TreeNode 类包含三个属性
1. value: 节点对应的值
2. left: 指向左边的子树
3. right：指向右边的子树
封装 BSTree 类作为一棵树
对于 BSTree 来说，只需要保存根节点即可，因为其他节点都可以通过根节点找到。

结构示意图：

6.2 insert 方法 v2 版

在 BSTree 中添加 insert 方法

insert(value) 的作用为向一棵二叉树插入数据

ts
  insert(value: T) {
    // 1. 根据传入 value 创建 TreeNode 节点
    const newNode = new TreeNode(value);

    // 2. 判断当前是否已经有了根节点
    if (!this.root) {
      // 当前树为空
      this.root = newNode;
    } else {
      // 树中已经有其他值
      this.insertNode(this.root, newNode);
    }
  }

  private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
    if (newNode.value < node.value) {
      // 去左边查找空白位置
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      // 去右边查找空白位置
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

测试：

ts
const bst = new BSTree<number>();

bst.insert(20);
bst.insert(30);
bst.insert(18);
bst.insert(14)
bst.insert(12)
bst.insert(19)
bst.insert(22)

树的结构：


               20
        ┌───────┴───────┐
       18              30
    ┌───┴───┐       ┌───┘
   14      19      22
  ┌─┘
 12

6.3 preOrderTraverse 方法 v3 版

在 BSTree 中添加 preOrderTraverse 方法

preOrderTraverse 方法的作用是先序遍历一个树

树的先序遍历的过程：

优先访问根节点
之后访问左子树
最后访问右子树

ts
  preOrderTraverse() {
    this.preOrderTraverseNode(this.root);
  }

  private preOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      console.log(node.value);
      this.preOrderTraverseNode(node.left);
      this.preOrderTraverseNode(node.right);
    }
  }

测试：

ts
const bst = new BSTree<number>();

bst.insert(20);
bst.insert(30);
bst.insert(18);
bst.insert(14);
bst.insert(12);
bst.insert(19);
bst.insert(22);

bst.preOrderTraverse();

树的结构：


               20
        ┌───────┴───────┐
       18              30
    ┌───┴───┐       ┌───┘
   14      19      22
  ┌─┘
 12

打印结果：

6.4. inOrderTraverse 方法 v4 版

在 BSTree 中添加 inOrderTraverse 方法

inOrderTraverse 方法的作用是中序遍历一个树

树的中序遍历的过程：

优先访问左子树
之后访问根节点
最后访问右子树

ts
  inOrderTraverse() {
    this.inOrderTraverseNode(this.root);
  }

  private inOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      this.inOrderTraverseNode(node.left);
      console.log(node.value);
      this.inOrderTraverseNode(node.right);
    }
  }

测试：

ts
const bst = new BSTree<number>();

bst.insert(20);
bst.insert(30);
bst.insert(18);
bst.insert(14);
bst.insert(12);
bst.insert(19);
bst.insert(22);

bst.inOrderTraverse();

树的结构：


               20
        ┌───────┴───────┐
       18              30
    ┌───┴───┐       ┌───┘
   14      19      22
  ┌─┘
 12

打印结果：

6.5. postOrderTraverse 方法 v5 版

在 BSTree 中添加 postOrderTraverse 方法

postOrderTraverse 方法的作用是后序遍历一个树

树的后序遍历的过程：

优先访问左子树
之后访问右子树
最后访问根节点

ts
  postOrderTraverse() {
    this.postOrderTraverseNode(this.root);
  }

  private postOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      this.postOrderTraverseNode(node.left);
      this.postOrderTraverseNode(node.right);
      console.log(node.value);
    }
  }

测试：

ts
const bst = new BSTree<number>();

bst.insert(20);
bst.insert(30);
bst.insert(18);
bst.insert(14);
bst.insert(12);
bst.insert(19);
bst.insert(22);

bst.postOrderTraverse();

树的结构：


               20
        ┌───────┴───────┐
       18              30
    ┌───┴───┐       ┌───┘
   14      19      22
  ┌─┘
 12

打印结果：

6.6. levelOrderTraverse 方法 v6 版

在 BSTree 中添加 levelOrderTraverse 方法

levelOrderTraverse 方法的作用是层序遍历一个树

层序遍历的过程：

从上向向下逐层遍历
层序遍历通常会借助队列来完成

ts
  levelOrderTraverse() {
    // 1. 如果没有根节点，那么不需要遍历
    if (!this.root) return;

    // 2. 创建队列结构
    const queue: TreeNode<T>[] = [];

    // 第一个节点是根节点
    queue.push(this.root);

    // 3. 遍历队列中所有的节点（依次出队）
    while (queue.length) {
      // 3.1 访问节点的过程
      const current = queue.shift()!;
      console.log(current.value);

      // 3.2 将左子节点放入到队列
      if (current.left) {
        queue.push(current.left);
      }

      // 3.3 将右子节点放入到队列
      if (current.right) {
        queue.push(current.right);
      }
    }
  }

测试：

ts
const bst = new BSTree<number>();

bst.insert(20);
bst.insert(30);
bst.insert(18);
bst.insert(14);
bst.insert(12);
bst.insert(19);
bst.insert(22);

bst.levelOrderTraverse();

树的结构：


               20
        ┌───────┴───────┐
       18              30
    ┌───┴───┐       ┌───┘
   14      19      22
  ┌─┘
 12

打印结果：

6.7 getMaxValue 方法 v7 版

在 BSTree 中添加 getMaxValue 方法

getMaxValue 方法的作用是获取树中的最大值

ts
  getMaxValue(): T | null {
    let current = this.root;
    while (current && current.right) {
      current = current.right;
    }

    return current?.value ?? null;
  }

6.8 getMinValue 方法 v8 版

在 BSTree 中添加 getMinValue 方法

getMinValue 方法的作用是获取树中的最小值

ts
  getMinValue(): T | null {
    let current = this.root;
    while (current && current.left) {
      current = current.left;
    }

    return current?.value ?? null;
  }

6.9 search 方法 v9 版

在 BSTree 中添加 search 方法

search 方法的作用：在树中查找一个数据，如果节点存在，则返回 true；如果不存在，则返回 false

ts
  search(value: T): boolean {
    let current = this.root;
    while (current) {
      // 找到了节点
      if (current.value === value) return true;

      if (current.value < value) {
        current = current.right;
      } else {
        current = current.left;
      }
    }

    return false;
  }

6.10 remove 方法 v10 版

在 BSTree 中添加 remove 方法

remove 方法的作用：删除某个数据

remove 的逻辑比较复杂，我们大致可以分为以下四种情况:

要删除的的节点是叶子结点（没有子节点）
要删除的的节点只有一个左子节点
要删除的的节点只有一个右子节点
要删除的的节点有两个节点

ts
   remove(value: T): boolean {
    // 1. 获取要删除的节点 current 和 其父节点 parent
    let current = this.root;
    let parent: TreeNode<T> | null = null;
    while (current) {
      // 找到了节点
      if (current.value === value) break;

      parent = current;

      if (current.value < value) {
        current = current.right;
      } else {
        current = current.left;
      }
    }
    // 如果没有找到要删除的节点返回 false
    if (!current) return false;

    // 2.  如果要删除的的节点是叶子结点
    if (current.left === null && current.right === null) {
      if (current === this.root) {
        // current 是根节点
        this.root = null;
      } else if (parent?.left === current) {
        // current 在父节点的左边
        parent!.left = null;
      } else {
        // current 在父节点的右边
        parent!.right = null;
      }
    }

    // 3. 如果要删除的的节点只有一个左子节点
    else if (current.right === null) {
      if (current === this.root) {
        this.root = current.left;
      } else if (parent?.left === current) {
        // current 在父节点的左边
        parent!.left = current.left;
      } else {
        parent!.right = current.left;
      }
    }

    // 4. 如果要删除的的节点只有一个右子节点
    else if (current.left === null) {
      if (current === this.root) {
        this.root = current.right;
      } else if (parent?.left === current) {
        // current 在父节点的左边
        parent!.left = current.right;
      } else {
        parent!.right = current.right;
      }
    }

    // 5. 如果要删除的的节点有两个子节点
    else {
      const successor = this.getSuccessor(current);
      if (current === this.root) {
        this.root = successor;
      } else if (parent?.left === current) {
        parent!.left = successor;
      } else {
        parent!.right = successor;
      }
    }
    return true;
  }

  // 获取后继节点
  private getSuccessor(delNode: TreeNode<T>): TreeNode<T> {
    // 获取右子树
    let current = delNode.right;
    let successor: TreeNode<T> | null = null;
    while (current) {
      successor = current;
      current = current.left;
    }

    // 拿到了后继节点
    if (successor !== delNode.right) {
      delNode!.right!.left = successor?.right ?? null;
      successor!.right = delNode.right;
    }

    // 一定要进行的操作：将删除后继节点的 left 赋值给后继节点的 left
    successor!.left = delNode.left;

    return successor!;
  }

7. 提升：遍历非递归版

在上面的的遍历实现中，我们都是使用递归的方式实现。

递归：直接或间接调用自身算法的过程

它的优点就是:

代码简洁
符合思维习惯，容易理解

但是它也有很明显的缺点：

效率较低
如果递归层次太深，耗内存且容易栈溢出

在这里我们就用非递归的方式再实现一遍

1. 先序遍历

ts
  preOrderTraverse() {
    let stack: TreeNode<T>[] = [];
    let current: TreeNode<T> | null = this.root;

    while (current !== null || stack.length !== 0) {
      while (current !== null) {
        console.log(current.value);
        stack.push(current);
        current = current.left;
      }

      current = stack.pop()!;
      current = current?.right;
    }
  }

2. 中序遍历

ts
  inOrderTraverse() {
    let stack: TreeNode<T>[] = [];
    let current: TreeNode<T> | null = this.root;

    while (current !== null || stack.length !== 0) {
      while (current !== null) {
        stack.push(current);
        current = current.left;
      }

      current = stack.pop()!;
      console.log(current.value);
      current = current?.right;
    }
  }

3. 后序遍历

ts
postOrderTraverse() {
  let stack: TreeNode<T>[] = [];
  let current: TreeNode<T> | null = this.root;
  let lastVisitedNode: TreeNode<T> | null = null;

  while (current !== null || stack.length !== 0) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    current = stack[stack.length - 1];
    if (current.right === null || current.right === lastVisitedNode) {
      console.log(current.value);
      lastVisitedNode = current;
      stack.pop();
      current = null;
    } else {
      current = current.right;
    }
  }
}

8. 总结

二叉搜索树作为数据存储的结构有重要优势：可以快速地找到给定关键字的数据项，并且可以快速插入和删除数据项

但是二叉搜索树有一个很麻烦的问题：如果插入的数据是有序的数据，比如下面的情况

有一棵棵始化为 9 8 12的二叉树，插入下面的数据7 6 5 4 3 ，最终会形成下面这样的结构

这种左右子树不平衡的树我们称为非平衡树
比较好的二叉搜索树结构应该是左右分布均匀的
对于一棵平衡二叉树来说，插入和查找等操作的效率都是 O(logN)
对于一棵非平衡二叉树，相当于编写了一个链表，查找效率变成了 O(N)

所以，为了能以较快的时间O(logN)来操作一棵树，我们需要保证树总是平衡的（至少大部分是平衡的）

常见的平衡树：（后续介绍）

AVL树
红黑树

目录

1. 认识树结构

2. 树结构的优点和术语

3. 认识二叉树

4. 二叉树常见存储方式

4.1 使用数组的方式

4.2 使用链表的方式：

5. 认识二叉搜索树

6. 二叉搜索树的封装

6.1 基础架构 v1 版本

6.2 insert 方法 v2 版

6.3 preOrderTraverse 方法 v3 版

6.4. inOrderTraverse 方法 v4 版

6.5. postOrderTraverse 方法 v5 版

6.6. levelOrderTraverse 方法 v6 版

6.7 getMaxValue 方法 v7 版

6.8 getMinValue 方法 v8 版

6.9 search 方法 v9 版

6.10 remove 方法 v10 版

7. 提升：遍历非递归版

8. 总结