[树和二叉树](7)题集_1

前言:由于该篇幅画图题太多,所以为了节省时间,我大部分都抄了答案(绿色底图即为答案)。

1、已知一棵树边的结合为{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H>,<A,C>},请画出这棵树,并回答下列问题:

  1. 哪一个是根节点?
  2. 哪些是叶子结点?
  3. 哪个是结点G的双亲?
  4. 哪些是结点G的祖先?
  5. 哪些是结点G的孩子?
  6. 哪些是结点E的子孙?
  7. 哪些是结点E的兄弟?哪些是结点F的兄弟?
  8. 结点B和N的层次号分别是什么?
  9. 树的深度是多少
  10. 以结点C为根的子树的深度是多少?

如下图所示:

img

2、一棵度为2的树和一棵二叉树有何区别?

  • 度不同

    • 度为2的树要求每个结点最多只能由两颗子树,并且至少由一个结点有两棵子树,二叉树的要求是度不超过2,结点最多有两个分支,可能为1或者0
    • 在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个
  • 分支不同

    • 度为2的树有两个分支,但分支没有左右之分
    • 一棵二叉树也有两个分支,但有左右之分,左右子树的次数不能随意颠倒
  • 次序不同

    • 度为2的树从形式上看与二叉树很相似,但是其子树是无序的,而二叉树是有序的,即,在一般树中,若某个结点只有一个孩子,就无需区分其左右次序,而在二叉树中即使是一个孩子也有左右之分

3、试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态

img

4、一棵深度为H的满k叉树有如下性质:

  • 第H层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树
  • 如果按层次顺序从1开始对全部结点编号,问:

    1. 各层的结点数目是多少?
    2. 编号为p的结点的父结点(若存在)的编号是多少?
    3. 编号为p的结点的第i个儿子结点(若存在)的编号是多少?
    4. 编号为p的结点有右兄弟的条件是什么?其右兄弟编号是多少?

思路:度为H,的满K叉树,我们假设H为3,深度为4,如下图所示:

image-20210120014042370

  1. 每层结点数位:k^(H(i)-1)

    1. 当i为1的时候,H(i)=1,3^(1-1)=1
    2. 当i为4的时候,H(i)=4,3^(4-1)=27
  2. 当p=1时,该结点为根,无父节点,否则其父节点编号为p+(k-2)/2的最大值
  3. 其第k-1个儿子的编号为p*k,所以,如果它有儿子,则其第i个儿子的编号为p*k+(i-(k-1))
  4. (p-1)%k!=0时,该结点有右兄弟,其右兄弟编号为p+1

5、已知一棵度为k的树中有n1个度为1的结点,n2个度为2的结点,....nk个度为k的结点,问该树中有多少个叶子结点?

n0=1+sum(上限为k,i=1)(i-1)ni

6、已知在一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点,试求该树含有叶子结点的数目

思路:这题可以套用二叉树的性质三如下所示

性质三:对任何一颗二叉树T,如果其终端结点树为n0,度为2的结点树为n2,则n0=n2+1

这儿就是把2换成k即可,则n0=nk+1

7、一棵含有n个结点的k叉树,可能达到的最大深度和最小深度各为多少

  • 最大深度为n+k-1(因若最大深度是为n个节点的单支树,则该树有可能不是k叉树了,这zhuan不符合k叉树的定义了,当k为1时,shu最大深度才为n,所以最大深度为n+k-1才具有普遍意义!)
  • 最小深度为以k为底(n*(k-1)+1)的对数,并对该对数向上取整

8、证明:一棵满k叉树上的叶子结点n0和非叶子结点数n1之间满足关系:n0=(k-1)n1+1

证明:由于是满k叉树,因而只有度为0和度为k的结点,设度为0的结点有n0个,度为k的结点有n1个,结点总数为n,则:

  • 结点关系:n=n1+n0
  • 分支关系:n-1=k·n1
  • 因而可得:n0=k(k-1)n1+1

9、试分别推到含有n个结点和含n0个叶子结点的完全三叉树深度H

图示如下:

image-20210120035352917

答案:image-20210120035442894

10、对于那些所有非叶子结点均有非空左右子树的二叉树:

