树结构简介

什么是树？

树是一种非线性数据结构，用于表示父节点与子节点之间的层次关系。树中的每个节点通过有向边与其他节点相连。

为什么要使用树？

相比数组或链表等线性数据结构，使用树的主要优势在于：我们不需要在O(n)线性时间内搜索元素，可以实现更高效的查找操作。

树的相关重要术语

在深入探讨树的结构之前，先熟悉一些基本术语。最常用的术语包括：

• 节点（Node）：树的基本组成单元。每个节点包含数据以及指向其子节点的若干指针，这些指针可能为空（null）。
• 边（Edge）：连接两个节点的基本组成部分。
• 根节点（Root）：唯一没有入边的节点，位于树的最顶端。
• 叶子节点（Leaf）：没有子节点的节点。
• 路径（Path）：由边连接的一系列有序节点。
• 高度（Height）：从根节点到最远叶子节点的最长路径上的边数。

在上图中，6、4、5 等都是树中的节点，其中节点6是该树的根节点。而节点1、3、5 和 8则是这棵树的叶子节点。

树中的每一个节点都通过边相互连接。例如，节点6、4、2 和 1通过边相连，从节点6到节点1构成一条路径。该树的高度为3。

• 父节点（Parent）：如果一个节点有向外的边指向其他节点，则称其为这些节点的父节点。
• 子节点（Child）：如果一个节点有来自另一个节点的入边，则它是该节点的子节点。
• 兄弟节点（Sibling）：具有相同父节点的多个节点互称为兄弟节点。
• 祖先节点（Ancestor）：从某一节点向上追溯至根节点路径上的所有节点，均称为该节点的祖先节点。
• 层级（Level）：某个节点所在的层级是指从根节点到该节点所经过的边的数量。

在上图中，6 是 4 和 8 的父节点，而这两个节点是 6 的子节点。同样地，节点1 和 节点3在这棵树中是兄弟节点，而节点 4 和 6 是它们的祖先节点。