二叉树

字数

1042 字

阅读时间

5 分钟

二叉树结构

二叉树的基础理论不再赘述，这里重点介绍几种重要的二叉树结构。

二叉树的种类

• 满二叉树
• 完全二叉树

完全二叉树是满二叉树的子集。

二叉搜索树 (BST)

满二叉树和完全二叉树没有数值 node.val 的概念，而二叉搜索树（Binary Search Tree, BST）是有数值的，并遵循以下约束：

• 若其左子树不为空，则左子树上所有节点的值均小于其根节点的值。
• 若其右子树不为空，则右子树上所有节点的值均大于其根节点的值。
• 其左、右子树也分别为二叉搜索树。

平衡二叉搜索树 (AVL 树)

平衡二叉搜索树又被称为 AVL（Adelson-Velsky and Landis）树，它具有以下性质：

• 它是一棵空树，或者其左右两个子树的高度差的绝对值不超过 1。
• 其左右两个子树都是一棵平衡二叉树。

上图最后一棵树不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了 1。

注意：C++ 中 map、set、multimap、multiset 的底层实现都是平衡二叉搜索树，因此它们的增删操作时间复杂度是 O(log n)。unordered_map 和 unordered_set 的底层实现是哈希表。

二叉树遍历

二叉树主要有两种遍历方式：

1. 深度优先遍历 (DFS)：先深入到子节点，遇到叶子节点再返回。
2. 广度优先遍历 (BFS)：逐层遍历。

二叉树节点结构定义

// Definition for a binary tree node.
function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
}

深度优先遍历

深度优先遍历包括前序、中序和后序遍历。

递归法

• 前序遍历 (Preorder Traversal)

  var preorderTraversal = function(root) {
      let res = [];
      const dfs = function(root) {
          if (root === null) return;
          // 先序遍历，从父节点开始
          res.push(root.val);
          // 递归左子树
          dfs(root.left);
          // 递归右子树
          dfs(root.right);
      };
      // 使用闭包存储结果
      dfs(root);
      return res;
  };

• 中序遍历 (Inorder Traversal)

  var inorderTraversal = function(root) {
      let res = [];
      const dfs = function(root) {
          if (root === null) {
              return;
          }
          dfs(root.left);
          res.push(root.val);
          dfs(root.right);
      };
      dfs(root);
      return res;
  };

• 后序遍历 (Postorder Traversal)

  var postorderTraversal = function(root) {
      let res = [];
      const dfs = function(root) {
          if (root === null) {
              return;
          }
          dfs(root.left);
          dfs(root.right);
          res.push(root.val);
      };
      dfs(root);
      return res;
  };

迭代法

迭代遍历主要利用 栈 的“先入后出”特性（与广度优先遍历利用 队列 的“先入先出”特性相对）。

• 前序遍历 (Preorder Traversal)

  // 入栈顺序: 右 -> 左
  // 出栈顺序: 中 -> 左 -> 右
  var preorderTraversal = function(root, res = []) {
      if (!root) return res;
      const stack = [root];
      let cur = null;
      while (stack.length) {
          cur = stack.pop();
          res.push(cur.val);
          cur.right && stack.push(cur.right);
          cur.left && stack.push(cur.left);
      }
      return res;
  };

• 中序遍历 (Inorder Traversal)

  // 入栈顺序: 左 -> 右
  // 出栈顺序: 左 -> 中 -> 右
  var inorderTraversal = function(root, res = []) {
      const stack = [];
      let cur = root;
      while (stack.length || cur) {
          if (cur) {
              stack.push(cur);
              // 左
              cur = cur.left;
          } else {
              // --> 弹出 中
              cur = stack.pop();
              res.push(cur.val);
              // 右
              cur = cur.right;
          }
      }
      return res;
  };

• 后序遍历 (Postorder Traversal)

  // 入栈顺序: 左 -> 右
  // 出栈顺序: 中 -> 右 -> 左 (结果翻转)
  var postorderTraversal = function(root, res = []) {
      if (!root) return res;
      const stack = [root];
      let cur = null;
      do {
          cur = stack.pop();
          res.push(cur.val);
          cur.left && stack.push(cur.left);
          cur.right && stack.push(cur.right);
      } while (stack.length);
      return res.reverse();
  };

广度优先遍历 (BFS)

广度优先遍历使用队列实现，也称为层序遍历。

var levelOrder = function(root) {
    let res = [],
        queue = [];
    queue.push(root);
    if (root === null) {
        return res;
    }
    while (queue.length !== 0) {
        // 记录当前层级节点数
        let length = queue.length;
        // 存放每一层的节点
        let curLevel = [];
        for (let i = 0; i < length; i++) {
            let node = queue.shift();
            curLevel.push(node.val);
            // 存放当前层下一层的节点
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        // 把每一层的结果放到结果数组
        res.push(curLevel);
    }
    return res;
};

<NolebaseGitContributors />


<NolebaseGitChangelog />