当前位置:   article > 正文

深入探索C语言中的二叉树:数据结构之旅

深入探索C语言中的二叉树:数据结构之旅

引言

在计算机科学领域,数据结构是基础中的基础。在众多数据结构中,二叉树因其在各种操作中的高效性而脱颖而出。二叉树是一种特殊的树形结构,每个节点最多有两个子节点:左子节点和右子节点。这种结构使得搜索、插入、删除等操作可以在对数时间复杂度内完成,这对于算法性能的提升至关重要。

核心内容

  • 二叉树的基本概念   

  • 我们首先需要理解什么是二叉树。在本文的代码中,二叉树由结构体BinaryTreeNode表示,每个节点包含数据以及指向左右子节点的指针。

  • 创建和销毁二叉树

    代码演示了如何使用BuyTreeNode函数为一个新节点分配内存,并通过CreateNode函数来构建一个简单的二叉树。同时,DestoryTree函数展示了如何安全地销毁二叉树,释放其占用的资源。

  • 二叉树的遍历

    遍历是二叉树中最重要的操作之一。我们介绍了三种基本的遍历方式:前序(PrevOrder)、中序(InOrder)和后序(PostOrder)遍历。这些遍历方法在二叉树的搜索和排序操作中发挥着关键作用。

  • 二叉树的其他属性

    除了遍历,我们还探讨了如何使用代码来确定二叉树的大小(TreeSize)、叶子节点的数量(TreeLeafSize)、树的高度(TreeHeight)以及特定层级的节点数(TreeLeveLK)。

  • 层序遍历的实现

    除了深度优先遍历,层序遍历(LevelOrder)也是一种重要的遍历方式。它按照节点所在的层级依次访问,这在某些特定的应用场景下非常有用,例如在构建搜索算法或执行宽度优先搜索时。

代码目录

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. #include <math.h>
  6. typedef int BTDataType;
  7. typedef struct BinaryTreeNode
  8. {
  9. BTDataType data;
  10. struct BinaryTreeNode* left;
  11. struct BinaryTreeNode* right;
  12. }TreeNode;
  13. TreeNode* BuyTreeNode(int x);
  14. TreeNode* CreateNode();
  15. void PrevOrder(TreeNode* root);//前序遍历 --深度优先遍历 dfs
  16. void InOrder(TreeNode* root);
  17. void PostOrder(TreeNode* root);
  18. int TreeSize(TreeNode* root);
  19. int TreeLeafSize(TreeNode* root);//叶子节点个数
  20. int TreeHeight(TreeNode* root);//高度
  21. int TreeLeveLK(TreeNode* root, int k);//第k层节点个数
  22. TreeNode* TreeCreate(char* a, int* pi);//构建二叉树
  23. void DestoryTree(TreeNode** root);//销毁二叉树
  24. void LevelOrder(TreeNode* root);//层序遍历 --广度优先遍历bfs

1.二叉树的基本概念和结构 

在深入了解二叉树之前,我们必须首先理解它的基本构成。二叉树是一种非常重要的数据结构,广泛应用于编程和算法设计中。它是一个有序树,每个节点最多有两个子节点,通常被称为左子节点和右子节点。

结构体表示二叉树

在我的代码中,二叉树通过结构体BinaryTreeNode表示。这个结构体定义了树的基本单元——节点。每个节点包含三个部分:数据部分和两个指针。

  1. typedef struct BinaryTreeNode {
  2. BTDataType data; // 节点存储的数据
  3. struct BinaryTreeNode* left; // 指向左子节点的指针
  4. struct BinaryTreeNode* right; // 指向右子节点的指针
  5. } TreeNode;

这种结构体的设计允许二叉树以递归的方式定义:每个节点本身可以被视为一个树的根,具有自己的子树。二叉树的这种特性是其许多算法操作的基础,包括遍历、搜索和修改。

数据与节点关系

