二叉树

算法 / 常见算法与数学
字数统计: 1.8k   |   阅读时长≈ 7 分钟

二叉树可以算是最基础的数据类型。

很多复杂的数据结构都是基于二叉树的，比如 红黑树（二叉搜索树）、多叉树、二叉堆、图、字典树、并查集、s 线段树 等等。

二叉树可以代表一种递归的思维方式,比如 回溯算法、BFS 算法、动态规划 本质上也是把具体问题抽象成树结构。

树的概念

1
2
3
4
5
6
7
    1
   / \
  2   3
 /   / \
4   5   6
   /     \
  7       8

  • 每个节点下方直接相连的节点称为子节点，上方直接相连的节点称为父节点。比方说节点 3 的父节点是 1，左子节点是 5，右子节点是 6；节点 5 的父节点是 3，左子节点是 7，没有右子节点。

  • 我们称最上方那个没有父节点的节点 1 为根节点，称最下层没有子节点的节点 4、7、8 为叶子节点。

  • 从根节点到最下方叶子节点经过的节点个数为二叉树的最大深度/高度，上面这棵树的最大深度是 4，即从根节点 1 到叶子节点 7 或 8 的路径上的节点个数。

  • 满二叉树: 每一层节点都是满的, 假设深度为 h，那么总节点数就是 2^h - 1。

    1
    2
    3
    4
    5
    6
    7
           1
         /   \
        2     3
       / \   / \
      4   9 5   6
     / \ / \/ \ / \
    10 11 7 12 13 8 14

  • 完全二叉树： 二叉树的每一层的节点都紧凑靠左排列，且除了最后一层，其他每层都必须是满的, 满二叉树就是特殊的完全二叉树。也可以说 完全二叉树的左右子树也是完全二叉树。 或 完全二叉树的左右子树中，至少有一棵是满二叉树。

    1
    2
    3
    4
    5
    6
    7
           1
         /   \
        2     3
       / \   / \
      4   9 5   6
     / \ / \
    10 1 7 2

  • 二叉搜索树：对于树中的每个节点，其左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。为左小右大的特性，可以让我们在 BST 中快速找到某个节点，或者找到某个范围内的所有节点，这是 BST 的优势所在。

    1
    2
    3
    4
    5
        7
       / \
      4   9
     / \   \
    1   8   10

遍历方式

层序遍历

一层一层地遍历二叉树,显然先访问的节点需要先处理，而左右节点暂时用不到需要先存起来，自然想到用队列来处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var levelOrderTraverse = function (root) {
  if (root === null) {
    return;
  }
  var q = [];
  q.push(root);
  while (q.length !== 0) {
    var cur = q.shift();
    // 访问 cur 节点
    console.log(cur.val);

    // 把 cur 的左右子节点加入队列
    if (cur.left !== null) {
      q.push(cur.left);
    }
    if (cur.right !== null) {
      q.push(cur.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
var levelOrderTraverse = function (root) {
  if (root === null) {
    return;
  }
  let q = [];
  q.push(root);
  // 记录当前遍历到的层数（根节点视为第 1 层）
  let depth = 1;

  while (q.length !== 0) {
    let sz = q.length;
    // 使用额外的变量，记录每层的节点个数
    // 也可以直接复制q队列，这样可以避免 shift 操作的O(n) 时间复杂度
    for (let i = 0; i < sz; i++) {
      let cur = q.shift();
      // 访问 cur 节点，同时知道它所在的层数
      console.log("depth = " + depth + ", val = " + cur.val);

      // 把 cur 的左右子节点加入队列
      if (cur.left !== null) {
        q.push(cur.left);
      }
      if (cur.right !== null) {
        q.push(cur.right);
      }
    }
    depth++;
  }
};

同理还可以添加更多的下信息，现在只知道整个树的层数，还可以为每个节点维护他的层数, 一般称作路径的权重，即从根节点到当前的节点。

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
function State(node, depth) {
  this.node = node;
  this.depth = depth;
}

var levelOrderTraverse = function (root) {
  if (root === null) {
    return;
  }
  // @visualize bfs
  var q = [];
  // 根节点的路径权重和是 1
  q.push(new State(root, 1));

  while (q.length !== 0) {
    var cur = q.shift();
    // 访问 cur 节点，同时知道它的路径权重和
    console.log("depth = " + cur.depth + ", val = " + cur.node.val);

    // 把 cur 的左右子节点加入队列
    if (cur.node.left !== null) {
      q.push(new State(cur.node.left, cur.depth + 1));
    }
    if (cur.node.right !== null) {
      q.push(new State(cur.node.right, cur.depth + 1));
    }
  }
};
递归遍历

先深入到一个分支中，在逐层的返回。

1
2
3
4
5
6
7
8
9
10
11
// 二叉树的遍历框架
var traverse = function (root) {
  if (root === null) {
    return;
  }
  // 前序位置
  traverse(root.left);
  // 中序位置
  traverse(root.right);
  // 后序位置
};

但是在不同的位置写代码，获取到的信息是不同的，所谓的前中后，是相对于根节点的先后。

  • 前序遍历： 根节点 => 左节点 => 右节点， 代码位置写在接入左树之前，因此先访问根节点，在访问左树的根节点。对于一个子树，只有左子树遍历完成后，才回去处理右子树，可以看作是进入一个二叉树节点的时候执行

  • 中序遍历： 左节点 => 根节点 => 右节点，代码会一直递归调用到左子树的左叶子节点，当左叶子节点访问完毕后，会弹出当前的调用栈，而上一个调用栈正是左节点的父节点，也就是根节点,可以看作是二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。

  • 后序遍历： 左节点 => 右节点 => 根节点，代码会一直递归调用到左子树的右叶子节点，当左右子节点访问完毕后，会弹出当前的调用栈，而上一个调用栈正是右节点的父节点，也就是根节点,可以看作是离开一个二叉树节点的时候执行。

而递归遍历常用于寻找最短路径， [二叉树最小/大深度], [二叉树直径],递归和遍历各有优势，遍历的思想是配合外部变量，递归则是将问题分解为子问题。

有一些问题虽然是在二叉树的遍历模型下，但是需要根据条件进入不同的分支处理，并在其中穿插其他的逻辑代码。 [二叉树展开为链表] [填充每个节点的下一个右侧节点指针]

二叉树的序列化

层序遍历

这应该是最容易想到的一种方法，就像 LeetCode 题目给出的可视化数据一样，将每一层的数据依次放入到数组中，就可以对二叉树序列化，但是需要注意的是要保留空节点，这样才能描述每一层节点之间的关系

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
var serialize = function (root) {
  if (root === null) return [];
  const queue = [root];
  const res = [];
  while (queue.length) {
    const first = queue.shift();
    res.push(first === null ? first : first.val);
    if (first !== null) queue.push(first.left, first.right);
  }
  return res;
};

var deserialize = function (data) {
  if (data.length === 0) return null;
  let index = 0;
  let root = new TreeNode(data[index++]);
  let queue = [root];

  while (data[index] !== undefined) {
    const node = queue.shift();
    const left = data[index++];
    const right = data[index++];

    node.left = left === null ? left : new TreeNode(left);
    node.right = right === null ? right : new TreeNode(right);
    if (left !== null) queue.push(node.left);
    if (right !== null) queue.push(node.right);
  }
  return root;
};
二叉树的唯一性
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2025 SunZhiqi

此时无声胜有声！

支付宝
微信