根节点是内部节点吗？ [英] Is the root node an internal node?

问题描述

所以我在网路上看过，这里的stackoverflow中有几个问题的定义如下：

• 一般来说，内部节点是不是叶的任何节点（没有子节点的节点）


• 非叶/非终端/内部节点 - 至少有一个度不等于的子节点或后代节点到0


• 据我所知，它是一个不是叶子的节点。

我即将得出结论，根也是一个内部节点，但是它的定义似乎有一些歧义，如下所示：

什么是内部节点在二叉搜索树中？

• 如图所示，内部节点是位于树根和叶子

如果我们遵循该定义，则根节点不会被视为内部节点。根节点是否是内部节点？

解决方案

一本书中的声明：离散数学及其应用 - 第7版Rosen说，

有孩子的顶点称为内部顶点。根是一个内部顶点，除非它是图中唯一的顶点，在这种情况下它是一个叶。

支持定理：

对于任何正整数n，如果T是具有n个内部顶点的完整二叉树，则T
具有n + 1个叶子和总共2n + 1个顶点。

案例1：

  O < -  1内部节点以及根
 / \ 
 OO < -  2叶节点
  

案例2：平凡树

  O < -  0内部顶点（没有内部顶点），这是叶
  

So I've looked around the web and a couple of questions here in stackoverflow here are the definition:

• Generally, an internal node is any node that is not a leaf (a node with no children)
• Non-leaf/Non-terminal/Internal node – has at least one child or descendant node with degree not equal to 0
• As far as i understand it, it is a node which is not a leaf.

I was about to conclude that the root is also an internal node but there seems to be some ambiguity on its definition as seen here:

What is an "internal node" in a binary search tree?

• As the wonderful picture shows, internal nodes are nodes located between the root of the tree and the leaves

If we follow that definition then the root node isn't going to be counted as an internal node. So is a root node an internal node or not?

解决方案

Statement from a book : Discrete Mathematics and Its Applications - 7th edition By Rosen says,

Vertices that have children are called internal vertices. The root is an internal vertex unless it is the only vertex in the graph, in which case it is a leaf.

Supportive Theorem:

For any positive integer n, if T is a full binary tree with n internal vertices, then T has n + 1 leaves and a total of 2n + 1 vertices.

case 1:

      O  <- 1 internal node as well as root
     / \
    O   O <- 2 Leaf Nodes

case 2: Trivial Tree

      O <- 0 internal vertices (no internal vertices) , this is leaf

这篇关于根节点是内部节点吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！