❌

普通视图

发现新文章，点击刷新页面。
昨天以前首页

JavaScript 实现二叉树

✇anran758's blog
作者 anran758
2021年1月5日 14:35

二叉树数据结构的学习与笔记。

目录

二叉树的储存结构

二叉树有两种储存方式，一种是顺序储存结构，一种是链式储存结构。

顺序储存结构就是二叉树从上至下，每层从左到右给树中节点进行编号:

1
[0,1,2,3,4,5,6]

0 是根节点，1 是根的左节点，2 是根的右节点，3 是根的左节点的左节点，4 是根的左节点的右节点…… 依照这个顺序排列下去。设 i 为顺序表中节点的索引, Qi 代表顺序表上储存的节点, n 为顺序表的长度，则可知:

  1. i = 0，Qi 节点是根节点
  2. 若 2i+1 < n, 则索引 2i+1 上储存的是 Qi 的左节点。反之，则没有节点。
  3. 若 2i+2 < n, 则索引 2i+2 上储存的是 Qi 的右节点。反之，则没有节点。
  4. **Qi 的双亲节点的索引为 (i-1)/2**。比如 i=4, (i-1)/2 向下取整等于 1, 索引为 4 的双亲节点为 1。

链式储存的结构大致如下:

1
2
3
4
5
6
7
8
9
10
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

顺序结构转链式结构