在这个结构体中,data字段存储了节点的值。这个值可以是任意类型,在我的示例中,它被定义为BTDataType(在这里是int类型)。每个节点的leftright指针分别指向它的左子节点和右子节点。如果某个节点不存在左子节点或右子节点,相应的指针将为NULL

这种结构使得操作和遍历二叉树变得可能,允许我们实现诸如插入、删除、查找等复杂操作,同时也为高效的算法实现提供了基础。

在后续部分,我们将探索如何使用这种结构体来创建和管理二叉树

 2.创建和销毁二叉树

在操作二叉树时,正确地管理内存是至关重要的。这涉及到两个基本操作:创建二叉树和销毁二叉树。在您的代码中,这两个过程通过BuyTreeNodeCreateNodeDestoryTree函数实现。

创建二叉树

  1. 分配节点内存: BuyTreeNode函数用于创建一个新的树节点。它接受一个数据值,分配足够的内存来存储一个新的TreeNode结构体,并将传入的数据值赋给新节点 

  1. TreeNode* BuyTreeNode(int x) {
  2. TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
  3. assert(node); // 确保内存分配成功
  4. node->data = x;
  5. node->left = NULL;
  6. node->right = NULL;
  7. return node;
  8. }

构建二叉树(1):

  1. TreeNode* TreeCreate(char* a, int* pi)
  2. {
  3. if (a[*pi] == '#')
  4. return NULL;
  5. TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
  6. if (root == NULL)
  7. {
  8. perror("malloc fail");
  9. exit(-1);
  10. }
  11. root->data = a[(*pi)++];
  12. root->left = TreeCreate(a, pi);
  13. root->right = TreeCreate(a, pi);
  14. return root;
  15. }

过程步骤

  1. 检查终止条件: 函数首先检查当前位置的字符是否为'#'。在这个上下文中,'#'代表一个空位置,意味着在这里不需要创建节点。如果是'#',函数返回NULL,这表明当前没有节点被创建,相当于告诉递归调用的上一层,这里是一个空分支。

  2. 创建新节点: 如果当前位置的字符不是'#',函数会继续创建一个新的树节点。它分配内存空间给新节点,并检查内存分配是否成功。如果分配失败,函数会报错并退出程序。

  3. 设置节点数据: 新节点的数据设置为当前字符数组位置的值。然后,指针pi递增,以便下一次调用时读取下一个字符。

  4. 递归构建子树: 接下来,函数递归地调用自身两次:一次用于构建左子树,一次用于构建右子树。这两个递归调用分别处理字符数组中接下来的部分,因此逐渐构建出整个树的结构。

  5. 返回树的根节点: 一旦左右子树都被创建,函数返回当前创建的节点,这个节点现在是一个完整子树的根节点。

说明

通过这种方式,TreeCreate函数能够从一个序列化的表示(在这里是一个字符数组)中逐步重建出原始的二叉树结构。这种序列化表示通常包含特殊的字符(如'#')来标示空节点,从而允许树的形状在数组中得以完整表达。

这个函数的递归性质使得它能够处理任意复杂的树结构,只要输入的字符数组正确地表示了树的结构。这种方法在二叉树的序列化和反序列化中非常常见,是处理树结构数据的一种强大技巧。

 构建二叉树(2) CreateNode函数展示了如何将这些独立的节点组合成一个完整的二叉树结构。这个函数硬编码了节点的创建和连接方式,构造了一个特定的二叉树。

  1. TreeNode* CreateNode() {
  2. TreeNode* node1 = BuyTreeNode(1);
  3. TreeNode* node2 = BuyTreeNode(2);
  4. ...
  5. node1->left = node2;
  6. node1->right = node4;
  7. ...
  8. return node1;
  9. }

销毁二叉树

