云南网站建设网络产品服务的提供者不得设置

当前位置： 首页 > news >正文

云南网站建设,网络产品服务的提供者不得设置,wordpress数据库改密码忘记,做婚礼效果图的网站有哪些【(C语言)数据结构奋斗100天】二叉树#xff08;上#xff09; #x1f3e0;个人主页#xff1a;泡泡牛奶 #x1f335;系列专栏#xff1a;数据结构奋斗100天 本期所介绍的是二叉树#xff0c;那么什么是二叉树呢#xff1f;在知道答案之前#xff0c;请大家思考一下…【(C语言)数据结构奋斗100天】二叉树上 个人主页泡泡牛奶 系列专栏数据结构奋斗100天 本期所介绍的是二叉树那么什么是二叉树呢在知道答案之前请大家思考一下下列问题 什么是二叉树的根节点什么是二叉树的左子树和右子树什么是二叉树的父节点和子节点二叉树的遍历有哪些方法 让我们带着这些问题开始今天的学习吧( •̀ ω •́ )✧ 一、树和二叉树

1. 什么是树 树是一种非线性的数据结构是n0个节点的有限集合。当n0时称为空树。在任意一颗非空树中我们可以看到节点的排列就像一颗倒着的树根朝上叶子朝下 在现实生活中有哪些像上面根朝上叶子朝下的树型结构呢 例如一个家族里组成的 “家谱” 就是一颗树。 再例如一个阶级关系就是一颗 “树”。 除开人与人的关系还有很多抽象的东西也可以成为一颗 “树”如一本书的目录如操作系统的文件系统。 以上的共同点都是由一个 “根” 衍生出许多的 “枝干”再从每一个 “枝干” 衍生出更多的 “叶子”。 在数据结构中我们对树有以下称呼 父节点/双亲节点某节点的上一个节点为父节点例如C是F的父节点(孩)子节点某一节点指向的下一个节点为子节点例如F是C的子节点兄弟节点父节点相同的节点互为兄弟节点例如D、E堂兄弟节点双亲在同一层的节点互为堂兄弟例如D、F互为堂兄弟节点节点的度一个节点含有的子树的个数称为该节点的度例如B的度为2C的度为1叶子节点度为0或者无子节点的称为叶子节点例如G、E、F树的度一颗树中的最大的节点的度例如上图树的度为2节点的层次根节点为第一层 依次类推树的高度/深度树节点的最大层次如上图树的高度为4节点的祖先根节点到此节点的经过的所有节点都为祖先例如A是所有节点的祖孙子孙只要在关系在某一节点的下面都为子孙森林有m 0的树所组成的集合称为森林 小结 树的关系可以由现实生活中的亲戚关系来表示 2. 什么是二叉树 什么是 n叉树 n叉树故名思意就是树的分叉最多可以有n个。 那么二叉树就是最多有2个孩子节点的树。如下图所示。 二叉树节点的两个孩子一个被称为左孩子一个被称为右孩子。这两个孩子的顺序是固定的。
2. 二叉树的类型 单二叉树的类型来说其实有很多种普通二叉树、满二叉树、完全二叉树、搜索二叉树、AVL树、红黑树……而今天我们的主题就是满二叉树和完全二叉树。 一颗二叉树的所有非叶子节点都存在左右孩子并且所有叶子节点都在同一层级上那么这就是满二叉树如下图。 满二叉树的总节点数为Sn2n−1S_n 2^{n}-1Sn​2n−1 n为层数 对一个有n个节点的二叉树按层级需要编号则所有节点编号从1到n。如果这颗树的所有节点和同样深度的满二叉树的编号为1到n的节点位置相同则这个二叉树为完全二叉树。如下图。简单来说最后一层连续排布但不满就是完全二叉树 4. 二叉树的规律性质 这是一个公比为2的等比数列首项为1。即 a11a_11a1​1公比 q2q2q2。第n层节点的数量为 2n−12^{n-1}2n−1前n层节点的数量总和为 Sn2n−1S_n2^n-1Sn​2n−1。对于任意一棵二叉树满足 nn0n1n2nn_0n_1n_2nn0​n1​n2​其中 nnn 为节点总数n0n_0n0​ 表示度数为0的节点个数n1n_1n1​ 表示度数为1的节点个数n2n_2n2​ 表示度数为2的节点个数。存在 n2n0−1n_2n_0-1n2​n0​−1 的关系。计算层数 nnn 的公式为 nlog⁡2(N1)n\log_2(N1)nlog2​(N1)其中 NNN 为节点总数。 上面这些规律往往会在刷题中使用到 二、二叉树的存储结构 链式结构和顺序结构是二叉树的两种常见存储方式。
3. 顺序结构 顺序存储结构使用数组作为基础存储单元它适用于表示完全二叉树。除了堆其他情况使用数组存储会则会造成大量空间浪费。顺序存储结构的二叉树在物理结构上是一个数组逻辑结构上是一棵二叉树。 用数组来存储我们通常会通过下标来访问元素观察节点规律我们不难发现 若父节点为 father子节点为 child则满足 fatherchild−12father \frac{child - 1}{2}father2child−1​ 若左右子节点分别为 left 和 right并且左右孩子都存在即 left,right≥nleft, right \ge nleft,right≥n则满足 leftfather∗21left father * 2 1leftfather∗21 rightfather∗22right father * 2 2rightfather∗22
   
