9、一棵左右子树均不为空的二叉树在后序线索化后（不带头结点的线索化），其空指针域数为

发布网友发布时间：2022-05-30 21:57

共3个回答

热心网友时间：2023-11-23 11:50

选B，
因为，例如，某二叉树的后续序列为dbca，显然，只有位于序列首尾的节点其指针域才可能为空，即只考虑节点d、a；由后续序列dbca，对节点d有，d无前驱，d有后继是b；对节点a有，由于a是整棵树的树根，又题目说左右子树均不为空即a有左右子树，也就是根节点a的左右指针域均不为空。
综上，只有节点d有一个空指针域，即选B。

热心网友时间：2023-11-23 11:50

插入序列：12, 4, 1, 7, 8, 10, 9, 2, 11, 6, 5

1、先插入12成为根

2、插入4在12的左子树，没有旋转

3、插入1在4的左子树，以4为中心向右单旋转，结果如下：
4
/ \
1 12

4、插入7在12的左子树，没有旋转

5、插入8在7的右子树，以8开始先左后右双旋转，结果如下：
4
/ \
1 8
/ \
7 12

6、插入10在12左子树，以8为中心开始向左单旋转，结果如下：
8
/ \
4 12
/ \ /
1 7 10

7、插入9在10 的左子树，以10为中心向右单旋转，结果如下：
8
/ \
4 10
/ \ / \
1 7 9 12

8、插入2在1的右子树，没有旋转

9、插入11在12 的左子树，没有旋转

10、插入6在7的左子树，没有旋转

11、插入5在6的左子树，以6为中心向右单旋转，结果如下：
8
/ \
4 10
/ \ / \
1 6 9 12
\ / \ /
2 5 7 11

热心网友时间：2023-11-23 11:51

b
是b
真的是b

9、 一棵左右子树均不为空的二叉树在后序线索化后（不带头结点的线索化），其空指针域数为

9、一棵左右子树均不为空的二叉树在后序线索化后（不带头结点的线索化），其空指针域数为