内存管理的另一方面是当二叉树不再需要时,正确地释放其占用的资源。这是通过DestoryTree函数实现的。

  1. 递归销毁: DestoryTree采用递归方式访问每个节点,并释放其占用的内存。递归是处理树结构的一种自然和强大的方法。

  1. void DestoryTree(TreeNode** root) {
  2. if (*root == NULL)
  3. return;
  4. DestoryTree(&(*root)->left);
  5. DestoryTree(&(*root)->right);
  6. free(*root);
  7. *root = NULL;
  8. }

 这种方法确保了所有节点都被适当地访问和释放,从而防止了内存泄漏——一种在长时间运行的程序中特别重要的考虑因素。

通过这些函数的实现,我们不仅构建了一个基本的二叉树,还学会了如何负责任地管理与之相关的内存。下一步,我们将探讨如何遍历二叉树,并了解它的其他重要属性

3.二叉树的其他属性

除了遍历,我们还探讨了如何使用代码来确定二叉树的大小(TreeSize)、叶子节点的数量(TreeLeafSize)、树的高度(TreeHeight)以及特定层级的节点数(TreeLeveLK)在理解了二叉树的基本结构和如何创建及销毁它之后,我们接下来会探索二叉树的几个其他重要属性:树的大小、叶子节点的数量、树的高度,以及特定层级的节点数。这些属性在二叉树的应用和分析中扮演着关键角色。

1. 二叉树的大小(TreeSize)

二叉树的大小是指树中节点的总数。这可以通过递归地计算每个节点的左右子树来确定。

  1. int TreeSize(TreeNode* root) {
  2. if (root == NULL) {
  3. return 0;
  4. }
  5. return 1 + TreeSize(root->left) + TreeSize(root->right);
  6. }

在这个函数中,如果当前节点为NULL,表示子树不存在,因此返回0。否则,计算大小时,将当前节点(1)加上左子树和右子树的大小。 

2. 叶子节点的数量(TreeLeafSize)

叶子节点是指没有子节点的节点。计算二叉树中叶子节点的数量有助于理解树的分布和深度。

  1. int TreeLeafSize(TreeNode* root) {
  2. if (root == NULL) {
  3. return 0;
  4. }
  5. if (root->left == NULL && root->right == NULL) {
  6. return 1;
  7. }
  8. return TreeLeafSize(root->left) + TreeLeafSize(root->right);
  9. }

 当遇到叶子节点时(即左右子节点均为NULL),返回1。否则,递归地计算左右子树中的叶子节点数量。

3. 树的高度(TreeHeight)

树的高度是从根到最远叶子节点的最长路径上的节点数。这是衡量树平衡和深度的重要指标。

  1. int TreeHeight(TreeNode* root) {
  2. if (root == NULL) {
  3. return 0;
  4. }
  5. return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
  6. }

 在这个函数中,如果节点为NULL,表示到达了树的底部,返回0。否则,高度是左右子树高度的最大值加1(当前节点)。

4. 特定层级的节点数(TreeLeveLK)

计算特定层级的节点数有助于理解树在不同深度的分布。

  1. int TreeLeveLK(TreeNode* root, int k) {
  2. if (root == NULL || k < 1) {
  3. return 0;
  4. }
  5. if (k == 1) {
  6. return 1;
  7. }
  8. return TreeLeveLK(root->left, k - 1) + TreeLeveLK(root->right, k - 1);
  9. }

当到达目标层级(k == 1)时,返回1。如果不是目标层级,递归地计算左右子树在k-1层级的节点数。

通过这些函数,我们不仅能够构建和管理二叉树,还能深入了解树的结构和特性。这些属性对于优化算法、分析数据结构性能等方面都至关重要。接下来,我们将研究二叉树的遍历方法,这是理解和操作二叉树的关键一环。

1.二叉树的遍历

前序、中序以及后序遍历
学习二叉树结构,最简单的方式就是遍历。所谓 二叉树遍历 (Traversal) 是按照某种特定的规则,依次对二叉 树中的节点进行相应的操作,并且每个节点只操作一次 。访问结点所做的操作依赖于具体的应用问题。 遍历   是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础