4. 链式结构 链式结构使用指针作为底层容器通过指向子节点的指针来表示树的逻辑结构。这种方式在存储灵活性和空间利用效率方面优于顺序结构。通用方法是链表中每个节点由三个域组成数据域和左右指针域。 typedef int treeType;//将int重定义为type_t typedef struct TreeNode {treeType val; //表示数据TreeNode* left; //表示左孩子TreeNode* right; //表示右孩子 }TreeNode;图片 总的来说选择使用链式结构还是顺序结构要根据具体的存储需求来决定。 三、二叉树的遍历 当我们介绍数组、链表时为什么没有着重研究他们的遍历过程呢 二叉树的遍历又有什么特殊之处 在计算机程序中遍历线性结构的数组或链表是一件简单的事情。相反二叉树是一种典型的非线性数据结构遍历时需要将非线性关系的节点转化为线性序列。 二叉树的遍历可以根据节点的直接位置关系分为两类 深度优先遍历前序遍历、中序遍历、后续遍历广度优先遍历层序遍历 下面就来看看这些不同的遍历方式吧ο(•ω)ρ⌒☆
5. 深度优先遍历 前序遍历 二叉树的前序遍历遍历顺序为根节点、左子树、右子树当遇到空指针NULL时返回。 代码示例如下 void PreOrder(TreeNode* root) {if (root NULL){return;}//先取出当前节点元素再对其进行相关操作printf(%d, root-val);InOrder(root-left);//遍历左节点InOrder(root-right);//遍历右节点 }中序遍历 二叉树的中序遍历遍历顺序为左子树、根节点、右子树当遇到空指针NULL时返回。 代码示例如下 void InOrder(TreeNode* root) {if (root NULL){return;}InOrder(root-left);//遍历左子树printf(%d, root-val);//取出元素进行操作InOrder(root-right);//遍历右子树 }后序遍历 二叉树的后序遍历遍历顺序为左子树、右子树、根节点当遇到空指针NULL时返回。 代码示例如下 void PostOrder(TreeNode* root) {if (root NULL){return;}PostOrder(root-left);//遍历左子树PostOrder(root-right);//遍历右子树printf(%d, root-val);//取出元素进行操作 }2. 广度优先遍历 广度优先遍历按层次遍历从根节点开始按从上至下从左至右的顺序遍历二叉树的所有节点。 使用广度优先算法我们通常需要借用队列这个数据结构来实现不知道队列的或者没看过这篇文章的赶紧取看看传送门 接下来我们就会使用队列来完成我们所需要的操作。 这是上一期的队列节点结构我们需要把QueueType的类型改为TreeNode来存放我们的节点 typedef TreeNode QueueType;//改为TreeNodetypedef struct QueueNode {QueueType value;struct QueueNode next; }QueueNode;而这也就是为什么我们需要对类型typedef的原因可以方便我们做修改φ(゜▽゜)♪ 遍历代码示例如下 void LevelOrder(TreeNode root) {Queue q;queue_init(q);queue_push(q, root);while (!queue_empty(q)){TreeNode* cur queue_front(q);queue_pop(q);if (cur NULL){continue;}printf(%d, cur-val);//取出元素进行操作queue_push(q, cur-left);queue_push(q, cur-right);}//不要忘了释放Queuequeue_destory(q); }在刷题过程中单纯只是这样多半会有些不够接下来我们就把代码进一步优化吧 void LevelOrder(TreeNode* root) {Queue q;queue_init(q);int level 0; //表示当前层数————queue_push(q, root);while (!queue_empty(q)){TreeNode* cur queue_front(q);queue_pop(q);//————————————————–int level_size queue_size(q);//获取当前层的元素个数for (int i 0; ilevel_size; i){printf(%d, cur-val);//取出元素进行操作//对当前节点的左右子节点进行判断若为空便没有必要入队列if (cur-left ! NULL){queue_push(q, cur-left);}if (cur-right ! NULL){queue_push(q, cur-right);}} //—————————————————level;//层数1 ————}//不要忘了释放Queuequeue_destory(q); }当每一层入完队列之后队列内的元素个数一定是下一层的元素个数可以简单的画一个图来看看这里就给大家布置一个小问题让你们自己来理解吧- 四、小结 二叉树是树形结构的一种其中每个节点最多有两个子节点。二叉树有多种遍历方法包括深度优先遍历和广度优先遍历。 深度优先遍历有三种 前序遍历中序遍历后序遍历 分别对应的遍历顺序为 根节点、左子树、右子树 左子树、根节点、右子树 左子树、右子树、根节点
   广度优先遍历的遍历顺序是从上到下、从左到右。 点赞是对博主的鼓励和支持 希望你们看完这篇博客后不妨给博主一个大大的三连表示对内容的赞赏 当然如果你是真心被内容打动那么点个四连甚至五连都是博主最大的动力 让我们一起用简单幽默的语气为点赞助力ο(•ω)ρ⌒☆ 题让你们自己来理解吧-