%% # 纲要 > 主干纲要、Hint/线索/路标 - **树的表示** - **二叉树** - 特殊二叉树 - 二叉搜索树 # Q&A #### 已明确 #### 待明确 > 当下仍存有的疑惑 **❓<font color="#c0504d"> 有什么问题？</font>** # Buffer ## 闪念 > sudden idea ## 候选资料 > Read it later %% # 树的基本概念 ## 树的定义 树是一种 "**无环连通图**"： **任意两节点之间互通，且只有唯一通路** - 树是 "**极小连通图**"：删除任一边后，不再连通，将得到两棵树。 - 树是 "**极大无环图**"：向任意两节点间添加一条边，都将得到一个环。 ## 树的属性 - 树中**任意节点与根节点之间，只存在唯一的通路**。 - 树中**节点数与边数**的关系： **$n$ 个节点的树，共有 $n-1$ 条边**。 - 树中**节点的==深度**==：等于根节点到该节点的**路径长度** $\text{depth}(v)=|\text{path}(v)|$，即经历的**边的条数**。 - **根节点的深度为 0** ； - 树的深度即为所有叶节点中的**最大深度**； - 树中**节点的==高度**==：该节点到**其子树中最远叶节点**的**最长路径长度**（即其子树的最大深度）$\text{height(}v)=\text{height(subtree(}v))$ - **叶节点的高度均为 0**； - **空树的高度特别地取为 $-1$**。 - 根节点的高度即为**整颗树的高度** $\text{height}(T)$ > [!NOTE] 树上节点的**深度**与**高度**示意： > > 对任一节点 $v$ 而言，$\text{depth}(v)+\text{height}(v)\le \text{height}(T)$，其深度与高度之和不会超过**全树的高度**。 > > ![[_attachment/00-数据结构与算法笔记/数据结构/树.assets/IMG-树-D58A4D21EFF401B7DEE8F1374D4B447A.png|903]] > > <br> ### 无根树的最长路径 **树的最长路径一定是某个叶子节点到另一个叶子节点的路径**。 求无根树的 **==最长路径==**（直径）： - **从任意顶点 A 出发，找到 "==距离其最远的顶点 B=="，则 B 一定是 "最长路径" 上的两端点之一**。 - **再从 B 出发找到 "==距离其最远的 C=="，则 ==B 到 C 必定是最长路径==**。 > [!note] 证明思路 > > **无根树是连通的**，从任意顶点 A 出发，**必然会到达最长路径上的某一顶点**。从该顶点继续出发，**所到达的最远顶点必然是最长路径的端点**。 > > > ![[Excalidraw-Solution/树_0.excalidraw|715]] > <br><br> # 树的表示方式 > 如何存储，表示一棵一般树？ 几种方式： - 方式一：**为每个节点存储其父节点** （可基于数组存储） - 方式二：**存储每个节点的子节点集合** （可基于哈希表存储，key 为节点标识，value 为数组存储其所有子节点标识） - 方式三：**综合方式二和方式一** - 方式四：**长子兄弟法** （二叉树的方式，存储其 "**首个子节点**" 以及 "**下一个兄弟节点**"） ### 方式一：为每个节点存储其父节点 表示方式： - 可用 **==数组==** 存储，**$n$ 个节点的标识**为 $[0, n-1)$，**数组元素 `parent[i]` 即为节点 `i` 的父结点标识**。 优点： - **便于获取各个节点的父结点** - 从任意节点出发，顺着父结点一路向上，最终可以抵达根节点。 缺点： - 不便于获取子节点、兄弟节点，需要 $O(n)$。  ### 方式二：为每个节点存储其子节点集合 表示方式： - 哈希表 `u2v` 中 **`key`存储节点标识，`value` 为一个集合，存储其所有子节点**。 优点： - **便于获取各个节点的子节点** 缺点： - 不便于获取各个节点的父亲节点，需要 $O(n)$。  ### 方式三：综合方式二和方式一  ### 方式四：长子兄弟法 表示方式：为**每个节点**存储其 **首个子节点 `firstChild()`**，以及 **下一个兄弟节点** `nextSibling()`。  > [!NOTE] 使用**长子兄弟法** 来描述多叉树，则凡是**有根**且**有序**的树，**均可以以二叉树的形式表示**。 > > - 将 `firstChild()` => `lc()` ，作为左子节点； > - 将 `nextSibling()` => `rc()`，作为右子节点。 %% # 树的搜索遍历 ![[Excalidraw-Solution/树.excalidraw.svg|700]] %% %%[[Excalidraw-Solution/树.excalidraw.md|🖋 Edit in Excalidraw]]%% <br><br> # 参考资料 - [树基础 - OI Wiki](https://oi-wiki.org/graph/tree-basic/) # Footnotes [^1]: [霍夫曼树 - OI Wiki](https://oi-wiki.org/ds/huffman-tree/)