按照规则,二叉树的遍历有: 前序 / 中序 / 后序的递归结构遍历
1. 前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历 (Inorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之中(间)。
3. 后序遍历 (Postorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根, 所以 N(Node )、 L(Left subtree )和 R(Right subtree )又可解释为
根、根的左子树和根的右子树 NLR LNR LRN 分别又称为先根遍历、中根遍历和后根遍历。

 

  1. void PrevOrder(TreeNode* root)
  2. {
  3. if (root == NULL)
  4. {
  5. printf("N ");
  6. return;
  7. }
  8. printf("%d ", root->data);
  9. PrevOrder(root->left);
  10. PrevOrder(root->right);
  11. }
  12. void InOrder(TreeNode* root)
  13. {
  14. if (root == NULL)
  15. {
  16. printf("N ");
  17. return;
  18. }
  19. InOrder(root->left);
  20. printf("%d ", root->data);
  21. InOrder(root->right);
  22. }
  23. void PostOrder(TreeNode* root)
  24. {
  25. if (root == NULL)
  26. {
  27. printf("N ");
  28. return;
  29. }
  30. PostOrder(root->left);
  31. PostOrder(root->right);
  32. printf("%d ", root->data);
  33. }

 2. 层序遍历

层序遍历 :除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1 ,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第 2 层 上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

 层序遍历  --广度优先遍历bfs 比如扫雷和基本搜索算法中就是以广度优先算法为基底

  1. void LevelOrder(TreeNode* root)
  2. {
  3. Queue q;
  4. QueueInit(&q);
  5. if (root)
  6. QueuePush(&q, root);
  7. int LevelSize = 1;
  8. while (!QueueEmpty(&q))
  9. {
  10. while (LevelSize--)//这里稍作变形,很多面试常考 控制层序遍历每一层每一层的输出
  11. {
  12. TreeNode* front = QueueFront(&q);
  13. QueuePop(&q);
  14. printf("%d ", front->data);
  15. if (front->left)
  16. QueuePush(&q, front->left);
  17. if (front->right)
  18. QueuePush(&q, front->right);
  19. }
  20. printf("\n");
  21. LevelSize = QueueSize(&q);
  22. }
  23. printf("\n");
  24. QueueDestory(&q);
  25. }

层序遍历是一种特殊的遍历方式,它按照树的层级,从上到下、从左到右的顺序访问每个节点。在我的函数中,这是通过使用一个队列实现的,队列是一种先进先出(FIFO)的数据结构。

过程步骤

  1. 初始化队列: 首先,创建一个空队列,用于存储将要访问的树节点。

  2. 根节点入队: 如果二叉树不为空,把根节点放入队列。这是遍历的起始点。

  3. 遍历队列中的节点: 接下来的步骤是循环进行的,直到队列为空。在每一次循环中,执行以下操作:

    • 处理当前层级的节点: 对于队列中的每个节点,执行以下子步骤:

      • 从队列中取出一个节点。
      • 访问该节点(比如,打印节点数据)。
      • 如果这个节点有左子节点,将左子节点加入队列。
      • 如果这个节点有右子节点,将右子节点加入队列。
    • 这个过程将会持续,直到队列为空。每处理完一层的所有节点,就开始处理下一层。

  4. 层与层之间的分隔: 在我的函数中,每处理完一层节点后,打印一个换行符,这样可以在输出中清楚地区分不同的层级。

  5. 销毁队列: 最后,当所有的节点都被访问过后,队列将会变空,遍历结束。此时,销毁或清空队列来释放资源。

通过这个过程,我的函数能够按层次顺序访问二叉树中的每个节点。这种遍历方式在很多场景中非常有用,例如在树的宽度优先搜索(Breadth-First Search, BFS)中。

结语

通过本文,我们不仅了解了二叉树的基本理论知识,还学习了如何在C语言中实现和操作这种数据结构。无论是对于初学者还是有经验的程序员来说,掌握这些知识都是非常有价值的。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小桥流水78/article/detail/767190
推荐阅读
相关标签
  

闽ICP备14008679号