Skip to content

树

一句话解释

树是一种层级数据结构,每个节点有一个父节点和零或多个子节点,从根节点开始。

用大白话说

树是由节点构成的层级结构。顶部有一个根节点,其余每个节点都恰好有一个父节点和零或多个子节点。没有子节点的节点称为叶子。这种父子关系形成分支结构,形如一棵倒置的树。树在计算中无处不在:文件系统(文件夹与文件)、DOM(HTML 元素)、抽象语法树(解析后的代码)、决策树、搜索树。最常见变体是二叉树(每个节点最多两个子节点),尤其是二叉搜索树——左子更小、右子更大,可实现 O(log n) 查找。树的操作包括遍历(前序、中序、后序访问每个节点)、查找、插入与删除。树是表示层级数据、以及将问题划分为子问题的算法的自然结构。

示例

javascript
class TreeNode {
  constructor(value) { this.value = value; this.children = []; }
}

const root = new TreeNode("root");
const a = new TreeNode("a"); const b = new TreeNode("b");
root.children.push(a, b);
a.children.push(new TreeNode("a1"));

function traverse(node, depth = 0) {
  console.log("  ".repeat(depth) + node.value);
  node.children.forEach(c => traverse(c, depth + 1));
}
traverse(root);
// root
//   a
//     a1
//   b

每个 TreeNode 持有一个值和一个子节点列表。traverse() 以深度优先递归访问每个节点。

相关术语

相关资源

相关课程

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回术语表