利用二叉树的性质，可以将顺序储存方式转换为对应的链式结构:

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
34
35
36
37
class TreeNode {
  constructor(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

function toLinkedListBinaryTree(list) {
  // 临时用于储存被转换为链表的节点
  const nodelist = [];

  for (let i = 0; i < list.length; i++) {
    const node = new TreeNode(list[i]);
    nodelist.push(node);

    // 根节点没有双亲节点
    if (i > 0) {
      // 由结论 4 可得双亲节点的索引
      const parentIdx = Math.floor((i - 1) / 2);
      const parent = nodelist[parentIdx];

      // 当前层从左向右赋值，若左节点被赋值，则剩下右节点没有被赋值
      if (parent.left) {
        parent.right = node;
      } else {
        parent.left = node;
      }
    }

  }

  return nodelist.shift()
}

// 在 console 进行测试
cnsole.log(toLinkedListBinaryTree([0,1,2,3,4,5,6,7,8,9]));

二叉树的遍历

遍历二叉树是指沿着某条搜索路径周游二叉树，依次对树中的每个节点访问且仅访问一次。

二叉树的遍历方式可以分为递归和非递归方式。遍历算法也可以分为**深度优先搜索 (Depth-First-Search，DFS)和广度优先搜索 (Breadth-First Search)**。

根据二叉树的递归定义，遍历一颗非空二叉树的问题可分为三个子问题: 访问根节点 (D)，遍历左子树 (L)，遍历右子树 (R)。遍历的顺序可分为: DLR (前序)、LDR (中序)、LRD (后序) 和 DRL (前序)、RDL (中序)、RLD (后序)。前三种是先左后右，后三种是先右后左。一般没有提别指明的话，我们谈论二叉树的遍历，都是在讲前三种。

二叉树的前序遍历、中序遍历、后序遍历都可以通过递归方式和非递归方式实现。

前序序遍历

递归形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
function preorderTraversal(root: TreeNode | null): number[] {
    return postorder(root, [])
};

function postorder(root?: TreeNode, result = []): number[] {
    if (!root) return result;

    result.push(root.val);
    postorder(root.left, result);
    postorder(root.right, result);

    return result;
}

中序遍历

递归形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
function inorderTraversal(root: TreeNode | null): number[] {
    return inorder(root, [])
};

function inorder(root?: TreeNode, result = []): number[] {
    if (!root) return result;

    inorder(root.left, result);
    result.push(root.val);
    inorder(root.right, result);

    return result;
}

后序遍历

递归形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
function postorderTraversal(root: TreeNode | null): number[] {
    return postorder(root, [])
};

function postorder(root?: TreeNode, result = []): number[] {
    if (!root) return result;

    postorder(root.left, result);
    postorder(root.right, result);
    result.push(root.val);

    return result;
}

层序遍历

层序遍历就是把二叉树分层，然后每一层从左到右遍历：

层序遍历二叉树很自然就能想到使用 BFS(广度优先搜索) 来遍历每层。

该算法采用一个队列来缓存二叉树的节点，若树不为空，先将二叉树根节点输出，先将根节点入队，再到循环体内出队。若根节点还有左孩子，则将左孩子也添加到队列中。若有右孩子，也将右孩子也添加到队列中。如此下去，直到队列为空:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 按层输出二叉树的值
function levelOrder(root: TreeNode | null) {
  if (!root) return;

  // 队列，先进先出
  const queue = [root];

  while (queue.length) {
    // 取队首的元素
    const node = queue.shift();
    console.log('node --> ', node.val)

    // 若有左右节点，则添加至队列
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
};

若想将每一层的值都存入数组中，则可以采用二维数组进行储存:

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
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];

  // 最终会返回的结果
  const result = [];
  
  // 队列，先进先出
  const queue = [root];

  while (queue.length) {
    // 当前层级
    const level = [];

    // 当前队列的长度
    const n = queue.length;

    for (let i = 0; i < n; i += 1) {
      const node = queue.shift();
      level.push(node.val);

      // 若有左右节点，则添加至队列
      // 由于已经储存上一轮的节点数，因此这里不会影响 n 的值
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
};

合并二叉树

不考虑副作用的话，可以直接将 root1 作为结果，修改 root1 的值即可。

1
2
3
4
5
6
7
8
9
function mergeTrees(root1?: TreeNode, root2?: TreeNode): TreeNode | null {
    if (!root1 || !root2) return root1 || root2;

    root1.val += root2.val;
    root1.left = mergeTrees(root1.left, root2.left);
    root1.right = mergeTrees(root1.right, root2.right);

    return root1;
};

二叉排序树 (BST)

二叉排序树(Binary Sort Tree)又称二叉查找树，它是一种特殊的二叉树，它或为空树，或具有以下性质的二叉树:

  1. 它的右子树非空，则右子树上所有节点的值都大于根节点的值。
  2. 它的左子树非空，则左子树上所有节点的值都小于根节点的值。
  3. 左右子树各是一颗二叉排序树。

以下为创建二叉排序树的代码:

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
34
function sortedArrayToBST(nums: number[]): TreeNode | null {
    let tree = null, node;

    while(nums.length) {
        node = new TreeNode(nums.shift())
        tree = insertBST(tree, node)
    }

    return tree;
};

function insertBST(tree: TreeNode, node: TreeNode) {
    let parent, p = tree;

    while(p) {
        // parent 指向 p 的双亲
        parent = p;
    
        // 要插入的节点的值小于 p 的值，赋值为左节点
        // 要插入的节点的值大于 p 的值，赋值为右节点
        p  = node.val < p.val ? p.left : p.right;
    }

    if (tree == null) return node;
    
    // console.log('p',parent.val, node.val)
    if(node.val < parent.val) {
        parent.left = node;
    } else {
        parent.right = node;
    }

    return tree;
}

高度平衡二叉搜索树

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1」的二叉树。

Q: 给定已按升序排序的整数数组，将其构建为二叉树。

A: 因为数组已经排过序了，因此可以直接采用二分法进行构建。先去中间的元素，再向两侧递归构建:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function sortedArrayToBST(nums: number[]): TreeNode | null {
    return dfs(nums, 0, nums.length - 1)
};

function dfs(nums: number[], min: number, max: number): TreeNode | null {
    if (min > max) return null;

   // 取中间的索引，先减后加的方式可以避免索引值溢出
    const mid = min + Math.floor((max - min) / 2);

    // 由于是采用二分法，因此左右子树的高度差不会超过 1
    const root = new TreeNode(
        nums[mid],
        dfs(nums, min, mid - 1),
        dfs(nums, mid + 1, max)
    );

    return root;
}

判断指定树是否是平衡树

可以采用自底向上进行遍历，该遍历方法类似于后序遍历:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function isBalanced(root: TreeNode | null): boolean {
    return height(root) !== -1;
};

function height(root?: TreeNode) {
    if (!root) return 0;
    
    const left = height(root.left);
    if (left == -1) return -1;

    const right = height(root.right);
    if (right == -1) return -1;

    // 高度差超过 1
    if (Math.abs(left - right) > 1) return -1;

    // 当前层 + 1
    return Math.max(left, right) + 1;
}
  • 时间复杂度：O(n)O(n)，其中 nn 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)O(n)。
  • 空间复杂度：O(n)O(n)，其中 nn 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 nn。
❌
❌