什么是树

提示

树是一种常见的数据结构，用于表示层次关系的数据。每个节点可以有零个或多个子节点。树的顶点称为根节点，其他节点称为子节点或叶节点。

树的基本概念

• 根节点（Root Node）：树的顶点。
• 节点（Node）：树的基本单元，可以包含数据和指向子节点的链接。
• 叶节点（Leaf Node）：没有子节点的节点。
• 父节点（Parent Node）：有子节点的节点。
• 子节点（Child Node）：从父节点衍生出来的节点。
• 层级（Level）：节点的深度，从根节点开始，根节点的层级为0。
• 子树（Subtree）：由节点及其所有后代节点组成的树。

树的基本术语

1. 结点的度（Degree）：结点的子树个数
2. 树的度：树的所有结点中最大的度数
3. 叶结点（Leaf）：度为0的结点
4. 父结点（Parent）：有子树的结点是其子树的根结点的父结点
5. 子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。
6. 兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。
7. 路径和路径长度：从结点n1到nk的路径为一个结点序列n1 , n2 ,... , nk , ni是 ni+1的父结点。路径所包含边的个数为路径的长度。
8. 祖先结点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。
9. 子孙结点(Descendant)：某一结点的子树中的所有结点是这个结点的子孙。
10. 结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1。
11. 树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度。

树的表示

树可以通过多种方式表示。常见的表示方法包括：

1. 嵌套对象：使用嵌套的JavaScript对象表示树结构。
2. 邻接表：使用数组或哈希表表示每个节点及其子节点的关系。
3. 类和实例：使用类和实例表示树和节点。