二叉树 - 面试助力，算法 101：JavaScript 描述

搜索文档…
二叉树
树(Tree)
树是计算机中经常用到的一种数据结构，与列表不同，它是一种非线性的数据结构，以分层的方式来储存数据。像公司的组织架构，就可以理解成一棵树。
一棵树最上面的节点被称为根节点，在下图中，A 就是根节点。如果一个节点下面连接多个节点，该节点被称为父节点，它下面的节点被成为子节点，一个节点可以有0、1或多个子节点，没有子节点的节点被称为叶子节点。A 是 B 的父节点，B 是 A 的子节点。C 和 D 属于同一个父节点 B，他们直接互相称之为兄弟，即互相为兄弟节点。C、D、F、H 和 I 都是叶子节点。
二叉树(Binary Tree)
二叉树是一种特殊的树，它的子节点个数不超过两个。上面的图就是一个二叉树。
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 kkk
 ，且结点总数是2k−12^k - 12k−1
，则它就是满二叉树。[来自百度百科]。
满二叉树(Full Binary Tree)
我们发现，满二叉树的所有叶子节点都在最底层，而且除了叶子节点，其他的节点都有左右两个子节点。
看完满二叉树，来认识一下由其引出来的完全二叉树，可能光看字面意思不是很好理解。若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
对于大多数同学来说 ，满二叉树很好理解，但是到了完全二叉树可能就迷糊了，下面的图给出了几个完全二叉树和非完全二叉树的例子，相信你看了应该就明白是怎么回事了。
二叉树的存储结构
存储一棵二叉树，有两种方法，一种是基于指针或者引用的二叉链式存储，一种是基于数组的顺序存储。
先来看大家都比较熟悉、更加直观的链式存储结构。链式存储结构中，每一个结点包含三个关键属性：指向左子节点的指针，数据，指向右子节点的指针。
结构定义
1
class Node {
2
  public data: any;
3
  public left?: Node;
4
  public right?: Node;
5
  constructor({ data, left, right }) {
6
    this.data = data;
7
    this.left = left;
8
    this.right = right;
9
  }
10
}
Copied!
再来看基于数组的顺序存储，为了帮助大家更好地理解，这里拿了一张完全二叉树的图。使用顺序存储，完全二叉树是非常合适的，可以自上而下，从左到右来顺序存储 n 个结点的完全二叉树。
我们把根节点放到 i=1i = 1i=1
，那么根节点的左子节点存储在下标 2∗i=22 * i = 22∗i=2
 的位置，右子节点存储在 2∗i+1=32 * i + 1 = 32∗i+1=3
 的位置。依此类推，B 节点的左子节点存储在 2∗i=2∗2=42 * i = 2 * 2 = 42∗i=2∗2=4
 的位置，右子节点存储在 2∗i+1=2∗2+1=52 * i + 1 = 2  * 2 + 1 = 52∗i+1=2∗2+1=5
 的位置。
