由含n个结点的二叉树线索化后有______ 个线索（不计头结点）。 A. 2n B. n+1_

学习人数: 4.2k

正确率: 56%

题目描述

未通过

由含n个结点的二叉树线索化后有______ 个线索（不计头结点）。

A. 2n

B. n+1

C. n-1

D. 2n-1

上面问题的答案是：

A 选项

B 选项

C 选项

D 选项

加入错题本

个人笔记

已有25条笔记

4 个回答 (点击展开回答)

2024年6月27日 08:37

问题等价于二叉树的空指针数量

2023年10月15日 16:53

由含n个结点的二叉树线索化后有n+1个线索（不计头结点）。

二叉树的线索化是在二叉链表的基础上，利用空闲指针域，将指向空孩子节点的指针改为指向该节点在某种遍历次序下的前驱或后继节点。由于每个节点有2个指针域，n个节点的二叉树原本有2n个指针域，其中有n-1个用于指向孩子的指针，剩下的n+1个空闲指针域可以用来线索化，形成n+1个线索。

2023年10月15日 15:47

由于二叉树线索化会将每个结点的左子树的最右结点指向其前驱，右子树的最左结点指向其后继，因此每个结点最多有2条线索。而对于一棵含n个结点的二叉树线索化后，其中除了根结点，每个结点都有一条线索，所以总共有 n-1 条线索。

2023年9月15日 11:41

2n个链域中，n-1个有用，n+1个空着可做线索