【C语言】数据结构-链式二叉树，详解分治递归和层序遍历_层序遍历二叉树递归

前言

在之前关于树的学习中，我们接触了二叉树的知识点，以及堆和堆排序的操作。

两个知识点都是超链接，可以点击查看我之前的博客，复习一下这两个知识点哦！

接下来我们要更进一步，学习一下链式二叉树的操作

本篇博客将以知识点讲解+OJ题目验证的方式来展开链式二叉树的内容

---

1.链式二叉树的基本结构

在学习链式二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。

之前我们提到过，树最优的表示方法是父母孩子表示法。但是对于二叉树这种度固定的树来说，可以 直接使用最简单的方法，定义两个指针指向它的左右叶子节点即可

typedef int BTDataType;

typedef struct BTreeNode
{
	BTDataType data;
	struct BTreeNode* left;
	struct BTreeNode* right;
}BTNode;
1
2
3
4
5
6
7
8

这里要说明的一件事是：普通树的“增删查改”操作是没有意义的，因为树并不是一个最优的储存结构。所以我们学习链式二叉树的操作时，更多学习的是分治 递归思想

---

2.分治递归思想

什么是分治思想？

举个例子，学校里面需要进行排查，找出本校里面身高最高的人。这时候校长可以去找各个年级的级组长，然后级组长去找各个班主任，班主任让班级里面的小组长统计组员身高数据。

这时候的小组长已经可以返回一个身高最高的值给班主任了，然后再层层上报，校长只需要在最后上报的4个数据中找出一个最高的，即为本校最高的同学

分治策略的思想就是分而治之，即先将一个规模较大的大问题分解成若干个规模较小的小问题，再对这些小问题进行解决，得到的解，在将其组合起来得到最终的解。在上面的例子中，较小的问题就是小组长统计组员身高，并上报。转换成代码语言就是return一个值

更详细的解释可以参考这篇大佬的博客

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/952579?site