data structures - trees - ¿El nodo raíz es un nodo interno?

trees data structure

Question

Así que he buscado en la web y un par de preguntas aquí en stackoverflow aquí están la definición:

• En general, un nodo interno es cualquier nodo que no es una hoja (un nodo sin hijos)
• Nodo no hoja / No terminal / interno: tiene al menos un nodo hijo o descendiente con un grado no igual a 0
• Por lo que yo entiendo, es un nodo que no es una hoja.

Estaba a punto de concluir que la raíz también es un nodo interno, pero parece haber cierta ambigüedad en su definición como se ve aquí:

¿Qué es un "nodo interno" en un árbol de búsqueda binario?

• Como muestra la maravillosa imagen, los nodos internos son nodos ubicados entre la raíz del árbol y las hojas

Si seguimos esa definición, el nodo raíz no se contará como un nodo interno. Entonces, ¿un nodo raíz es un nodo interno o no?

Answer 1

En mi humilde opinión, cuando se habla de un árbol con más de un nodo, podemos decir que el nodo raíz es un nodo interno. Cuando solo hay un nodo (el nodo raíz), no surge la cuestión del nodo interno. Por lo tanto, podemos decir vacuamente que es un nodo interno.

Answer 2

Sí, el nodo raíz es un nodo interno.
[Más explicación]

Un nodo raíz nunca se llama como un nodo hoja incluso si es el único nodo presente en el árbol. Por ej. si un árbol tiene un solo nodo, entonces decimos que es un árbol con solo nodo raíz, nunca decimos que el árbol tenga un solo nodo de hoja.
Como el nodo interno significa un nodo no hoja y como el nodo raíz nunca se considera nodo hoja, diría que en el caso de nodo único, el nodo raíz es un nodo interno .

Answer 3

Declaración de un libro: Matemáticas discretas y sus aplicaciones - Séptima edición Por Rosen dice:

Los vértices que tienen hijos se llaman vértices internos. La raíz es un vértice interno a menos que sea el único vértice en el gráfico, en cuyo caso es una hoja.

Teorema de apoyo:

Para cualquier entero positivo n, si T es un árbol binario completo con n vértices internos, entonces T tiene n + 1 hojas y un total de 2n + 1 vértices.

caso 1:

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

caso 2: árbol trivial

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