• 数据结构--》解锁数据结构中树与二叉树的奥秘（一）

            数据结构中的树与二叉树，是在建立非线性数据结构方面极为重要的两个概念。它们不仅能够模拟出生活中各种实际问题的复杂关系，还常被用于实现搜索、排序、查找等算法，甚至成为一些大型软件和系统中的基础设施。

            无论你是初学者还是进阶者，本文将为你提供简单易懂、实用可行的知识点，帮助你更好地掌握树和二叉树在数据结构和算法中的重要性，进而提升算法解题的能力。接下来让我们开启数据结构与算法的奇妙之旅吧。

    目录

    树和森林的概念

    树的常考性质

    二叉树的定义及其性质

    二叉树的表示

    二叉树遍历

    树和森林的概念

    树的定义：树是一种非线性的数据结构，它由节点（node）和边（edge）组成。树的基本概念是以层次结构来组织和表示数据。

    在树中，有一个特殊的节点被称为根节点（root），它是树的顶层节点，所有其他节点都直接或间接地与根节点相连。除了根节点外，每个节点可以有零个或多个子节点（child），子节点又可以有自己的子节点，形成了树的分支结构。没有子节点的节点被称为叶节点（leaf）或叶子节点，它们位于树的最底层。节点之间的连接称为边，边描述了节点之间的关系。每个节点可以有零条到多条边连接到其子节点。任意两个节点之间都存在唯一的路径，通过路径可以从一个节点到达另一个节点。

    树的结构具有以下特点：

    1. 一个树可以由零个或多个节点组成。
    2. 有且只有一个根节点，它是树的起点。
    3. 每个节点可以有零个或多个子节点。
    4. 节点之间通过边相连，形成层次结构。
    5. 每个节点除了根节点外，都有且只有一个父节点。

    树的基本术语：

    结点之间的关系描述

            根节点（Root Node）：树的顶层节点称为根节点。根节点是树的起点，它没有父节点，其他所有节点都直接或间接地与根节点相连。

            祖先节点（Ancestor Node）：对于一个节点，它的所有上级节点（包括父节点、父节点的父节点等等）都被称为该节点的祖先节点。

            子孙节点（Descendant Node）：对于一个节点，它的所有下级节点（包括子节点、子节点的子节点等等）都被称为该节点的子孙节点。

            父节点（Parent Node）：一个节点的直接上一级节点称为其父节点。每个节点都可以有零个或多个子节点，但只能有一个父节点（除了根节点）。

            子节点（Child Node）：一个节点直接连接的下一级节点称为其子节点。一个节点可以有零个或多个子节点。

            兄弟节点（Sibling Node）：具有相同父节点的节点称为兄弟节点。兄弟节点在同一层级上。

            叶节点（Leaf Node）：也称为叶子节点，是没有子节点的节点，位于树的最底层。

            层级（Level）：根节点在第一层，其直接子节点在第二层，以此类推。一个节点所在的层级数即为该节点的层级。

    结点、树的属性描述

            节点值（Node Value）：每个节点都可以携带一个值或数据，表示该节点所代表的实际含义或信息。

            节点深度（Node Depth）：节点深度指的是该节点到根节点的路径长度，即从根节点到该节点所经过的边的数量。根节点的深度为0。

            节点高度（Node Height）：节点高度指的是该节点到其最远叶节点的路径长度，即从该节点到达最远叶节点所经过的边的数量。叶节点的高度为0。

            子树（Subtree）：对于一个树中的节点，可以以该节点为根构成的子树称为该节点的子树。

            树的大小（Tree Size）：指的是树中包含的所有节点的总数。

            树的高度（Tree Height）：指的是树中任意节点的高度的最大值。也可以理解为从根节点到最远叶节点的路径长度的最大值。

    有序树、无序树

            有序树（Ordered Tree）：有序树是指树中的子节点之间存在明确的顺序关系。在有序树中，每个子节点都有一个明确定义的位置，在遍历和表示树的时候需要按照顺序来考虑。例如，家谱树中的兄弟姐妹一般按照他们出生的先后顺序排列。

            无序树（Unordered Tree）：无序树是指树中的子节点之间没有明确的顺序关系。在无序树中，所有子节点都是平等的，没有先后之分。例如，文件系统中的目录结构就是一种无序树，其中的各个子目录之间没有特定的顺序。

            有序树和无序树的区别在于子节点的排列方式。在有序树中，子节点的顺序很重要，会影响到树的结构和含义；而在无序树中，子节点的顺序并不重要，只需要知道它们是该节点的子节点即可。

    森林

    森林（Forest）是指由多棵树（Tree）组成的集合。简单来说，森林可以看作是多个独立的树的集合。

    森林的特点在于其中的树之间是相互独立的，彼此之间没有直接的连接或关系。每棵树都可以独立地进行遍历和操作。

    需要注意的是，森林和树的层次结构是不同的概念。树是一种层次结构，它具有唯一的根节点和从根节点到其他节点的确定路径；而森林则是多个独立的树的集合，在森林中任意两棵树之间没有直接的联系。

    树的抽象数据类型：

    树的抽象数据类型定义了对树进行操作的基本操作集合，包括以下常见操作：

    1）创建树：创建一个空的树数据结构。

    2）插入节点：在树中插入一个新节点，并建立节点之间的关系。

    3）删除节点：从树中删除指定的节点，并调整节点之间的关系。

    4）遍历树：按照特定的顺序访问树中的节点，例如先序遍历、中序遍历、后序遍历等。

    5）查找节点：在树中查找指定的节点。

    6）获取树的属性：获取树的高度、节点个数、根节点等属性信息。

    树的抽象数据类型并不关注具体的实现方式，而是定义了可以对树进行的操作以及这些操作的预期行为。

    回顾重点，其主要内容整理成如下内容：  

    树的常考性质

    常见考点1：结点数 = 总度数 + 1

    常见考点2：度为m的树、m叉树的区别

    常见考点3：度为m的树第i层至多有  m^{i-1} 个结点 (i \geq 1)，同理m叉树第i层至多有 m^{i-1} 个结点 (i \geq 1)：

    常见考点4：高度为h的m叉树至多有 \frac{m^{h}-1}{m-1} 个结点。

    常见考点5：高度为h的m叉树至少有h个结点。高度为h度为m的树至少有h+m-1个结点。

    常见考点6：具有n个结点的m叉树的最小高度为 log_m(n(m-1)+1)

    高度最小的情况——所有结点都有m个孩子：

    回顾重点，其主要内容整理成如下内容：   

    二叉树的定义及其性质

    二叉树定义：

    二叉树是n(n⩾0)个结点的有限集合，其有以下两种情况：

    1）为空二叉树，即 n = 0 的时候

    2）由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。

    特点：每个结点至多只有两颗子树；左右子树不能颠倒。

    二叉树的五种状态：

    几个特殊的二叉树：

    满二叉树：所有叶节点都在同一层，并且所有非叶节点都有两个子节点的二叉树称为满二叉树。

    完全二叉树：除了最后一层节点之外，所有节点都拥有两个子节点，并且最后一层的节点都向左对齐的二叉树称为完全二叉树。

    二叉排序树：(比如找关键字为60的结点)

    平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。

    回顾重点，其主要内容整理成如下内容：   

    二叉树的常考性质：

    常见考点1：设非空二叉树中度为0、1和2的结点个数分别为 n0,n1,n2 ，则 n0=n2+1

    叶子结点比二分支结点多一个

    常见考点2：二叉树第i层至多有 2i−1 个结点(i⩾1);m叉树第i层至多有 m^{i-1} 个结点(i⩾1)

    常见考点3：高度为h的二叉树至多有 2h−1 个结点（满二叉树）

    高度为h的m叉树至多有 \frac{m^{h}-1}{m-1} 个结点

    完全二叉树的常考性质：

    常见考点1：具有n个(n>0)结点的完全二叉树的高度h为 log2(n+1) 或 log2n+1

    常见考点2：对于完全二叉树，可以由结点数 n 推出度为 0、1和2的结点个数为n0、n1和n2

    回顾重点，其主要内容整理成如下内容：    

    二叉树的表示

    在数据结构中，二叉树可以通过数组表示和链表存储表示两种方式来实现。下面分别对这两种表示方式进行简述：

    数组表示：

    数组表示是将二叉树的节点按照某种方式存储在一个一维数组中。一般情况下，数组可以按照层次遍历的顺序存储二叉树的节点。假设根节点存储在数组下标为0的位置，那么对于任意一个节点的索引 i，其左子节点的索引为 2i+1，右子节点的索引为 2i+2。如果某个位置为空，可以使用特定的空值表示。

    数组表示的优点：

    数组表示的优点是存储简单，通过数组索引可以快速访问到任意节点。缺点是当二叉树的形状发生改变时，需要重新调整数组的大小，可能涉及到大量的元素移动。

    1. #include 
    2. #include 
    3.  
    4. // 二叉树节点结构体
    5. struct TreeNode {
    6.     int val;
    7.     struct TreeNode* left;
    8.     struct TreeNode* right;
    9. };
    10.  
    11. // 构建二叉树的数组表示
    12. struct TreeNode* build_binary_tree(int arr[], int size) {
    13.     struct TreeNode** tree = malloc(sizeof(struct TreeNode*) * size);
    14.     
    15.     for (int i = 0; i < size; i++) {
    16.         if (arr[i] != -1) {
    17.             struct TreeNode* node = malloc(sizeof(struct TreeNode));
    18.             node->val = arr[i];
    19.             node->left = NULL;
    20.             node->right = NULL;
    21.             tree[i] = node;
    22.         } else {
    23.             tree[i] = NULL;
    24.         }
    25.     }
    26.     
    27.     for (int i = 0; i < size; i++) {
    28.         if (tree[i] != NULL) {
    29.             if (2 * i + 1 < size)
    30.                 tree[i]->left = tree[2 * i + 1];
    31.             if (2 * i + 2 < size)
    32.                 tree[i]->right = tree[2 * i + 2];
    33.         }
    34.     }
    35.     
    36.     struct TreeNode* root = tree[0];
    37.     free(tree);
    38.     
    39.     return root;
    40. }
    41.  
    42. // 测试代码
    43. int main() {
    44.     int arr[] = {1, 2, 3, 4, 5, 6, 7};
    45.     int size = sizeof(arr) / sizeof(arr[0]);
    46.     
    47.     struct TreeNode* root = build_binary_tree(arr, size);
    48.     
    49.     // 输出测试结果
    50.     printf("root: %d\n", root->val);
    51.     printf("left child of root: %d\n", root->left->val);
    52.     printf("right child of root: %d\n", root->right->val);
    53.     
    54.     return 0;
    55. }

    链表存储表示：

    链表存储表示是使用链表的方式来表示二叉树。每个节点包含一个指向其父节点的指针，一个指向其左子节点的指针，一个指向其右子节点的指针。

    链表存储表示的优点：

    链表存储表示的优点是可以灵活地插入、删除节点而不需要移动其他节点，适用于频繁变化的二叉树结构。缺点是访问某个节点需要从根节点开始遍历，效率相对较低。

    1. #include 
    2. #include 
    3.  
    4. // 二叉树节点结构体
    5. struct TreeNode {
    6.     int val;
    7.     struct TreeNode* left;
    8.     struct TreeNode* right;
    9. };
    10.  
    11. // 构建二叉树的链表存储表示
    12. struct TreeNode* build_binary_tree(int arr[], int size) {
    13.     if (size == 0) {
    14.         return NULL;
    15.     }
    16.     
    17.     struct TreeNode* root = malloc(sizeof(struct TreeNode));
    18.     root->val = arr[0];
    19.     root->left = NULL;
    20.     root->right = NULL;
    21.     
    22.     struct TreeNode** queue = malloc(sizeof(struct TreeNode*) * size);
    23.     int front = 0;
    24.     int rear = 0;
    25.     queue[rear++] = root;
    26.     
    27.     int i = 1;
    28.     while (i < size) {
    29.         struct TreeNode* node = queue[front++];
    30.         
    31.         // 处理左子节点
    32.         if (arr[i] != -1) {
    33.             node->left = malloc(sizeof(struct TreeNode));
    34.             node->left->val = arr[i];
    35.             node->left->left = NULL;
    36.             node->left->right = NULL;
    37.             queue[rear++] = node->left;
    38.         }
    39.         i++;
    40.         
    41.         // 处理右子节点
    42.         if (i < size && arr[i] != -1) {
    43.             node->right = malloc(sizeof(struct TreeNode));
    44.             node->right->val = arr[i];
    45.             node->right->left = NULL;
    46.             node->right->right = NULL;
    47.             queue[rear++] = node->right;
    48.         }
    49.         i++;
    50.     }
    51.     
    52.     free(queue);
    53.     
    54.     return root;
    55. }
    56.  
    57. // 测试代码
    58. int main() {
    59.     int arr[] = {1, 2, 3, 4, 5, 6, 7};
    60.     int size = sizeof(arr) / sizeof(arr[0]);
    61.     
    62.     struct TreeNode* root = build_binary_tree(arr, size);
    63.     
    64.     // 输出测试结果
    65.     printf("root: %d\n", root->val);
    66.     printf("left child of root: %d\n", root->left->val);
    67.     printf("right child of root: %d\n", root->right->val);
    68.     
    69.     return 0;
    70. }

    二叉树遍历

    遍历：按照某种次序把所有结点都访问一遍。根据二叉树的递归特性要么是个空二叉树，要么就是由“根结点+左子树+右子树”组成的二叉树

    根据二叉树的三种遍历规则，相关的具体案例如下：

    再进行具体的练习一遍：

    回顾重点，其主要内容整理成如下内容：

    二叉树的层序(次)遍历：

    其相应的代码实现如下：

    由遍历序列构造二叉树：

    回顾重点，其主要内容整理成如下内容： 

  • 相关阅读:
    Typora消失的图片？
    Ajax入门及jQuery库对Ajax的封装
    QPE更换Logo和相关信息
    数字签名与数字证书
    Python自动化测试selenium指定截图文件名方法
    STL：stack和queue
    从CPU100%高危故障到稳定在10%：一个月的优化之旅，成功上线！
    Latex IEEE模板导入中文问题
    2.5 C#视觉程序开发实例1----CamManager实现模拟相机采集图片(Form_Vision部分代码)
    Maven的详细介绍(maven的全据配置以及idea中maven的配置）
  • 原文地址：https://blog.csdn.net/qq_53123067/article/details/133612098