由含n个结点的二叉树线索化后有______ 个线索(不计头结点)。
A. 2n
B. n+1
C. n-1
D. 2n-1
问题等价于 二叉树的空指针数量
由含n个结点的二叉树线索化后有n+1个线索(不计头结点)。
二叉树的线索化是在二叉链表的基础上,利用空闲指针域,将指向空孩子节点的指针改为指向该节点在某种遍历次序下的前驱或后继节点。由于每个节点有2个指针域,n个节点的二叉树原本有2n个指针域,其中有n-1个用于指向孩子的指针,剩下的n+1个空闲指针域可以用来线索化,形成n+1个线索。
由于二叉树线索化会将每个结点的左子树的最右结点指向其前驱,右子树的最左结点指向其后继,因此每个结点最多有2条线索。 而对于一棵含n个结点的二叉树线索化后,其中除了根结点,每个结点都有一条线索,所以总共有 n-1 条线索。
2n个链域中,n-1个有用,n+1个空着可做线索
B
用户登录可进行刷题及查看答案
登录后提交答案