Java教程

数据结构_二叉树

本文主要是介绍数据结构_二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二叉树

基本概念

树的定义

在这里插入图片描述
所以树一定有至少一个节点(没有空树的概念),但是二叉树可以没有节点。虽然这个点无关紧要,但还是提一下。

关系术语

在这里插入图片描述

层次术语

在这里插入图片描述

例题

在这里插入图片描述

首先我们假设这些点都是独立的那么明显有4x3+3x4+2x5+1x2=36个叶子,但是现在他是树,那么我们将这些独立得东西合并,显然,n个合并会减少n-1个叶子(因为合并只能替换叶子),所以36-(3+4+5+2-1)=23,所以叶子的个数为23

二叉树定义

在这里插入图片描述

二叉树性质

在这里插入图片描述
前两个很好理解,就不说了。
第三个:设度为一的节点数为n1所以叶子的个数为:n0=2xn2+n1-(n1+n2-1)=n2+1;记住这个结论,加快解题速度。
当然用PPT上的证明也可以理解,就是麻烦一点,解释一下PPT上第二个式子:
在这里插入图片描述
大部分结点头上都有一个分支连着,除了根节点,所以节点数与分支数的关系为:n-1=分支数,即在这里插入图片描述

来道例题:
在这里插入图片描述
直接n0-1=19

特殊二叉树

在这里插入图片描述
这个很好理解就是K层的塞满结点(不能再多的树)

在这里插入图片描述
就是在满二叉树的基础上,从左往右去掉若干个结点(必须按照顺序,不能越过某一个)

完全二叉树性质

在这里插入图片描述
在这里插入图片描述
性质5很简单,那就解释一下性质四,n在(2k-1-1,2k-1],即[2k-1,2k-1],所以向下取整后值必为k-1,再加上一个1就是k了。

一大波习题

在这里插入图片描述
一个一个来吧,第一题:
100个节点,第一个想法是利用n0=n2+1,先求出层数k,那么从2到k-2之间的都是度为二的,再加上第k层的节点数mod2向下取整得到第k-1层的度为2的节点数。但是这题有更好的方法,还记得那个编号吗,叶子的特点是没有孩子,也就是说叶子的编号乘以二是大于100,那么很明显,51-100都是叶子,共50个。
第二题:第七层可以容下26个,这里明显没有满,所以一共七层,那么总结点书就是,10+前六层的个数(前六层是一个满二叉树)=73,利用上一题的结论叶子数为37,所以n2=37-1=36,进而推出n1=73-37-36=0
第三题:
对的,从完全二叉树定义出发,1到k-2层肯定没有度为1的,k-1层最多一个,k层都是叶子,所以要么一个要么没有,同时这题给了我们一个结论,就是总结点数为偶数的完全二叉树入度为1的个数为1,总结点数为奇数的完全二叉树入度为1的个数为0.
第四题:
两者编号介于[2k-1,2k-1],之间,所以以2为底取对数后向下取整的值是一样都为k-1,考虑这个范围的下面一个,值为k-2,上面一个值为k,所以只要满住以2为底取对数后向下取整的值一样就行。

存储

顺序存储方式

在这里插入图片描述
在这里插入图片描述
解答一下两个问题:
一.220-1,230-1,参考满二叉树结点个数

  1. 现判断是否是父子关系,若不是进入下一步,
  2. 选一个数不断/2向下取整,直到遇到存在的结点,
  3. 然后另一个也这样操作,中止条件是比上面得到的数小或相等(相等直接返回)
  4. 回到步骤2

链式

在这里插入图片描述
在这里插入图片描述
第二个问题转化为n1,n0的个数问题就行了
看道习题
在这里插入图片描述
有两种情况,一种是第六层是做后一层
第二种是第六层是倒数第二层
第一种情况很简单,也不是节点数最多的。看一下第二种,第六层是满的,加上之前的有26-1个结点,第七层有26-2x5或26-(2x5+1)个结点,所以,最多有26-1+26-2x5个结点。

遍历

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
每次在中序中找分割点就行了:以第一层为例,前序第一个为A,所以A是根节点,中序中以A为分隔点,左边为左子树部分,右边为右子树部分,而且这两团在前序中肯定是抱团存在的,找出这两团,BCDE,FG,这两团的中序就是分割后的两部分,又回到了刚开始的情形,明显B,F为左右孩子,。。。。
在这里插入图片描述
这个简单,更之前的一样,只是这次都是从每团的最后一个找。
还有,为什么只有前序和后序不能确定一棵二叉树,答案很明显,我们可以通过后序每团的最后一个和前序每团第一个确定根节点,我们甚至可以根据抱团的原则,找出那个是左边那团,那个是右边那团,但是抱团会出现歧义(当然如果限定条件的话也许可以画出唯一的二叉树)
比如这个:在这里插入图片描述
有这么多种分割方法(框出来的是左子树)。为什么前面说一定会出现歧义:因为子框和红框这两种必然存在的分类方式就已经可以导致歧义了。

算法实现

在这里插入图片描述
在这里插入图片描述
练习
在这里插入图片描述
(2)不会,先放着
(3)在visit那步加一个计数的就行了。
在这里插入图片描述
第一个:限定输出条件就行了,
第二个:跟背包问题(见递归那里)类似,定义一个数组(全局)存待输出的值,再定义一个数(局部)存放入了几个数,不断往左往右试探,遇到叶子就打印数组。
第三个:解答PPT上有,这个递归函数的出口时到达叶子时返回1
return max(fun(T->left),fun(T->right))+1 //T是当前结点
在这里插入图片描述

二叉树构建

二叉树包含数据和结构,数据好说,但是结构难搞。
这里的解决方案是要求用户以前序遍历的结果输入数据
在这里插入图片描述
在这里插入图片描述
传入当前节点指针的引用用于改变当前的内容(NULL或塞东西)
还有get_root的反回值必须是引用,不然我们没法改变根节点指针的指向。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
这个从根节点开始,一个一个来相互补充就行了。

线索二叉树

略,详见视频笔记

树和森林

森林:很多棵树

树的存储

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
就是把上面的结点位置变了一下,没有结构上的改变,因为上面的本来就是一棵二叉树。

森林存储

在这里插入图片描述
为了跟上面做区分,树与数之间用红线相连。
在这里插入图片描述
在这里插入图片描述

树与森林的遍历

在这里插入图片描述
在这里插入图片描述
就是前序遍历化完后的二叉树
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

哈夫曼树

引入

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

把结点的指针塞给优先队列,然后拿前两个合并一下重新塞回去
在这里插入图片描述
这个结论记一下
在这里插入图片描述
从根节点往下走,往左记0往右记1,解码的话就是把按照码不断从根节点往下走(0往左,1往右遇到根节点就打印,然后回到根节点)
在这里插入图片描述

习题

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

这篇关于数据结构_二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!