2. 计算机
  3. 一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为(57)个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后

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

admin2019-07-12  57
问题 一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为(57)个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点，则(58)。
选项 A、s→right指向的结点一定是s所指结点的直接后继结点
B、s→left指向的结点一定是s所指结点的直接前驱结点
C、从s所指结点出发的right链可能构成环
D、s所指结点的left和right指针一定指向不同的结点
答案C
解析 本题考查数据结构基础知识。具有m个结点的二叉树采用二叉链表存储结构，链表中共有m个结点，-每个结点中两个指针(当前结点的左、右孩子指针)，则共有2m个指针。除了树根之外，其余的每个结点都由一个来自父结点的指针所指向，因此该二叉链表结点中的空指针总数必定为2m-(m-1)＝m+1个，可以充分利用这些空指针域来存放结点的前驱和后继信息。对图(a)所示的二叉树进行中序线索化后如图(b)所示。假设指针s指向中序线索二叉树中的某结点，则s→right指向的结点不一定是s所指结点的直接后继结点。当s结点具有右子树时，s→right指向其右子树而不是后继结点。同理，s→left指向的结点不一定是s所指结点的直接前驱结点。在线索二叉树中，s所指结点的left和right指针可能指向相同的结点，从s所指结点出发的right链可能构成环，如图(c)所示。
转载请注明原文地址:https://kaotiyun.com/show/4QCZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)