(1)试问:有n个叶子结点的树中共有多少个结点?

(2)试证明:img,其中n为叶子结点的个数,li表示第i个叶子结点所在的层次(设根结点所在的层次为1)

img

11、在二叉树的顺序存储结构中,实际上隐含着双亲的信息,因此可和三叉链表对应,假设每个指针域占4个字节存储,每个信息域占k个字节的存储,试问:对于一棵有n个结点的二叉树,且在顺序存储结构中最后一个结点的下标为m,在什么条件下顺序存储结构比三叉链表更节省空间。

img

12、对第3题所得的各种形态的二叉树,分别写出前序,中序,后序遍历的序列

终于碰到一道水题了!!!

img

13、假设n和m为二叉树中两结点,用“1”、“0”、或“Φ”(分别表示:肯定、恰恰相反,或者不一定)填写下表:

思路:左方和右方可以根据(根左右)、(左根右)、(左右根)来求得。而祖先和子孙画图求得即可,如下所示:

image-20210120041007861

当n为m的祖先:

  • 假设n为b,m为d时:前序[n在m前]、中序[n在m后]、后序[n在m后]
  • 假设n为b,m为e时:前序[n在m前]、中序[n在m前]、后序[n在m后]
  • 假设n为a,m为e时:前序[n在m前]、中序[n在m前]、后序[n在m后]

当n为m的子孙,将上述n与m每种假设对换即可,由上分析可得:

image-20210120041729871

注:如果(1)离a和b最近的共同祖先p存在,且(2)a在p的左子树中,b在p的右子树中,则称a在b的左方(即b在a的右方)。

14、找出所有满足下列条件的二叉树:

(a)它们在先序遍历和中序遍历时,得到的结点访问序列相同;

(b)它们在后序遍历和中序遍历时,得到的结点访问序列相同;

(c)它们在先序遍历和后序遍历时,得到的结点访问序列相同。

思路:同样可以根据前、中、后遍历序列可以得到:

  • 当先序[根左右]和中序[左根右]序列相同时,是一棵不含左子树的树。
  • 当后序[左右根]和中序[左根右]序列相同时,是一棵不含右子树的树。
  • 当先序[根左右]和后序[左右根]序列相同时,是一棵即不含左子树也不含右子树的树

    • 我们可以从序列中取出某棵子树,等到的序列必然相同,又递归的思想将问题规模缩小化即可证得算法的正确性。

15、请对下图所示的二叉树进行后序线索化,为每个空指针建立相应的前驱或后继线索

img

思路:<u>我们先求得其后序序列:GDBEHFCA,然后根据其序列判断树中左右孩子是否为空创建线索,答案如下图所示:</u>

image-20210120044420729

16、将下列二叉链表改为先序线索链表(不画出树的形态)

思路:将下列二叉链表的先序序列求出照着填即可

image-20210120044633603

示例图如下:

image-20210120044707771

17、阅读下列算法,若有错,则改之

Bitee InSucc(BiTee q){
    //已知q是指向中序线索二叉树上某个结点的指针
    //本函数返回指向*q的后继的指针
    r=q->rchild;
    if(!r->rtag) r=r->rchild;
    return r;
}

思路:<u>q在中序[左根右]序列中的后继可能为:若q的右rtag域为0,则直接返回其右tag域</u>

否则返回其右子树中最左边的结点。

改后如下:

Bitee InSucc(BiTee q){
    //已知q是指向中序线索二叉树上某个结点的指针
    //本函数返回指向*q的后继的指针
    if(!q->rtag) return q->rchild;
    BiTee r=q->rchild;
    while(r->ltag) r=r->lchild;
    return r;
}

18、试讨论,能否在一棵中序全线索二叉树上查找给定结点*p在后序序列中的后继

思路:先画个图,如下所示:

image-20210120051219270

如上图所示,我们可以得出:

  1. 若p为根结点,则其在后序序列中无后继
  2. 若p不为根结点,则中序线索遍历查找p的双亲结点

    • 若p为其双亲结点的左孩子,则其在后序序列中的后继为其兄弟结点左下的子孙
    • 若p为其双亲结点的右孩子,则其在后序序列中的后继为其双亲结点

