现在假设F是一个森林，B是由F转换得到的二叉树，F中有n个非

[单选题]

现在假设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有（）个?

查看正确选项

冯吃吃呀

根据森林转换为二叉树的“左孩子右兄弟”的表示法，即对于每棵二叉树，每个结点的右指针指向其右邻兄弟。

针对每一个非终端结点，一定会有且仅有一个孩子结点没有右邻兄弟，即右指针领域为空。因此N个非终端结点，就有N个右指针域为空。

看完单棵二叉树，再来看这些二叉树是怎么连接成一棵二叉树的。原理是：将后一棵二叉树的根节点作为前一棵二叉树的右孩子连接起来，所以只有最后一棵二叉树的根结点没有右孩子，即右指针域为空。

因此综上：N个非终端结点，就有(N+1)个结点的右指针域为空。

编辑于 2020-04-03 21:01:04 回复(0)

PKU_xiaowei

举个例子：

   1
 /   \
2     3

发表于 2020-04-11 15:58:39 回复(1)

提交观点

问题信息

C++工程师网易算法工程师 2020 数据分析师 Java工程师

上传者：小小

难度：

2条回答 291收藏 3058浏览

扫一扫，把题目装进口袋