树
一句话解释
树是一种层级数据结构,每个节点有一个父节点和零或多个子节点,从根节点开始。
用大白话说
树是由节点构成的层级结构。顶部有一个根节点,其余每个节点都恰好有一个父节点和零或多个子节点。没有子节点的节点称为叶子。这种父子关系形成分支结构,形如一棵倒置的树。树在计算中无处不在:文件系统(文件夹与文件)、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() 以深度优先递归访问每个节点。
相关术语
相关资源
相关课程
- 数据结构
学习树与图。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。