完全二叉树的这种存储结构，有以下特点：
非根节点的父节点对应数组下标为是 i/2i / 2i/2
​
节点的左子节点的序号是 2∗i2 *  i2∗i
,如果2∗i>n2 * i > n2∗i>n
，则左子节点不存在
节点的右子节点的序号是2∗i+12 * i + 12∗i+1
，如果2∗i>n+12*  i > n + 12∗i>n+1
，则右子节点不存在
如果不是完全二叉树，用这种结构来存储会浪费比较多的空间，可以看下面的图。
因此，如果一棵树刚好是完全二叉树，采用顺序存储是最节省内存空间的，不需要额外再提供左右两个指针。
二叉树的遍历
二叉树的常见的遍历方法有 3 种：前序遍历、中序遍历、和后序遍历，依据节点和它的左右子树的遍历顺序不同来划分。
前序遍历：对于二叉树中的任意节点，先访问该节点，再去访问当前节点的左子树，然后是右子树，若当前节点无左子树，则访问当前节点的右子树；
中序遍历：对于二叉树中的任意节点，先访问该节点的左子树，再去访问当前节点，然后是右子树；
后序遍历：对于二叉树中的任意节点，先访问该节点的左子树，再去访问当前节点的右子树，然后是当前节点；
二叉树是一种递归形式的数据结构，因此对于二叉树的 3 种遍历，我们就可以借助其自身的特性，通过递归实现。
1
// 前序遍历
2
function preTraversal(node) {
3
  if (node === null) {
4
    return;
5
  }
6
  console.log(node.data);
7
  preTraversal(node.left);
8
  preTraversal(node.right);
9
}
10
​
11
// 中序遍历
12
function inTraversal(node) {
13
  if (node === null) {
14
    return;
15
  }
16
  inTraversal(node.left);
17
  console.log(node.data);
18
  inTraversal(node.right);
19
}
20
​
21
// 后序遍历
22
function postTraversal(node) {
23
  if (node === null) {
24
    return;
25
  }
26
  postTraversal(node.left);
27
  postTraversal(node.right);
28
  console.log(node.data);
29
}
Copied!
可以看到，使用递归实现二叉树的遍历十分简单。
二叉查找树(Binary Search Tree)
二叉查找树(BST)是一种特殊的二叉树，较小的值保存在左子树中，较大的值保存在右子树中，这一特性使得 查找的效率很高。因此它又有另外一个名字，叫二叉排序树(Binary Sort Tree)。看了图是不是瞬间明白二叉查找树是个啥。
二叉查找树的查找
对于 BST 通常有以下 3 种类型的查找：
找给定值
找最小值
找最大值
根据二叉查找树的属性，查找最小值和最大值比较简单。因为较小的值总是在左子节点上，要找到最小值，只需要遍历左子树，直到找到最后一个节点。
1
function getMin() {
2
  let currentNode = this.tree;
3
  while (currentNode.left !== null) {
4
    currentNode = currentNode.left;
5
  }
6
  return currentNode.data;
7
}
Copied!
查找最大值也是同理，只需遍历右子树，直到找到最后一个节点即可。
1
function getMax() {
2
  let currentNode = this.tree;
3
  while (currentNode.right !== null) {
4
    currentNode = currentNode.right;
5
  }
6
  return currentNode.data;
7
}
Copied!
在 BST 上查找给定值，通过比较该值和当前节点上的值的大小，就能够确定向左还是向右遍历。
1
function find(data) {
2
  let node = this.tree;
3
  while (node !== null) {
4
    if (node.data === data) {
5
      return node;
6
    } else if (data < node.data) {
7
      node = node.left;
8
    } else {
9
      node = node.right;
10
    }
11
  }
12
}
Copied!
二叉查找树的插入
在二叉查找树中插入元素比较复杂，分为以下几种情况：
首先需要检查 BST 是否有根节点，如果没有，插入的节点就是根节点，就完事了
如果待插入的节点不是根节点，那么就需要遍历整棵树，找到合适的位置
如果要插入的数据大于当前节点，并且当前节点的右子树为空，就将新数据插入到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据小于当前节点，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。
1
function insert(data) {
2
  const n = new Node(data);
3
  if (this.tree === null) {
4
    this.tree = n;
5
    return;
6
  }
7
​
8
  let node = this.tree;
9
  while (node !== null) {
10
    if (data > node.data) {
11
      if (node.right === null) {
12
        node.right = n;
13
        return;
14
      }
15
      node = node.right;
16
    } else {
17
      if (data < node.data) {
18
        if (ndoe.left === null) {
19
          node.left = n;
20
          return;
21
        }
22
        node = node.left;
23
      }
24
    }
25
  }
26
​
27
}
Copied!
二叉查找树的删除
在二叉查找树上删除节点的操作最复杂，牵一发而动全身，节点直接存在相互关联。如果删除的是没有子节点的节点，那就直接删掉就完事了。稍微麻烦的是删除节点只有一个子节点的情况，如果删除的节点包含两个子节点，那就是最麻烦的了。
删除没有子节点的节点
如果没有子节点，直接把要删除的节点干掉就行
删除只有一个子节点的节点
只有一个子节点只需要把更新父节点指向要删除节点的指针，指向要删除节点的子节点就可以了。比如图中删除节点的节点是 16，把 15 指向 13 的指针指向 20 即可。
现在来看最复杂的情况：
删除有两个子节点的节点
有两个子节点，我们需要查找右子树上的最小值，把它拿到待删除的节点上，然后再删除这个最小的节点。删除这个最小的节点，又回到了上面讲的两条规则，这个最小节点不可能有两个子节点，如果有左子节点，就不是最小节点了。
1
function remove(data) {
2
  let node = this.tree;
3
  let parentNode;
4
  while (node !== null && node.data != data) {
5
    parentNode = node;
6
    if (data > node.data) {
7
      node = node.right;
8
    } else {
9
      node = node.left;
10
    }
11
  }
12
​
13
  if (node === null) {
14
    return; // 没找着
15
  }
16
​
17
  // 我们采用非递归的方式，先处理要删除的节点有两个子节点的情况
18
  if (node.left !== null && node.right !== null) {
19
    // 查找右子树中最小节点
20
    let minNodeParent = node;
21
    let minNode = minNodeParent.right;
22
    while (minNodeParent.left !== null) {
23
      minNodeParent = minNode;
24
      minNode = minNode.left;
25
    }
26
    node.data = minNode.data;
27
    node = minNode; // 下面就变成删除 minNode 了
28
    parentNode = minNodeParent;
29
  }
30
​
31
  // 删除节点是叶子节点或者只有一个子节点
32
  let childNode = null;
33
  if (node.left !== null) {
34
    childNode = node.left;
35
  } else if (node.right !== null) {
36
    childNode = node.right;
37
  }
38
​
39
  if (parentNode === null) { // 父节点是 null，说明删除的是根节点
40
    this.tree = childNode;
41
  // 第二种情况，把父节点的指向删除节点的指针指向删除节点的子节点
42
  // 删除的是 node，把 parentNode 指向 node 的指针，指向 childNode
43
  } else if (parentNode.left === node) {
44
    parentNode.left = childNode;
45
  } else {
46
    parentNode.right = childNode;
47
  }
48
}
Copied!
本章节分为 4 个部分：
Part 1
最小栈
Shuffle an Array
将有序数组转换为二叉搜索树
Part 2
对称二叉树
二叉树的最大深度
验证二叉搜索树
Part 3
二叉树的层次遍历
二叉树的序列化与反序列化
Part 4
中序遍历二叉树
从前序与中序遍历序列构造二叉树
二叉搜索树中第 K 小的元素
Part 5
填充每个节点的下一个右侧节点指针
岛屿数量
二叉树的锯齿形层次遍历
阅读完本章节，你将有以下收获：
熟悉栈的数据结构，可以解决基本栈相关问题
掌握二叉树的概念
会用不同的方法去遍历二叉树，解决相关问题
以前
排序链表、相交链表和奇偶链表
下一个
最小栈、Shuffle an Array和将有序数组转换为二叉搜索树
最近更新 2yr ago
复制链接
内容
树(Tree)