数据结构基础--二叉树

某二叉树的后序和中序遍历序列正好一样,则该二叉树中的任何结点一定都无右孩子。
某二叉树的后序和中序遍历序列正好一样,则该二叉树中的任何结点一定都无左孩子。
答案为TF,可以这样来想哈,后序的话我们可以写作(left)(right)(根),中序的话我们可以写作(left)(根)(right),令二者相等 即可得到(right)=null

若A和B都是一棵二叉树的叶子结点,则存在这样的二叉树,其前序遍历序列为…A…B…,而中序遍历序列为…B…A…
答案为F,根据上面的方法我们将(根)=NULL,可以看到,不管是什么的遍历方法,结点为叶的情况下,顺序都是一样的

若一个结点是某二叉树的中序遍历序列的最后一个结点,则它必是该树的前序遍历序列中的最后一个结点。 (2分)
答案为F,考虑特殊情况,c为根,d为left,中序为dc,前序为cd

如果一棵非空k(k≥2)叉树T中每个非叶子结点都有k个孩子,则称T为正则k叉树。若T的高度为h(单结点的树h=1),则T的结点数最多为:(3分)
如果一棵非空k(k≥2)叉树T中每个非叶子结点都有k个孩子,则称T为正则k叉树。若T的高度为h(单结点的树h=1),则T的结点数最少为:(3分)答案为(k的h次方−1)/(k−1)k(h−1)+1,最多的时候很好想,就是每层都是上一层的k倍,也就是1、k、k^2^…所以也就是个等比数列,列公式就完事了。至于最少的情况就是从第二层开始就只有一个结点有孩子,那么也就是1+k+k+k+…+k个(注意这里的应该有h-1个k,因为第一层只有一个),所以答案是k(h-1)+1啦

1-5若一个结点是某二叉树的中序遍历序列的最后一个结点,则它必是该树的前序遍历序列中的最后一个结点。

中序序列即(left)根(right),先序序列是根(left)(right),最后一个结点都是right…吗?当然不是啦,你的right可别忘了还是个树,也就是说可能存在之后还存在上述的结构,而当我们在right树中如果没有下一个right的话,就会出现中序是(left)根,而前序是根(left)的情况,这就完蛋了。

1-7已知一棵二叉树的先序遍历结果是ABC, 则CAB不可能是中序遍历结果。

答案是T,先序遍历可以确定的是A为根结点,而B、C的位置是不确定的,可以归纳为2种情况

  • B、C都为叶子,那么根据我们上面的小技巧,B、C相对位置不能发生改变,所以不对
  • B、C不都为叶子,那么再次按照先序,B为子树的根结点,树就确认了,发现其中序遍历也不是CAB

2-3要使一棵非空二叉树的先序序列与中序序列相同,其所有非叶结点须满足的条件是:

还是老办法,依照题意有:根(left)(right) == (left)根(right),也就是left=0,所以不能有左子树,答案为只有右子树

2-4已知一棵二叉树的树形如下图所示,其后序序列为{ e, a, c, b, d, g, f }。树中与结点a同层的结点是:

首先,先用自己的字母填充满所有的顶点,然后自己拿后序遍历一遍,然后一一对应填入,之后就随便做了

2-5

在下述结论中,正确的是: (2分)

① 只有2个结点的树的度为1;

② 二叉树的度为2;

③ 二叉树的左右子树可任意交换;

④ 在最大堆(大顶堆)中,从根到任意其它结点的路径上的键值一定是按非递增有序排列的。

1是正确的,不说了;2显然不对,叶结点的度是1;3不对;4很对

2-7如果一棵非空k(k≥2)叉树T中每个非叶子结点都有k个孩子,则称T为正则k叉树。若T有m个非叶子结点,则T中的叶子结点个数为:

这个题目要用到之前总结的知识了,我们设该树有h+1层,由于树为k叉树,所以其叶结点的个数为k的h次方,那么我们忽略所有的叶结点,剩余的树依然是k叉树,其结点数也就等于m(题目条件),那么由之前总结的公式得到 (k的h次方−1)/(k−1) == m,解得k的h次方也就等于m(k−1)+1

2-8有一个四叉树,度2的结点数为2,度3的结点数为3,度4的结点数为4。问该树的叶结点个数是多少?

这题可以用个小技巧,结点+边法,我们设结点数为x,由于树的性质可知边个数为x-1,设叶结点的个数为y,那么可列方程:x == y + 2 + 3 + 4 y == 2x2 + 3x3 + 4x4 + x*0,解方程就完事了

2-11任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序

不发生改变,上边证明过了

2-12二叉树中第5层(根的层号为1)上的结点个数最多为:

其实这个上面的题目用到过这个知识点了,最多就是k的h-1次方,k是k叉树,h是高度

2-19设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少结点数和最多结点数分别为

一看就可以看出这其实就是之前的k叉树的最多最少结点问题,公式推过了,不再说了

successful,估计明天会更新排序,有时间的话还有更新树、森林、哈夫曼树,希望能在是考试前全部更新完吧,这样之后就可以好好更新别的内容啦