c语言数据结构顺序表的代码,c语言数据结构用什么软件
第一篇前言。链式二叉树的基本结构2。分治递归思想3。前/中/后顺序遍历3.1通过递归遍历计算节点数3.2用后继遍历的思想破坏树3.3前/中/后顺序遍历OJ问题4。计算节点数4.1叶节点数4.2二叉树第k层节点数4.3求二叉树的深度OJ问题5。在树6中找到值为X的节点。序列遍历6.1判断二叉树是否是完全二叉树结论前言在前面对树的学习中，我们接触了二叉树的知识点以及堆的操作和堆排序。
两个知识点都是超链接。可以点击查看我之前的博客，复习这两个知识点！
接下来，我们将更进一步，学习链式二叉树的运算。
本博客将通过知识点讲解OJ题目验证，扩展链式二叉树的内容。
1.链式二叉树的基本结构在学习链式二叉树的基本运算之前，需要先创建一棵二叉树，然后才能学习其相关的基本运算。
正如我们之前提到的，树的最佳表示是父子表示。但是对于一个固定度的树，比如二叉树，你可以用最简单的方式直接定义两个指针指向它的左右叶节点。
typedef int BTDataType
typedef struct BTreeNode
{
BTDataType数据；
struct BTreeNode * left
struct BTreeNode * right
} BTNode这里要说明一点，普通树的“增、删、检、改”操作是没有意义的，因为树并不是一个最优的存储结构。所以当我们研究链式二叉树的运算时，我们更多地了解了分治递归。
2.分治递归思想什么是分治思想？
比如学校需要筛选，找出学校最高的人。这时候校长可以去找各年级的班长，然后班长去找班主任，班主任让班长统计小组成员的身高数据。
这时候小组长已经可以把最高的值返回给班主任，然后层层上报。校长只需要找到最后上报的四个数据中最高的一个，也就是全校最高的同学。
分而治之的思想就是分而治之，即先把一个大规模的问题分解成几个小规模的问题，然后对这些小规模的问题进行求解，将得到的解组合起来得到最终的解。上例中，较小的问题是组长统计队员身高并上报。转换成代码语言是一种价值回报。
更详细的解释，请参考大佬们的这个博客？
——递归和分治策略的五种常见算法策略
早期学习递归求斐波那契数用的是分而治之的思想？入口
int fo2(int a)
{
if ((a==1) (a==2))
返回1；
其他
返回(fo2(a-1))(fo2(a-2))；//n-1和n-2项
}当a=1或2时，为分而治之的结束节点，递归以return 1终止。
3.在理解了上述分治递归思想后，我们将学习链式二叉树的三种遍历方式。
前序遍历：根节点-左子树-右子树中序遍历：左子树-根节点-右子树逆序遍历：左子树-右子树-根节点从前序遍历开始。我们来实践一下分而治之的思想：用递归按照前序遍历的顺序打印出树中节点的值。
假设我们现在创建一个简单的二叉树，就像这样？你能弄清楚序言遍历的打印顺序应该是什么吗？
答案是1 2 3 4 5 6
看到这里，你一定一脸懵：啊，怎么出来的？
别担心，我们现在将它们的end subtree NULL添加到打印的内容中，因此前导遍历的结果是：
1 3 Null Null Null 4 5 Null Null 6 Null Null没有悬念，就开始分析这个遍历结果是怎么出来的吧！
如前所述，前序遍历的顺序是：根节点-左子树-右子树。
下图可以让你更直观的看到这三种遍历方式的区别。
其中前序遍历被转换成如下的代码语言
//二叉树的前序遍历
void btreeprevord(Bt node * root)
{
if (root==NULL)
{//为了便于理解，也把空节点打印出来。
printf( NULL )；
返回；
}
printf(%d ，root-data)；
BTreePrevOrder(根-左)；
BTreePrevOrder(root-right)；
}在这个过程中，当根节点为NULL时，就是分而治之的结束，递归停止。
恐怕还不清楚。为了彻底说清楚，我们得画一个递归示意图来求解。
图中一个字打错了，看到一半才发现.请忽略！
如果你能理解上图中前序遍历的思路，那么中序遍历和后序遍历的操作就很简单了！猜猜怎么修改前导码？
没错，就是把printf的位置改了！
//二叉树中的顺序遍历
void BTreeInOrder(BTNode* root)
{
if (root==NULL){
printf( NULL )；
返回；
}
BTreeInOrder(根左)；
printf(%d ，root-data)；
BTreeInOrder(根右)；
}
//按逆序遍历二叉树
void BTreePostOrder(BTNode* root)
{
if (root==NULL){
printf( NULL )；
返回；
}
BTreePostOrder(根-左)；
BTreePostOrder(根-右)；
printf(%d ，root-data)；
}最后打印出来的结果分别如下，完全对应上面的示意图！返回原理图
3.1通过递归遍历上面的递归来计算节点数，我们打印出每个节点的值。
我们只需要对其中一个递归代码做一个小的修改，把printf改成count，这样就可以把它从遍历改成计算一棵二叉树的节点数了。
在这里，我选择指针变量，这样主函数就可以得到计数结果。
//二叉树中的节点数
void BTreeSize(BTNode* root，int* pcount)
{
if (root==NULL)
返回；
(* pcount)；//指针变量，可以在主函数中调用
BTreeSize(左根，pcount)；
BTreeSize(root- right，pcount)；
}
可以用全局静态变量来计数，但是那种计数会在下一次调用中叠加，调用后放0很不方便。
当然，我贴的方法也不是最优的，因为它需要额外创建一个变量count来作为参数调用，而不是直接返回节点数。
所以有下面这个用三只眼的算子？递归地分而治之，计算节点数。
如果根节点为空，则为结束案例；否则，左子树和右子树的节点大小为1(节点本身)。//高级方法
int BTreeSize(BTNode* root) {
return root==NULL？0 :
BTreeSize(根左)
BTreeSize(根右)1；
}3.2用后续遍历的思想破坏树。当我们不需要使用二叉树的时候，我们需要释放它调用的内存。
问题是，如果释放根节点，如何找到它的左右子树？
所以我们在释放的时候要用遍历的顺序来释放，就是先破坏左右子树，再向上破坏。这样可以避免找不到子树的问题。
//二叉树销毁
void BTreeDestory(BTNode** root)
{
if (*root==NULL)
返回；
//通过后续遍历的思想破坏树
BTreeDestory((* root)-left)；
BTreeDestory((* root)-right)；
免费(* root)；
* root=NULL//可以使用二级指针直接在函数中设置根节点的指针。
}3.3按照前/中/后的顺序遍历OJ问题
三个Leetcode OJ问题
44.二叉树145的一阶遍历。二叉树的二阶遍历94。二叉树的中序遍历
在这里，我只说明前序遍历这个话题，因为后两者的思路是完全一样的，只需要做一点代码上的改动。
给定一棵树，你需要按照前面序列的顺序遍历它，将每个节点的值保存在一个数组中并返回它。
这里的输入用例是“伪代码”，[1，null，2，3]表示1的左子树为NULL，右子树为2；2的左子树为3，右子树为空。
既然要用数组来存储，首先要知道这个二叉树有多少个节点，这样才能方便的打开数组。
注意：这种接口题目，数组必须用动态内存函数malloc开发。
然后改变preorder遍历中的printf把值放到arr数组中！
//二叉树中的节点数
void BTreeSize(struct TreeNode * root，int* pcount)
{
if (root==NULL)
返回；
(* pcount)；
BTreeSize(左根，pcount)；
BTreeSize(root- right，pcount)；
}
//前导遍历代码
void btreeprevord(struct TreeNode * root，int*arr，int* i)
{
if (root==NULL){
返回；
}
arr[(* I)]=root-val；
//因为在递归调用中需要多次调用不同的I，所以需要获取地址
BTreePrevOrder(root- left，arr，I)；
BTreePrevOrder(root- right，arr，I)；
}
int * preorderstraversal(struct TreeNode * root，int* returnSize){
int count=0；
BTreeSize(根，计数)；//计算树节点的数量
int * arr=(int *)malloc(sizeof(int)* count)；//打开数组
int I=0；//下标
BTreePrevOrder(root，arr，I)；
* returnSize=count
返回arr
}
4.计算节点数计算二叉树中节点数的方法已在3.1中描述。下面是对节点数量的更详细的计算。
4.1叶节点的数量众所周知。在这个二叉树中，只有3、5和6是叶节点。
判断一个节点是不是叶节点其实很简单：只要它的左右子树都是空的，就是叶节点。
以此作为分而治之的结束条件。只要满足这个条件，就会返回1。如果它遍历了空节点，它将返回0。在其他情况下，它将返回左子树和右子树的叶节点数之和。//二叉树的叶节点数。
int BTreeLeafSize(BTNode* root)
{
if (root==NULL)
返回0；
if(左根==NULL右根==NULL)
返回1；
返回BTreeLeafSize(根左)BTreeLeafSize(根右)；
}4.2二叉树第k层的节点数。假设根节点是第一层。如果想知道第k层有多少个节点，如何设计函数？
先这么想：3所在的层对于根来说是第三层，但对于2来说是第二层，对于3本身来说是第一层。
那么，我们可以让k层向下到-1进行递归吗？
//二叉树第k层的节点数
int BTreeLevelKSize(BTNode* root，int k)
{
断言(k=1)；//保证k=1
if (root==NULL)
返回0；
如果(k==1)
返回1；
返回BTreeLevelKSize(左根，k - 1)
BTreeLevelKSize(根右，k-1)；
}
4.3二叉树的深度在前面对树的概念研究中，我们解释了树的深度(即一棵树有多少层)。
深度和前面校长身高统计的例子差不多。我们需要找到左边和右边子树中更深的一个并返回它。结束条件是当节点为空时，return 0终止递归。
//二叉树深度，即有多少层？
int BTreeDepth(BTNode* root)
{
if (root==NULL)
返回0；
int left=BTreeDepth(root-left)；
int right=BTreeDepth(root-right)；
向左向右返回？左1:右1；
}注意：这里的左1和右1是用来计算上层节点本身的。
求二叉树的深度oj问题leetcode上有一个OJ问题就是求二叉树的最大深度。复制代码，改名字就搞定了！
标题链接：104。二叉树的最大深度
5.在树中找到值为X的节点。在二叉树中寻找一个值。基本思想是遍历它，判断根节点和左右子树中是否有值为X的节点。
具体分析，写以下代码注释！
//二叉树查找值为x的节点。
BTNode* BTreeFind(BTNode* root，BTDataType x)
{
if (root==NULL)
返回NULL//如果节点为空，则将其作为空返回。
if (root- data==x)
返回根目录；//节点本身是X，返回节点自己的地址
BTNode* ret1=BTreeFind(根左，x)；
如果(ret1！=NULL)//如果在左边找到，返回左边节点的地址。
返回ret1
BTNode* ret2=BTreeFind(根右，x)；
如果(ret2！=NULL)//如果找到右侧，则返回右侧节点的地址
返回ret2
返回NULL//两者都找不到，也不是它本身。返回null
}6.顾名思义，序列遍历就是一层一层的遍历。
例如上面的树，序列遍历的结果如下
1 4 3 null 5 6实现序列遍历，需要用到堆栈中的队列和之前学过的队列知识？入口
在VS项目中，导入预写队列的头文件和源文件，然后引用！
这里可以体现出之前typedef类型的作用：你只需要改变第一个数据类型，剩下的就可以搞定了！
在引用头文件的时候，因为需要用到栈代码中二叉树的定义，所以需要先引用二叉树的头文件，再引用队列的头文件。
做完这些之后，我们来谈谈序列遍历的思想
首先插入根节点，然后在根节点不在队列中时插入其左右子树的节点。
当队列中的所有值都为空时，序列遍历完成。
所以我们需要排队的不是节点的值，因为那样我们就找不到节点的左右子树了。队列是节点的地址！
//序列遍历
void btreelevelord(Bt node * root)
{
队列q；
queue init(q)；
如果(根！=NULL){//根节点不为空，开始排队。
QueuePush( q，root)；
}
而(！QueueEmpty( q))
{
Bt node * head=queue front(q)；//获取队列头数据
queue pop(q)；//出列
printf(%d ，head-data)；
如果(头-左！=空)
{
QueuePush( q，头向左)；
}
如果(头-对！=空)
{
QueuePush( q，头右)；
}
//序列遍历不需要递归，可以通过循环来解决问题。
}
printf( \ n )；
QueueDestory(q)；//防止内存泄漏
返回；
}遍历的结果如下
6.1判断一棵二叉树是否是完全二叉树。学会了序列遍历，就可以判断一棵二叉树是不是完全二叉树了！
完全二叉树：第k-1层是完全二叉树，最后一层不满足，但从左到右分布。
具体想法是
当队列头为空时，遍历开始。如果所有队列都为空，则表示二叉树已满。如果有非空节点，则不是满二叉树。//判断二叉树是否是完全二叉树。
bool BTreeComplete(BTNode* root)
{
队列q；
queue init(q)；
如果(根！=NULL) {
QueuePush( q，root)；
}
而(！QueueEmpty( q))
{
Bt node * head=queue front(q)；//获取队列头数据
queue pop(q)；//出列
if (head==NULL){
打破；//遇到队列中空节点，退出循环。
}
QueuePush( q，头向左)；
QueuePush( q，头右)；
}
而(！QueueEmpty( q))
{
Bt node * head=queue front(q)；//获取队列头数据
queue pop(q)；//出列
如果(头！=空)
{
//printf(不是完整的二叉树\ n )；
返回false
}
}
QueueDestory(q)；//防止内存泄漏
返回true
}结论链式二叉树的内容到这里就结束了！
如果博客中有不清楚的地方，请在评论区提出来！
下一篇博客会讲解一些关于二叉树的OJ题和概念性选择题！~我们后会有期~
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。