一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为n-1。

题目

一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为n-1。

相似考题

1.若一棵二叉树的叶子数为n,则该二叉树中,左、右子树皆非空的结点个数为n－1。()此题为判断题(对，错)。

2.●二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行 （42)遍历，可得到一个结点元素的递增序列（42）A. 先序（根、左、右）B. 中序（左、根、右）C. 后序（左、右、根）D. 层序（从树根开始，按层次）

3.若一棵二叉树中只有叶节点和左、右子树皆非空的节点，设叶节点的个数为k，则左、右子树皆非空的节点个数是【 】。

4.若一棵二叉树中只有叶结点和左右子树皆非空的结点，设叶结点的个数为k，则左右子树皆非空的结点个数是( )。A．2kB．k-1C．2k-1D．2k-1

更多“一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为n-1。”相关问题

  • 第1题：

    对于一棵具有n个结点的二叉树,其相应的链式存储结构中共有n－1个指针域空。()

    此题为判断题(对，错)。


    标准答案：错

  • 第2题：

    一棵左右子树均不空的二叉树在前序线索化后,其中空的链域的个数是:()。

    A不确定

    B0

    C1

    D2


    正确答案：C

  • 第3题：

    关于各种非空线索二叉树中空指针的个数有如下说法：

    ①任一非空先序线索二叉树有2个空指针。

    ②任一非空中序线索二叉树有2个空指针。

    ③任一非空后序线索二叉树有2个空指针。

    其中说法准确的个数是(5)。

    A．0

    B．1

    C．2

    D．3


    正确答案：B
    解析：非空先序线索二叉树有1或2个空指针，如图13-39所示。

    易知，先序序列的最后一个结点一定是叶子结点，该结点无后继，于是其右指针为空。先序序列的第一个结点一定是根结点，其无前驱，若根结点无左子树，显然其左指针为空，同时注意到，第一个结点的右指针、最后一个结点的左指针以及夹在第一个结点(根结点)和最后一个结点之间的任一结点的左右指针不是指向其左右子树便是指向前驱或后继的线索，均非空，于是该树中共有2个空指针；若根结点有左子树，那么根结点的左指针指向其左子树，同时也注意到，第一个结点(根结点)的右指针、最后一个结点的左指针以及夹在第一个结点和最后一个结点之间的任一结点的左右指针不是指向其左右子树便是指向前驱或后继的线索，均非空，于是该树中便只有一个非空指针。因此①错误。易知，任一非空中序线索二叉树中，中序遍历的第一个结点肯定是左子树为空的结点，它无前驱，其左指针为空；最后一个结点肯定是右子树为空的结点，它无后继，其右指针为空；第一个结点的右指针、最后一个结点的左指针以及夹在第一个结点和最后一个结点之间的任一结点的左右指针不是指向其左右子树便是指向前驱或后继的线索，均非空。因此，空指针一定是2个。因此②准确。非空后序线索二叉树有1或2个空指针(如图13—40所示)。

    其推理论证类似于非空先序线索二叉树，在此不再赘述。因此③不准确。

  • 第4题：

    若一棵二叉树中只有叶节点和左、右子树皆非空的节点，设叶节点的个数为1，则左、右子树皆非空的节点个数为【 】。


    正确答案：×
    0 解析：根据二叉树的性质：叶子节点数为双分支节点数加1。本题叶节点为1，所以双分支节点(左、右子树皆非空的节点)为0。

  • 第5题：

    一棵左右子树不空的二叉树在先序线索化后，其空指针域数为(15)。

    A．0

    B．1

    C．2

    D．不确定


    正确答案：B
    解析：先序线索化后其空指针域为0。

  • 第6题：

    一棵有n个结点采用链式存储的二叉树中，共有（）个指针域为空。

    An

    Bn+1

    Cn-1

    Dn-2


    B
    略

  • 第7题：

    一棵有19个结点的二叉树，采用链式结构存储，该树结构中有（）个指针域为空。


    正确答案:20

  • 第8题：

    二叉排序树或者是一棵空树，或者是具有下列性质的一棵二叉树：（1）若左子数不空，则左子树所有结点的值（）；（2）若右子数不空，则右子树所有结点的值（）； （3）左右子树又分别是（）。


    正确答案:均小于根结点的值；均大于根结点的值；二叉排序树

  • 第9题：

    填空题
    对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有（）个指针域为空。

    正确答案： n+1
    解析： 暂无解析

  • 第10题：

    填空题
    一棵有19个结点的二叉树，采用链式结构存储，该树结构中有（）个指针域为空。

    正确答案： 20
    解析： 暂无解析

  • 第11题：

    填空题
    一棵左右子树均不空的二叉树在先序线索化后，其空指针域有（）个。

    正确答案： 0
    解析： 暂无解析

  • 第12题：

    填空题
    二叉排序树或者是一棵空树，或者是具有下列性质的一棵二叉树：（1）若左子数不空，则左子树所有结点的值（）；（2）若右子数不空，则右子树所有结点的值（）； （3）左右子树又分别是（）。

    正确答案： 均小于根结点的值,均大于根结点的值,二叉排序树
    解析： 暂无解析

  • 第13题：

    在一棵二叉树的二叉链表中，空指针数等于非空指针数加(55)。

    A．2

    B．1

    C．0

    D．-1


    正确答案：A
    解析：当二叉树只有一个结点时，空指针数为2，非空指针数为0，空指针数比非空指针数多2。

  • 第14题：

    在一棵非空二叉树的中序遍历序列中,根结点的右边只有其右子树上的所有结点。()

    此题为判断题(对，错)。


    参考答案：正确

  • 第15题：

    一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其空链域数为(17)。

    A．0

    B．1

    C．2

    D．不确定


    正确答案：A
    解析：一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后就没有空链域了。

  • 第16题：

    一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为(57)个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点，则(58)。

    A．m+2

    B．m+1

    C．m

    D．m-1


    正确答案：B

  • 第17题：

    对二叉树进行后序遍历和中序遍历时，都依照左子树在前右子树在后的顺序。已知对某二叉树进行后序遍历时，结点M是最后被访问的结点，而对其进行中序遍历时，M是第一个被访问的结点，那么该二叉树的树根结点为M，且（ ）。

    A.其左子树和右子树都必定为空
    B.其左子树和右子树都不为空
    C.其左子树必定为空
    D.其右子树必定为空

    答案：C
    解析：
    前序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。中序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。后序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点。结点M是树根结点，而在中序遍历的时候，M是第一个被访问的结点，那么可以看出其左子树应该为空。

  • 第18题：

    一棵左右子树均不空的二叉树在先序线索化后，其空指针域有（）个。


    正确答案:0

  • 第19题：

    对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有（）个指针域为空。


    正确答案:n+1

  • 第20题：

    设一棵完全二叉树具有1000个结点，则此完全二叉树有（）个叶子结点，有（）个度为2的结点，有（）个结点只有非空左子树，有（）个结点只有非空右子树。


    正确答案:500；499；1；0

  • 第21题：

    判断题
    一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为n-1。
    A

    对

    B

    错


    正确答案： 对
    解析： 暂无解析

  • 第22题：

    单选题
    一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：（  ）。
    A

    0

    B

    1

    C

    2

    D

    不确定


    正确答案： C
    解析：

  • 第23题：

    单选题
    一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：（  ）。
    A

    不确定

    B

    0

    C

    1

    D

    2


    正确答案： C
    解析：

相关内容