19、分别画出和下列树对应的各个二叉树

image-20210120052827325

树和二叉树的对应:左子树为其孩子,右子树为其兄弟,答案如下所示:

image-20210120052946237

6.20将下列森林转换为相应的二叉树,并分别按以下说明进行线索化:

(1)先序前驱线索化;

(2)中序全线索化前驱线索和后继线索;

(3)后序后继线索化。

思路:森林对应二叉树,先将森林中没棵树转换为二叉树,然后将其根节点沿右子树相连

image-20210120053321835

21、画出和下列二叉树相应的森林:

  • image-20210120053627717

<u>思路:与上一题类同,根沿着右子树拆开即可</u>

image-20210120053935385

22、对于19题中给出的各树分别求出以下遍历序列:

  • 先根序列
  • 后根序列

思路:按照二叉树的方法遍历即可,如下:

image-20210120054656936

23、画出和下列已知序列对应的树T: 树的先根次序访问序列为GFKDAIEBCHJ; 树的后根次序访问序列为DIAEKFCJHBG。

image-20210120054908514

24、画出和下列已知序列对应的森林F: 森林的先序次序访问序列为:ABCDEFGHIJKL; 森林的中序次序访问序列为:CBEFDGAJIKLH。

image-20210120055219640

25、证明:在结点数多于1的哈夫曼树中不存在度为1的结点。

思路:利用数学归纳法证明即可。

  1. 当n=2时,要使其成为最优二叉树,必须使两个结点都成为叶子结点
  2. 假设当n=k(k>2)时,结论也成立,则当n=k+1时,要使其成为最优二叉树,必须用前k个结点构造出的哈夫曼树与第k+1个结点组成的新的二叉树,所以n=k+1也成立
  3. 综上,结论成立

26、假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这8个字母设计哈夫曼编码。使用0~7的二进制表示形式是另一种编码方案。对于上述实例,比较两种方案的优缺点。

image-20210120055843997

27、假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。

28、假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该树。

29、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。

img

30、证明:树中结点u是结点v的祖先,当且仅当在先序序列中u在v之前,且在后序序列中u在v之后。

证明:命题等价于遍历时u在v之前的充分条件是遍历序列为先序序列,u在v之后的充分条件是遍历序列为后序序列

由于u是v的祖先,故若以u为根结点,v必在u的左子树或右子树上,考虑三种遍历次序,先序遍历是 【根、左、右】,中序遍历是【左、根、右】,后序遍历是【左、右、根】

  • 充分性:若要保证u在v之前,必须保证根结点的访问先于子树,即采用先序,相反,要保证u在v之后,必须保证根结点的访问迟于子树,即采用后序遍历
  • 必要性:若采用先序序列,必然先访问结点,后访问其子树,故u的访问必先与v,若采用后序序列,则根结点在最后被访问,因而u的访问必在v之后

31、证明:由一棵二叉树的先序序列和中序序列可唯一确定这课二叉树。

证明:命题等价于证明由一棵二叉树的先序序列和中序序列唯一可确定一结点的位序,进一步等价于证明由一棵二叉树的先序序列和中序序列可唯一确定任一结点的父结点的值及其属于此父节点的左孩子还是右孩子

  • 根据二叉树的性质,每一个结点最多只有一个父结点,所以无论其遍历序列如何,其父节点的值要么不存在(根结点)要么存在且唯一
  • 二叉树先序遍历序列为 [根左右],中序遍历序列为 [左根右],由此可得,对于任一结点,[在先序序列中寻找其前驱,若前驱不存在,说明此结点是树的根结点] ,若前驱存在,再判断 [此结点与其前驱] 在 [中序序列中的相对次序] ,若其前驱位于其右边,则可断定该结点为其父结点的左子树,否则为右子树
  • 这样一来,根据先序序列和中序序列,就可以唯一确定每一个结点的父节点值即其相对位置(左子树或右子树),进而确定每个结点的位置,由此就可确定唯一的二叉树

本文链接:

https://nullcode.fun/120.html
1 + 2 =
快来做第一个评论的人吧~