树基础：结构、术语和使用案例

Source: Dev.to

什么是树？

Tree 是一种层次化、非线性的数据结构，由 节点 组成。

每个节点：

• 存储一个值
• 拥有零个或多个子节点
• 恰好有一个父节点（根节点除外）

常见的现实类比：

• 文件夹结构
• 公司组织结构图
• 网站 DOM

当数据天然呈现层次结构时，树是理想的选择。

常见的树类型

树的变体很多，但以下是软件开发和面试中最常用的几种：

• Binary Tree
• Binary Search Tree (BST)
• AVL Tree
• Red‑Black Tree
• N‑ary Tree
• Trie（前缀树）

本文重点讨论 Binary Tree，因为大多数遍历逻辑都是从这里开始的。

什么是二叉树？

Binary Tree 是一种每个节点最多拥有 两个子节点 的树。

class Node {
  constructor(key, left = null, right = null) {
    this.left = left;
    this.right = right;
    this.val = key;
  }
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

// The tree structure:
//        1
//       / \
//      2   3
//     / \
//    4   5

你也可以使用嵌套的构造函数调用来构建树，但这种写法对初学者更易读。

树的遍历

遍历描述了我们如何“走访”树。四种基本的遍历模式如下：

• Inorder
• Preorder
• Postorder
• Breadth‑First Search (Level Order)

我们将在 Part 1.2 中深入探讨每一种，这里先给出快速预览。

Inorder（左 → 根 → 右）

在二叉搜索树中很有用，因为它会按排序顺序返回节点。

function inorderTraversal(node) {
  if (node !== null) {
    inorderTraversal(node.left);
    console.log(node.val);
    inorderTraversal(node.right);
  }
}

Preorder（根 → 左 → 右）

适用于序列化或复制树。

function preorderTraversal(node) {
  if (node !== null) {
    console.log(node.val);
    preorderTraversal(node.left);
    preorderTraversal(node.right);
  }
}

Postorder（左 → 右 → 根）

常用于删除或求值树。

function postorderTraversal(node) {
  if (node !== null) {
    postorderTraversal(node.left);
    postorderTraversal(node.right);
    console.log(node.val);
  }
}

Breadth‑First Search（层序遍历）

从左到右访问树的每一层。

function breadthFirstTraversal(root) {
  const queue = [root];

  while (queue.length > 0) {
    const currentNode = queue.shift();
    console.log(currentNode.val);

    if (currentNode.left) queue.push(currentNode.left);
    if (currentNode.right) queue.push(currentNode.right);
  }
}

为什么遍历很重要

不同的问题需要不同的遍历策略：

• Inorder → 在 BST 中得到有序输出
• Preorder → 重建或序列化树
• Postorder → 求值表达式、删除结构
• BFS → 最短路径、逐层处理

在面试中你会反复看到这些模式。

继续数据结构系列

本文是持续更新的 Data Structures Series 的一部分，旨在提供清晰的概念、真实世界的直觉以及 JavaScript 实现。

👉 Data Structures Series — Overview