树的定义、基本术语及性质

树的定义、基本术语及性质

引用

CSDN

1.

https://m.blog.csdn.net/m0_64055811/article/details/137720224

在计算机科学领域，树（Tree）是一种重要的非线性数据结构，用于模拟具有层级关系的数据集合。它由节点（Node）组成，每个节点可以有零个或多个子节点，但只有一个父节点（除了根节点外）。本文将详细解释树的基本定义和术语，并探讨其性质。

1. 树的定义

树是由节点组成的数据结构，它具有以下特点：

1. 节点：存储数据的单元，可以是任何类型的值。
2. 边：连接两个节点的线，表示它们之间的父子关系。
3. 根：仅有一个根节点，没有父节点，是树的起点。
4. 子树：根节点之外的任意节点都可以作为子树的根，形成独立的树。
5. 叶子：没有子节点的节点称为叶节点。
6. 分支节点：具有一个或多个子节点的节点。

以下是错误示例：

除了根节点外，任何一个结点都有且仅有一个前驱

2. 基本术语

1. 父节点：给定节点直接相连且方向指向该节点的节点。
2. 子节点：给定节点直接相连且方向远离该节点的节点。
3. 兄弟节点：具有同一个父节点的节点。
4. 深度：从根到特定节点的唯一路径上的边数。
5. 高度：从特定节点到叶子的最长路径上的边数。
6. 度：一个节点的子节点个数。

3. 树的性质

1. 节点与边的关系：在任何树中，边的数量总是等于节点数减去一。
2. 唯一路径：任意两个节点之间有且仅有一条简单路径。
3. 层次关系：树中的节点形成了明确的层次结构。
4. 无环：树中不存在环路，即没有路径可以从一个节点出发回到自身。

本文原文来自CSDN