• 3
  • 新人请关照

算法导论树的内部节点指的是什么节点?

关于树的内部节点我有些不理解,希望大佬解答一下

在算法导论红黑树那章有一段话是这样写的:

树中每个节点包含5个属性:color、key、left、right、和p。如果一个节点没有子节点或父节点,则该节点相应指针的属性值为NIL。我们可以把这些NIL视为指向二叉搜索树的叶节点(外部节点)的指针,而把带关键字的节点视为树的内部节点。
  1. 如果只有一个节点,那这个节点是内部节点还是外部节点?
  2. 如果是有15个节点呢,如下图一样,有多少内部哪些是内部节点,哪些是外部节点?

图片描述

阅读 1.6k
评论
    1 个回答
    • 3.7k

    这段话不是定义得很清楚吗?外部节点指的是叶子节点,非叶子节点就是内部节点。

    按照这个定义,如果只有一个节点的输,这个节点是叶子节点,所以是外部节点,但我认为这是没有意义的,这段话里面的二叉搜索树,应该不会只有一个节点,这应该是一个非法的状态。

    这个图也很清楚,1,3,5,7,9,11,13,15没有子节点所以是叶子节点所以是外部节点,其他的都是内部节点。

    一般意义上的二叉搜索树,外部节点用来装载要搜索的数据项,但不论有没有需要搜索的数据项,树应该都存在,所以可能会有一个根节点,这时候,和我上面的结论相反,如果二叉搜索树只有一个节点,那么这个节点是根节点,是内部节点而不是外部节点。

    如果只有一个搜索数据项,二叉搜索树应该有两个节点,一个是根节点,数据节点也就是外部节点作为根节点的子。

      撰写回答

      登录后参与交流、获取后续更新提醒

      相似问题
      推荐文章