数据结构基础--树、森林、哈夫曼树

今天上了一天的数电。。。明明本来没那么多课的,结果硬生生加了好几节。。。估计今天更不了排序了,先把树这部分搞完吧

1-1对于一个有N个结点、K条边的森林,不能确定它共有几棵树。

答案是F,这个其实是可以算出来的,我们在图中说过树是边最少的一种连通图了,其边数(下文中边数用e数代替)== 结点数(下文中用v数代替)-1,所以我们就知道了, N - K的差值就是树的个数了

1-2对N(≥2)个权值均不相同的字符构造哈夫曼树,则树中任一非叶结点的权值一定不小于下一层任一结点的权值。

这个是对的因为构造哈夫曼树的时候就是每次拿出最小的来一层层搭建的,而且每一次搭建的上一层都是下边两个的和,所以其实非叶结点的权值都是要大于等于下一层结点的值的

2-1具有1102个结点的完全二叉树一定有__个叶子结点。

这个之前也用过了,就是2n(2n是总的v数)/2个,至于为啥,我们拿1到2n依照层序遍历好所有的v,自然最后一层的最后一个也就是2n,而由于是完全二叉树,最后一层的结点数除以2也就是之前一层的结点数,也就是说上一层v的最后一个就是n,那么最后一层的第一个就是n+1……一直到2n,就是n个。

2-2若森林F有15条边、25个结点,则F包含树的个数是:

上面说过了,就是v-e

2-3将森林转换为对应的二叉树,若在二叉树中,结点u是结点v的父结点的父结点,则在原来的森林中,u和v可能具有的关系是: (3分)

  1. 父子关系; 2. 兄弟关系; 3. u的父结点与v的父结点是兄弟关系

答案是1和3,首先我们要知道森林是怎么变成二叉树的,这里也顺便详细总结一下几种常见的转换吧

  • 树转换为二叉树,简单说就是三步,加线、去线、转圈。首先把所有的兄弟结点都加上线,接着把非叶结点只保留与第一个孩子的结点,其他全部去掉,然后调整到一个比较好看的角度就完了

  • 森林转换为二叉树,这个也很简单,首先把所有的树都变成二叉树,然后下一棵树都变成上一棵树的右儿子就完事了

2-4对于一个有N个结点、K条边的森林,共有几棵树?

N-K,上面详细说过了。

2-5设森林F中有三棵树,第一、第二、第三棵树的结点个数分别为M1,M2和M3。则与森林F对应的二叉树根结点的右子树上的结点个数是:

这个就是上面提到的那个森林变二叉树的过程,实际上是M3成了M2的右子树,M2成了M1的右子树,所以右子树的结点个数应该是M2+M3

2-6由若干个二叉树组成的森林F中,叶结点总个数为N,度为2的结点总个数为M,则该集合中二叉树的个数为:

设有x个二叉树,度为1的结点为v,边数为e,根据之前推出来的结论有 x = n + m + v - e,对于边数e还有e = 2*m + v,连立得x = n - m

2-7已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则该完全二叉树的结点个数最多是

附加题 已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则该完全二叉树的结点个数最少是

对于题目中的完全二叉树来说,最起码前五层都是满的,所以就是上次总结的等比数列求和公式2的五次方-1除以2-1,也就是31,而第六层就有故事了(因为完全二叉树的叶结点只有可能出现在最后一层和倒数第二层)

  • 第六层就是最后一层,那就是31 + 8 = 39了,也就是最少的情况

  • 第六层是倒数第二层,那么就是有8个结点到头了,往下不能延伸了,但剩下的2的五次方-8个顶点还是可以继续往下走的,所以就是第七层还有48个结点,加起来就是最多的情况了

2-8在一个用数组表示的完全二叉树中,如果根结点下标为1,那么下标为17和19这两个结点的最近公共祖先结点在哪里(数组下标)? (注:两个结点的“公共祖先结点”是指同时都是这两个结点祖先的结点)

来看一下二叉树在数组中常见的几种查找。设结点的序列为index(假设根结点为0),那么他的左儿子也就是2*index+1,他的右儿子也就是2*index+2,而他的父亲就是(index-1)/2。

题目中因为根结点是1,我们提前一格,所求的就是16和18,根据公式得7和8,再求一次得3,因为我们index提前了一格,所以再加1,答案就是4了

2-9具有65个结点的完全二叉树其深度为(根的深度为1)

记住公式就完事了,深度k =[log~2~N] + 1(注意要向下取整)

2-10对N(N≥2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中,错误的是:

当一棵具有n 个叶子结点的二叉树的WPL 值为最小时,称其树为哈夫曼树,其二叉树的形状是唯一的

哈夫曼树的形态不是唯一的,但是它的带权路径长度WPL是唯一的。

如:3,5,6

可以构造出

​ 14

​ 8 6

3 5

​ 14

​ 6 8

​ 3 5

这两种形态,所以哈夫曼树形态不唯一。

2-18(neuDS)在哈夫曼树中,任何一个结点它的度都是( )

0或者2,因为,这很好想吧,因为我们都是拿两个结点拼起来的