【408考点之数据结构】树的基本概念

树的基本概念

树是一种重要的非线性数据结构，在计算机科学和许多实际应用中具有广泛的应用。树的基本概念包括树的定义、基本术语、树的性质和树的类型等。

一、树的定义

树（Tree）是n（n≥0）个节点的有限集合。对于任意一个非空树：

1. 有且仅有一个称为根（Root）的节点。
2. 当n>1时，其余节点可分为m（m>0）个互不相交的有限集合T1，T2，…，Tm，每一个集合本身又是一棵树，称为根的子树（Subtree）。

二、树的基本术语

1. 节点（Node）：树的基本单位，包含一个数据元素及若干指向其子节点的分支。
2. 根节点（Root）：树的顶端节点，没有父节点。
3. 叶节点（Leaf）：没有子节点的节点。
4. 内部节点（Internal Node）：至少有一个子节点的节点。
5. 子节点（Child）和父节点（Parent）：节点的直接下属节点称为子节点，直接上属节点称为父节点。
6. 兄弟节点（Sibling）：具有相同父节点的节点互为兄弟。
7. 路径（Path）：从一个节点到另一个节点经过的节点序列。
8. 树的度（Degree）：树中节点的最大度数。
9. 节点的度（Degree of a Node）：节点的子树个数。
10. 层次（Level）：节点所在的层次，从根开始定义，根为第1层，根的子节点为第2层，依次类推。
11. 树的深度（Depth）或高度（Height）：树中节点的最大层次。

三、树的性质

1. 性质1：在非空树中，n个节点共有n-1条边。
2. 性质2：度为m的树中，第i层最多有m^(i-1)个节点（i≥1）。
3. 性质3：深度为h的m叉树最多有(m^h - 1)/(m - 1)个节点（m > 1）。
4. 性质4：具有n个节点的完全二叉树的深度为⌊log₂n⌋ + 1。
5. 性质5：n个节点的树至少有⌈log₂(n + 1)⌉层。

四、树的类型

1. 二叉树（Binary Tree）：每个节点最多有两个子树的树结构。二叉树常用于实现堆、二叉搜索树、平衡树等。
2. 完全二叉树（Complete Binary Tree）：除了最后一层外，所有层的节点都达到最大值，且最后一层的节点都在左侧。
3. 满二叉树（Full Binary Tree）：每个节点要么是叶子节点，要么有两个子节点。
4. 平衡二叉树（Balanced Binary Tree）：任何节点的两个子树的高度差不超过1的二叉树。
5. 二叉搜索树（Binary Search Tree）：左子树所有节点的值小于根节点的值，右子树所有节点的值大于根节点的值。
6. 森林（Forest）：m（m≥0）棵互不相交的树的集合。