电子商务网站优点,wordpress主题dux,wordpress安装网站吗,石家庄企业招聘信息网文章目录 一#xff1a;实现链式结构二叉树1.1前中后序遍历1.1.1遍历规则1.1.2代码实现 1.2结点个数以及高度等1.2.1二叉树结点个数1.2.2二叉树叶子结点个数1.2.3二叉树第k层结点个数1.2.4二叉树的深度/高度1.2.5 二叉树查找值为x的结点1.2.6二叉树的销毁 1.3层序遍历1.4判断是… 文章目录 一实现链式结构二叉树1.1前中后序遍历1.1.1遍历规则1.1.2代码实现 1.2结点个数以及高度等1.2.1二叉树结点个数1.2.2二叉树叶子结点个数1.2.3二叉树第k层结点个数1.2.4二叉树的深度/高度1.2.5 二叉树查找值为x的结点1.2.6二叉树的销毁 1.3层序遍历1.4判断是否为完全二叉树 二结语 欢迎大家阅读我的博客给生活加点impetus, 今天我们学习二叉树的实现感受递归的魅力 一实现链式结构二叉树
⽤链表来表⽰⼀棵⼆叉树即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。 我们先来定义链式结构二叉树的结构。 链式结构二叉树是由结点组成的定义二叉树的结构就是定义结点的结构。 在数据结构初阶的学习过程中中前期对于二叉树的插入代码不会深入研究在后期c阶段学习红黑树平衡树等会对二叉树数据的插入操作进行研究。 我们需要了解二叉树的遍历方式有哪些 1.1前中后序遍历 为了后方我们能够理解深刻我们先依据下列图示来手动创建一个二叉树 这里我们的存储类型为char类型因为存储的是字符。 创建结点 构造链式二叉树 接下来我们来深入讲解各种遍历方法的规则。
1.1.1遍历规则
按照规则⼆叉树的遍历有前序/中序/后序的递归结构遍历 1前序遍历(Preorder Traversal 亦称先序遍历)访问根结点的操作发⽣在遍历其左右⼦树之前 访问顺序为根结点、左⼦树、右⼦树 2中序遍历(Inorder Traversal)访问根结点的操作发⽣在遍历其左右⼦树之中间 访问顺序为左⼦树、根结点、右⼦树 3后序遍历(Postorder Traversal)访问根结点的操作发⽣在遍历其左右⼦树之后 访问顺序为左⼦树、右⼦树、根结点 接下来依靠规则自行先思考上述二叉树的遍历顺序先来说明结果 前序遍历首先从根结点进入依照前序遍历规则–根左右首先A结点是根结点可以直接打印左方为B结点B同样也是根结点所以打印B后会继续向下遍历直到找到不为根结点的结点其实就是叶子结点NULL右的话就是D结点右子树NULL此时B结点的整个左子树遍历完全同样方法遍历右子树直至A结点的左子树全部遍历完毕。同理遍历右子树。 顺序为A B D NULL NULL NULL C E NULL NULL F NULL NULL 中序遍历首先从根结点进入依照前序遍历规则–左根右首先A结点是根结点不能打印会继续向左遍历直至找到不为任何子树的结点度为0的结点即叶子结点先打印D的左子树再打印D最后打印D的右子树随后B的整个左子树打印完毕打印B后再打印B的右子树随后A的整个左子树打印完毕打印A后随后打印A的右子树同理。 顺序为NULL D NULL B NULL A NULL E NULL C NULL F NULL 后序遍历首先从根结点进入依照前序遍历规则–左右根首先A结点是根结点不能打印会继续向左遍历直至找到不为任何子树的结点度为0的结点即叶子结点先打印D的左子树再打印D的右子树再打印D随后B的整个左子树打印完毕打印B的右子树NULL随后打印BA的整个左子树打印完毕同理打印A的右子树。 打印顺序NULL NULL D NULL B NULL NULL E NULL NULL F C A 所以遍历时我们需要注意 1除叶子结点以外其他结点都是根结点当层次很多时1到h-1层都是层次2的树或子树。 2遍历时主要是涉及递归函数 1.1.2代码实现
前序遍历 中序遍历 后序遍历 图解前序遍历 细节 1遍历只能从根结点开始遍历且一定要根据口诀的顺序 2遍历都是先经过包含叶子结点的二叉树 3叶子结点其实是递归的结束条件 4递推回归时与函数栈帧创建的联系 5遍历时某结点看做根结点该棵树一定要延伸到叶子结点才能看做一棵树。 1.2结点个数以及高度等
1.2.1二叉树结点个数
大部分人想到的都是设置计数器那我们来看看这个算法的好坏。 方法一 所以这个地方我们需要传地址而且size既不能做全局变量也不能做局部变量。那我们索性添加一个参数。 来看下面这段代码 方法二直接来返回int 思路结点个数根结点1左子树结点右子树结点 我们来画图演示一下 逐步递推逐步回归、 方法二同样能够实现预期结果并且思路更加简单。 总结 1函数栈帧销毁函数执行完全或者return提前返回 :2局部变量static生命周期延长仍然存在作用域上例修饰size时仍然错误 1.2.2二叉树叶子结点个数 思路**左子树叶子结点个数右子树叶子结点个数** 1.2.3二叉树第k层结点个数 思路深度优先遍历k自减准确找到第k层最后返回个数 1.2.4二叉树的深度/高度 思路根结点max{左子树右子树} 最好使用变量接收一下因为我们需要比较大小 1.2.5 二叉树查找值为x的结点 思路查找左子树与右子树同时该结点是否为X 1.2.6二叉树的销毁 思路只能后序遍历因为每一个结点malloc都要释放如果先释放根结点孩子结点就找不到了。 注意优先级高低:-大于*。 free之后及时置空防止成为野指针。 1.3层序遍历
前方的所有遍历都是涉及前中后序遍历都是深度优先遍历。 下面我们来讲解广度优先遍历(层序遍历)我们来看这样一个题目 如果我们仍然按照深度优先来遍历的话肯定是不行的因为只有当该部分函数栈帧销毁之后才会继续进入到上一个函数栈帧。 思路借助数据结构–队列根结点入队列循环判断队列是否为空 不为空取队头出队头将队头的左右且不为空的孩子入队列。 我们来画图演示一下 再来看一张 下面是代码部分 细节 1我们涉及到了Queue我们需要重新添加Queue.c和Queue.h文件。 2队列中存储的是二叉树结点指针类型需要将Queue中定义的int改为struct BTNode。 3typedef重定义的是数据类型一定要加struct加以声明只写BTNode会报错。 4存储指针是因为结构体访问成员是指针类型左孩子右孩子如果直接存储结构体会报错。 5如果也把空孩子加入就会退出循环。 1.4判断是否为完全二叉树 性质 1除最后一层外其余结点的度都为2 2有序 我们需要使用层序遍历 思路层序遍历根结点入队列循环判断队列是否为空不为空取队头出队头将队头的左右孩子入队列不管是不是空遇到空停止循环比较队列剩余元素如果还有非空元素则为非完全二叉树反之是完全二叉树。 我们来画图理解观察区别层序遍历部分我将不再演示 接下来来看代码 细节 1层序遍历入得都是top(队头)的左右孩子如果写成root-left这将面临死循环。 :2这里的队列并不是依次相连的中间有很多断开的而最开始的Queue结点是一个一个依次相连的 二结语
最后感谢大家的阅读欢迎大家有更多的思路与我交流同时不足之处欢迎指正 逆水行舟–不进则退加油希望早日看见最好的自己
