购物网站界面 管理员需求分析,建筑工程招投标网,深圳创建公司要多少钱,个人房源网1我们之前学了二叉树的顺序存储#xff08;这种顺序存储的二叉树被称为堆#xff09;#xff0c;我们今天来学习一下二叉树的链式存储#xff1a;
我们使用链表来表示一颗二叉树#xff1a;
⽤链表来表⽰⼀棵⼆叉树#xff0c;即⽤链来指⽰元素的逻辑关系。通常的⽅法是…1我们之前学了二叉树的顺序存储这种顺序存储的二叉树被称为堆我们今天来学习一下二叉树的链式存储
我们使用链表来表示一颗二叉树
⽤链表来表⽰⼀棵⼆叉树即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。 比如这就是我们的二叉树的链式存储跟链表是不是比较像就是使用链表来进行存储我们的二叉树
但是我想你也一定发现了我们使用链式存储的二叉树不一定是完全的二叉树
我们之前在讲堆的时候我们的二叉树使用的一定是完全二叉树因为我们的堆的话使用的是顺序存储使用完全二叉树的话可以节省我们的内存空间
但是我们的二叉树在进行链式存储的时候没有这个要求我们可以是完全二叉树也可以是其他的二叉树没有什么要求
我们的链式存储我们该怎样定义我们的结点呢
我们可以知道我们的二叉树的度最大为2最小为0所以我们就设置两个指针一个左指针还有一个右指针分别指向我们的左孩子和右孩子 这就是我们的二叉树的结点的定义
二叉树的前中后序遍历
对二叉树的操作离不开二叉树的遍历我们来看一下二叉树的遍历
前序遍历先遍历根节点在遍历左子树最后便利右子树
中序遍历先遍历左子树在遍历根节点最后遍历右子树
后序遍历先遍历左子树在遍历右子树最后便利根节点
//我们的前中后分别表示的是根节点的位置前就表示根节点在第一个位置中就表示根节点在中间位置后就表示根节点在最后面的位置。 接下来我们来实现一下前序遍历的代码 这就是我们的前序遍历我们在函数里面进行递归调用我们先把我们的根节点的数据进行打印然后遍历我们的左子树然后遍历右子树当我们遇到的结点的数据是NULL的时候我们打印并返回
接下来我们来实现一下中序遍历 这个就是我们的中序遍历当然你可以发现他和前序遍历是比较像的我们只是改变了位置我们先进行了左子树的遍历然后当我们的左子树一直下去知道是空的时候我们返回然后打印我们的这课子树的根节点然后再进行这棵树的右孩子的遍历这样不断地递归 这就是我们的中序遍历的结果
接下来我们来看后序遍历
12
这就是我们的后序遍历我们还是可以发现那就是我们的基本代码还是没有什么大的改变我们还是只是改变了原来代码的顺序我们先让左子树进行遍历左子树无限的递归直到左子树的尽头然后在左子树的尽头我们先遍历右子树然后打印我们的根节点。 这就是我们的结果
然后我们来实现一下有关二叉树的代码的实现但是我们在这里对二叉树的插入操作这一些并不进行讲解因为我们进行链式存储的二叉树并不是完全二叉树只要是二叉树的话都可以进行链式存储这样的话我们的二叉树的插入位置就是非常多了这就没有了限制这就不是很好等到我们后面学习的红黑树平衡树的话这些对二叉树的插入操作是有限制的我们就可以实现一下插入操作
我们先来实现一下计算二叉树的结点个数
计算二叉树的结点的个数有两种方法
第一种的话我们对二叉树进行遍历然后设置计数器之前我们遇到根节点的话我们就打印数据这下我们不打印数据我们让计数器1遇到空结点的话我们不操作计数器但是这时候就出现问题了我们的size计数器不知道是使用局部变量还是全局变量这两个都不行局部变量的话因为我们遍历树我们的函数要不断地进行递归我们每次进入我们的函数的话我们的计数器都会被清零。。那我们使用全局变量呢也不行全局变量看着好像可以每次进入函数的话我们的计数器没有被清零但是有一个问题那就是我们的全局变量在我们递归调用遍历完我们的二叉树的时候我们的全局变量没有变化这就导致我们再一次调用我们的二叉树的时候size就加倍了这就累加了那怎么办呢我们还有方法就是我们不设置计数器了我们直接使用递归来进行。 实际的代码只有几行我们进行判断如果是空的的话我们就返回0但是如果不是空的的话我们就返回1判断根节点的左右子树
我们然后来继续看我们的下一个要实现的方法
二叉树的叶子结点的个数
我们要求二叉树里面叶子结点的个数那我们就要判断一下我们遍历到的这个结点是不是叶子节点那么我们要怎样判断他是不是叶子节点呢我们就看他的两个孩子是不是NULL如果他的两个孩子都是NULL的话我们就说这个结点是一个叶子节点。
我们在进行遍历的时候我们就看他是不是叶子结点如果是叶子节点的话我们就返回1不是叶子节点的话如果是根节点或者是空的结点我们就不管或者返回0然后我们还是使用遍历 我们来看我们的代码进入到我们的函数里面以后我们先判断它是不是空的结点如果是空的结点的话这就不是叶子节点我们返回0然后的话我们就再次进行遍历和我们的第一个判断结点个数其实是比较次相似的我们判断它的结点的个数的时候我们先进行判断看他是不是NULL不是的话我们进行return的时候进行1因为一颗正常的二叉树在进行链式存储的时候不需要是完全二叉树我们如果可以遍历到的话他不是NULL就是一个正常的结点 所以我们要统计结点的个数的话我们就1然后遍历这个结点的左子树和右子树然后不断的递归调用我们的函数最终就可以得到我们的二叉树的节点的个数这里的话我们就不1了我们进行额外的叶子节点的判定。
二叉树第K层结点的个数:
这里的话我们就传两个参数我们的第一个参数还是我们的二叉树的根节点当然我们传的还是一级指针的我们不需要修改我们的二叉树我们传一级指针就可以了然后我们的第二个参数我们就传一个计数器我们传一个k我们不断地让k--当我们的k等于1的时候就来到了我们的第k层然后我们遍历到k等于1的结点的时候我们就返回1。 我们来看我们的代码我们进入到我们的函数我们先判断是不是NULL是的话我们就返回0因为我们的链式存储的二叉树不要求是完全二叉树所以还没到第k层的时候就先出现了NULL所以我们还是要对NULL进行一下判断是NULL的话我们就返回0不是的话我们就继续这时候我们可以继续进行就说明我们的这个结点他不是NULL所以的话我们就判断一下他是不是第k层就可以了是的话我们就返回1然后我们的return还是和之前一样我们直接进行他的左右子树的判断进行不断的递归判断。
求二叉树的深度或者高度:
我们还是要根据递归的思想来进行判断,首先我们开始的时候进入的就是根节点然后根节点不是NULL然后我们就继续我们就求他的左子树的大小然后我们再求右子树的大小然后我们1一个三目操作符判断左右子树哪个比较大加的1就是我们的根节点 我们来看我们的函数我们进入我们的函数进入到函数里面以后我们还是遇到NULL的话我们返回0然后的话我们就根据我们的思路我们先把左子树的高度求出来然后把右子树的高度求出来然后return 1左右子树里面比较大的那个我们在求他的左右子树的时候我们还是使用我们的这个函数假如我们要求这个左子树的高度的时候我们就求这个左子树的左子树的高度和右子树的高度然后return 1比较大的子树然后这就是我们的左子树我们就这样不断地进行递归直到我们的左右子树变成NULL的时候我们就递归到尽头了。这时候就返回我们就可以求出我们的二叉树的高度。
然后接下来我们要实现的是
查找二叉树节点值为x的结点: 我们直接来看我们的代码
当然我们这次函数的传值传的还是两个参数第一个参数为根节点第二个参数是我们的x值进入到函数里面我们还是遇到NULL的结点的时候我们就返回NULL如果他不是NULL的话我们就判断这个非空的结点的data是不是x如果这个结点的数据恰好就是我们的x的话我们就返回这个结点但是如果这个结点的x不是我们要求的x的话我们就看他的左孩子是不是我们要求的x我们再次进入到我们的函数里面我们先进行判空如果不是NULL的话我们就看他的data是不是我们要求的x如果是的话我们就返回然后返回到我们的第一个函数里面然后我们把返回值存起来判断它是不是NULL如果不是NULL的话我们就把他返回在这里可能你觉得有点草率你可能会说我们只进行判空那会不会返回的虽然不是NULL但是有可能是其他的不是data为x的结点呢但是其实你继续看当我们的结点的左孩子不是NULL并且左孩子的数据的data不是我们的x的话我们的函数就不会返回他我们就会判断我们的这个左孩子的左孩子看他是不是我们一定是不会返回我们的无效的数据的我们看我们的函数我们进行返回的条件一定是他为NULL或者不为NULL但是他的data为x这时候我们才会进行返回至于下面的两个左右孩子我们其实就是函数进行递归我们的返回的条件永远是不变的。。
接下来我们来看
二叉树的销毁 直接来看我们的代码我们可以很清楚的发现我们的函数的参数是一个二级指针为什么这里是二级指针呢
因为这里的话我们是要改变我们的结点了,我们的一级指针就可以代表我们的结点我们要修改我们的结点就相当于是修改一级指针所以这里我们要传二级指针。
然后我们看我们的函数我们进入到我们的函数里面还是我们先判断我们的结点是不是NULL如果是的话我们就出节点什么都不返回直接return就可以但是如果我们得这个不是NULL的话我们就要进行遍历销毁我们的结点了这里就有一个问题我们是采用什么遍历方式在这里的话我们采用后序遍历我们把根节点放在最后面进行删除因为如果我们先删除根节点的话我们的这个结点的左右孩子就找不到了所以在这里我们只能使用后序遍历来进行销毁。
接下来我们来看下一个函数--
层序遍历
什么是层序遍历呢
之前我们学的前序遍历中序遍历后序遍历都是从左往右的进行遍历。
我们得层序遍历指的就是我们按层序的进行遍历先是第一层然后第二层的进行遍历 就比如我们的这个二叉树他进行遍历的结果就是A,B,C,D,E,F.
那我们该怎样才能实现我们的这个方法
我们在这里可以创建一个队列来进行 我们可以先把我们的第一个二叉树的结点放入到队列里面然后取第一个结点第一个结点出队列然后把第一个结点的左右非空孩子入队列然后继续取队头结点然后把队头结点的左右孩子非空孩子入队列。 我们来看我们的函数进入到我们的函数里面以后我们创建一个队列然后初始化一个空的队列然后把我们的根节点压入队列最后结束以后我们把我们的队列销毁
接下来我们来看
判断是否为完全二叉树
在这里我们判断一个二叉树是不是完全的二叉树 我们来看我们的这个二叉树这就不是一个完全二叉树显然这是一个非完全的二叉树他的数据就是不连续的我们在进行层序遍历的时候我们遍历的结果是 A,BC,D,NULL,E,F. 我们遍历完后的结果就是我们中间会有一个NULL这样的数据就是不连续的我们在实现我们的堆二叉树的时候我们采用的是完全的二叉树堆二叉树就是没有什么数据空间的浪费他的数据是连续的堆二叉树的底层就是一个数组我们的这个链式存储底层成了链表
所以我们就可以看这个二叉树的数据是不是连续的就可以了所以我们在这里就还是使用我们的层序遍历来进行我们的层序遍历就是按层的来进行遍历。 我们来看我们的非完全的二叉树层序遍历的结果就是当我们的队列取到空的结点以后我们的队列里面还有非空的结点这就是我们的非完全的二叉树。
但是我们的完全二叉树我们的队列在取到NULL的时候我们的队列里面的数据的结点就都是空的结点了。
我们来看我们的代码
