网站权重对优化的作用,网站开发去哪学,长沙网站快速排名提升,做护肤的网站有哪些#x1f4d9;作者简介#xff1a; 清水加冰#xff0c;目前大二在读#xff0c;正在学习C/C、Python、操作系统、数据库等。 #x1f4d8;相关专栏#xff1a;C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 #x1f44d… 作者简介 清水加冰目前大二在读正在学习C/C、Python、操作系统、数据库等。 相关专栏C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 收藏 ⭐留言 如有错误还望各路大佬指正 ✨每一次努力都是一种收获每一次坚持都是一种成长✨ 目录 前言
1. 二叉树的链式结构 1.1链式二叉树的结构
2. 二叉树初阶训练 2.1 二叉树节点个数 2.2 叶子节点个数 2.3 第k层节点个数
总结 前言 前边我主要介绍了二叉树的顺序结构链式结构也只是简单提及今天我们来详细介绍一下二叉树的链式结构。 1. 二叉树的链式结构 二叉树的顺序结构是通过顺序表来存储二叉树的数据那么链式结构就是通过链表连接二叉树的各个节点进而来实现二叉树的树形结构。链式二叉树存储不需要像堆那要必须是完全二叉树它可以是一颗普通二叉树。 1.1链式二叉树的结构 二叉树的链式结构是指使用节点之间的指针连接来表示二叉树的结构。在链式结构中每个节点都包含一个数据元素和指向其左子节点和右子节点的指针。一个二叉树的节点通常由两个部分组成数据域和指针域。
typedef struct BinaryTree
{int data;//数据域struct BinaryTree* left;//指针域struct BinaryTree* right;//指针域
}BTNode; 通过这种链式结构我们可以方便地遍历和操作二叉树。最常见的遍历方法就是使用递归遍历二叉树。前边我们也简单介绍了二叉树的前序、中序、后续遍历。也很简单但是在实际中并不会这么直白的让你递归遍历二叉树都是遍历的变形。
2. 二叉树初阶训练 2.1 二叉树节点个数 如何计算一个二叉树的节点个数呢 链式结构的树使用递归来遍历最简单也是最常用的遍历方法。这样写吗
int TreeSize(BTNode* root)
{int size 0;if (root NULL)return 0;elsesize;TreeSize(root-left);TreeSize(root-right);return size;
} 节点是NULL就返回0不为空就size。看似没有问题但深入思考一下就会发现端倪每次递归都会重新创建一个size然后每次的size都加到了一个size上吗其实并没有size出了函数作用域就会销毁递归到叶子节点返回后前边的size就会被销毁。 只要解决size作用域问题是不是就可以解决了增加size的生命周期有两种方法一个是使用全局变量另一个是使用static修饰。这样虽然可以计算出二叉树的节点个数但这样也存在缺点这个函数的使用就会变成一次性的如果在一个程序中多次调用数据就会累计如第一次是5第二次就是10……也有解决的办法就是每次使用前将size置为0。但这都不是这个问题的最优解最优解就是使用递归解决。 递归的核心就是分治将一个复杂的过程分解成一个一个的类似子问题。要计算一颗二叉树的节点个数就只需要计算左子树节点个数右子树节点个数1。左子树又可以分为左子树右子树直到叶子节点叶子节点的左右子树为NULL所以遇到NULL就返回0那我们就可以这样写
int TreeSize(BTNode* root)
{if (root NULL)return 0;return TreeSize(root-left) TreeSize(root-right) 1;
} 如下图 虚线代表的递归返回返回节点的个数。这里也仅仅是一个简单的递归有了这个题目的思路我们来进阶一下。 2.2 叶子节点个数 计算叶子节点个数也是使用递归对这个问题进行分治计算一棵树的叶子节点个数也就是左子树和右子树中叶子节点的个数子树又可以再分为左子树、右子树。遇到叶子节点就停止。使用递归可以大幅的减少代码的复杂度。现在就只需考虑一下递归停止的条件。叶子节点的左子树与右子树都为空所有当根的左右子树都为NULL时就可以判定为叶子节点。
int BinaryTreeLeafSize(BTNode* root)
{if (rootNULL){return 0;}if (root-left NULL root-right NULL){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
} 例如这棵树有三个叶子节点 当前节点为NULL就不是叶子节点返回0如果左右子树都为NULL则该节点就是叶子节点返回1最后将左子树和右子树的叶子节点个数相加最终返回值就是叶子节点的个数。 2.3 第k层节点个数 在前两个的基础上我们再来一个变形计算第k层节点个数。这道题目不像前两个那要它需要有控制一下递归的深度。
int BinaryTreeLevelKSize(BTNode* root, int k) 传入一个k和根节点通过k来控制递归的深度。这里我们默认根节点的高度是1。如果遇到NULL就返回0
int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k 0);if (root NULL){return 0;}if (k 1){return 1;}return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}
例如这棵树 假设我们要计算第3层节点个数。第一次调用从根开始k此时等于3然后开始向下递归第二次调用传参是k-1到第二层时k2到第三层时k1。这里我们需要注意一下两个判断返回的顺序要先判断当前节点是否为NULL不为NULL才开始判断k是否为1。 总结 本篇文章主要简单介绍了一下二叉树的链式结构以及链式结构遍历的特点通过一些简单的练习帮助大家更快上手二叉树的链式递归。理解并使用好递归的分治对于后续的学习至关重要希望这篇文章可以帮到您。最后感谢阅读
