数据结构-了解树和二叉树
一、了解树
1. 树的基本概念
树是一种非线性数据结构，主要用于表示层次关系。它由节点和连接这些节点的边组成。树的形状像一棵倒立的树，根部在上，树枝向下延伸。
2. 树的定义
树可以定义为一个空树或由以下性质的节点组成的非空集合：
- 空树：没有任何节点的树。
- 非空树：包含一个根节点和零个或多个子树的集合。
3. 基本术语
-
节点（Node）：树的基本元素，可以存储数据。每个节点可以有多个子节点。
-
边（Edge）：连接两个节点的线，表示父子关系。
-
根节点（Root）：树的顶端节点，没有父节点。每棵树只有一个根节点。
-
叶子节点（Leaf）：没有子节点的节点，位于树的最底层。
-
子节点（Child）：直接连接到某个节点的节点。
-
父节点（Parent）：直接连接到某个节点并且在其上方的节点。
-
兄弟节点（Sibling）：同一个父节点的子节点。
-
深度（Depth）：从根节点到该节点的边的数量。根节点的深度为0。
-
高度（Height）：从该节点到最远叶子节点的边的数量。叶子节点的高度为0。
-
层（Level）：树中节点的层数，根节点在第0层，根节点的子节点在第1层，以此类推。
-
子树（Subtree）：从某个节点开始的树，包括该节点及其所有后代节点。
-
度（Degree）：一个节点的度是它的子节点数量。
4. 森林
森林是由多个不相交的树组成的集合。可以将森林看作是多个树的组合。例如，如果我们从一棵树中删除根节点，剩下的子树就形成了一个森林。
5. 树的性质
-
节点数量与边的关系：一棵有 n 个节点的树必定有 n−1 条边。这是因为每增加一个节点，就必须增加一条边来连接它。
-
高度和节点数：树的高度与节点数量之间存在关系。对于一棵完全二叉树，节点数 n 和高度 h 的关系是n=2^(h+1) − 1。
-
叶子节点的数量：在一棵树中，叶子节点的数量 L 和非叶子节点的数量 N 之间的关系是 L=N+1（对于二叉树）。
-
树的遍历：树的遍历是指访问树中每个节点的过程。常见的遍历方式有：
- 前序遍历（Pre-order）：访问根节点，然后访问左子树，最后访问右子树。
- 中序遍历（In-order）：访问左子树，访问根节点，然后访问右子树。
- 后序遍历（Post-order）：访问左子树，访问右子树，然后访问根节点。
6. 树的类型
-
二叉树：每个节点最多有两个子节点（左子节点和右子节点）。
-
平衡树：树的高度尽量保持平衡，以优化查找效率，如AVL树和红黑树。
-
N叉树：每个节点可以有N个子节点。
-
Trie树：用于存储字符串的树，常用于词典和自动补全。
二、了解二叉树
1. 二叉树的定义
二叉树（Binary Tree） 是一种每个节点最多有两个子节点的数据结构。这两个子节点通常被称为左子节点和右子节点。
2. 基本术语
- 根节点（Root）：二叉树的顶端节点。
- 叶子节点（Leaf）：没有子节点的节点。
- 深度（Depth）：从根节点到该节点的边的数量。
- 高度（Height）：从该节点到最远叶子节点的边的数量。
- 度（Degree）：节点的子节点数量（0、1或2）。
3. 二叉树的性质
-
节点数量与高度：
- 一棵满二叉树的高度为 h 时，节点数量为 2^(h+1) − 1。
- 一棵完全二叉树的高度为 h 时，节点数量在 2^h 到 2^(h+1) − 1 之间。
-
叶子节点数量：
- 在一棵二叉树中，如果有 n 个节点，叶子节点的数量 L 和非叶子节点的数量 N 之间的关系是：L=N+1
4. 特殊的二叉树
-
满二叉树（Full Binary Tree）：
- 每个节点要么是叶子节点，要么有两个子节点。
-
完全二叉树（Complete Binary Tree）：
- 除了最后一层外，其他层都是满的，且最后一层的节点尽可能地集中在左侧。
-
平衡二叉树（Balanced Binary Tree）：
- 任意节点的左右子树的高度差不超过1。
-
二叉搜索树（Binary Search Tree, BST）：
- 对于每个节点，左子树的所有节点的值小于该节点的值，右子树的所有节点的值大于该节点的值。
5. 二叉树的遍历
- 前序遍历（Pre-order）：访问根节点 → 访问左子树 → 访问右子树。
- 中序遍历（In-order）：访问左子树 → 访问根节点 → 访问右子树。
- 后序遍历（Post-order）：访问左子树 → 访问右子树 → 访问根节点。
- 层序遍历（Level-order）：按层访问节点，从上到下，从左到右。
6. K 叉树
K 叉树（K-ary Tree） 是一种每个节点最多有 K 个子节点的树结构。
- 定义：K 叉树的每个节点可以有 0 到 K 个子节点。
- 性质：
- K 叉树的节点数量与高度的关系类似于二叉树。例如，深度为 h 的 K 叉树的最大节点数为 [ K^(h+1)−1 ] / (K−1)。
- K 叉树的遍历方法与二叉树类似，但在遍历时需要访问所有 K 个子节点。
三、二叉树的顺序存储
1. 二叉树顺序存储的定义
顺序存储 是将二叉树的节点按照一定顺序存储在数组中的一种方法。该方法适用于完全二叉树或满二叉树，因为它们的节点排列较为规则，便于使用数组进行存储。
2. 存储结构
在顺序存储中，通常使用一个一维数组来存储二叉树的节点。假设数组的下标从 0 开始，节点的存储规则如下：
- 根节点 存储在数组的第 0 个位置（索引 0）。
- 对于任意节点 ii（索引从 0 开始）：
- 左子节点的索引为 2*i+1
- 右子节点的索引为 2*i+2
- 父节点的索引为 (i−1)/2（向下取整）
3. 存储示例
假设有以下二叉树：
A
/ \
B C
/ \ \
D E F
这个二叉树的顺序存储可以表示为数组：
Index: 0 1 2 3 4 5
Array: [A, B, C, D, E, F]
- A (根节点) 存储在索引 0
- B (左子节点) 存储在索引 1
- C (右子节点) 存储在索引 2
- D (B 的左子节点) 存储在索引 3
- E (B 的右子节点) 存储在索引 4
- F (C 的右子节点) 存储在索引 5
4. 优点
- 简单直观：顺序存储结构简单，容易实现。
- 随机访问：可以通过数组的下标快速访问任意节点，时间复杂度为 O(1)。
- 空间利用率高：适用于完全二叉树，能有效利用数组空间。
5. 缺点
- 空间浪费：对于不完全二叉树，可能会造成大量空闲空间。例如，如果树的高度很大，但节点数量很少，数组的大小可能会非常大。
- 动态调整困难：在插入或删除节点时，可能需要频繁移动数组中的元素，导致效率降低。
- 不适合稀疏树：对于稀疏的二叉树，顺序存储并不高效。
6. 适用场景
顺序存储适用于以下场景：
- 完全二叉树或满二叉树的存储。
- 节点数量相对固定且较少变化的二叉树。
- 需要频繁访问节点的场景。
四、二叉树的链式存储
1. 二叉树链式存储的定义
链式存储 是通过节点之间的指针关系来存储二叉树的一种方式。每个节点不仅存储数据，还包含指向其左右子节点的指针。链式存储适用于任意形状的二叉树，特别是对于不完全二叉树或稀疏树。
2. 存储结构
在链式存储中，每个节点通常包含以下三个部分：
- 数据域（Data）：存储节点的值。
- 左指针（Left Pointer）：指向左子节点。
- 右指针（Right Pointer）：指向右子节点。
节点结构示例（C 语言）
// 定义二叉树节点结构
typedef struct TreeNode {
int data; // 数据域
struct TreeNode* left; // 左子节点指针
struct TreeNode* right; // 右子节点指针
}TreeNode , *BiTree;
3. 链式存储的优点
- 灵活性高：可以动态调整树的结构，方便进行插入和删除操作。
- 空间利用率高：只在需要时分配内存，避免了顺序存储中可能的空间浪费。
- 适合稀疏树：对于不完全或稀疏的二叉树，链式存储能够有效利用内存。
4. 链式存储的缺点
- 访问效率低：由于节点不连续存储，随机访问某个节点的时间复杂度为 O(n)，而顺序存储为 O(1)。
- 额外空间开销：每个节点需要额外的指针空间，增加了内存开销。
5. 构建链式存储的示例
假设我们要构建以下二叉树：
A
/ \
B C
/ \ \
D E F
我们可以通过链式存储来表示这个二叉树，节点之间的指针关系如下：
链式存储中，节点的指针将指向相应的子节点：
- 节点 A 的左指针指向节点 B，右指针指向节点 C。
- 节点 B 的左指针指向节点 D，右指针指向节点 E。
- 节点 C 的右指针指向节点 F。
总结：
本文详细介绍了树和二叉树的基本概念、定义、术语、性质、以及不同的存储方式。以下是主要内容的概述：
一、树的基本概念
- 树的定义：树是一种非线性数据结构，由节点和连接这些节点的边组成。树可以是空树或包含根节点及其子树的非空树。
- 基本术语：包括根节点、叶子节点、深度、高度和度等。
- 森林：由多个不相交的树组成的集合。
- 树的性质：如前序、中序、后序遍历等。
二、二叉树
- 定义：二叉树是一种每个节点最多有两个子节点的树结构。
- 基本术语：包括根节点、叶子节点、深度、高度和度等。
- 性质：如满二叉树和完全二叉树的节点数量关系，以及叶子节点和非叶子节点的关系。
- 特殊的二叉树：如满二叉树、完全二叉树、平衡二叉树和二叉搜索树。
- 遍历方式：包括前序遍历、中序遍历、后序遍历和层序遍历。
- K叉树：每个节点最多有 K 个子节点的树结构。
三、二叉树的顺序存储
- 定义：使用一维数组存储二叉树节点，适用于完全二叉树或满二叉树。
- 存储结构：根节点存储在数组的第0个位置，子节点的索引规则明确。
- 优点：简单直观、随机访问、空间利用率高。
- 缺点：空间浪费、动态调整困难、不适合稀疏树。
- 适用场景：适合完全二叉树和节点数量相对固定的二叉树。
四、二叉树的链式存储
- 定义：通过节点之间的指针关系存储二叉树，适用于任意形状的二叉树。
- 存储结构：每个节点包含数据域和左右子节点指针。
- 优点：灵活性高、空间利用率高、适合稀疏树。
- 缺点：访问效率低、额外空间开销。
- 构建示例：通过链式存储表示特定的二叉树结构，展示节点之间的指针关系。