Что такое "внутренний node" в двоичном дереве поиска?

Я очищаю интернет для определения термина "Внутренний Node". Я не могу найти краткое определение. Каждый источник, который я ищу, использует термин, не определяя его, и использование не дает правильного определения того, что на самом деле является внутренним node.

Вот два места, в которых я в основном смотрю: http://planetmath.org/encyclopedia/ExternalNode.html предполагает, что внутренние узлы являются узлами, которые имеют два поддерева, которые не являются нулевыми, но не говорят, какие узлы в исходном дереве внутренняя и внешняя.

http://www.math.bas.bg/~nkirov/2008/NETB201/slides/ch06/ch06-2.html, кажется, намекает, что внутренние узлы существуют только в правильных бинарных деревьях и не дают много полезной информации о них.

Что на самом деле является внутренним node!?

Ответ 1

     I         ROOT (root is also an INTERNAL NODE, unless it is leaf)
   /   \
  I     I      INTERNAL NODES
 /     / \
o     o   o    EXTERNAL NODES (or leaves)

Как показывает замечательная картина, внутренние узлы расположены между корнем дерева и листьями. Обратите внимание, что корень также является внутренним node, за исключением случая, когда он является единственным node дерева.

Что говорит на одном из сайтов о внутреннем node, имеющем два дочерних элемента, для дерева является полным двоичным деревом, а не для node для внутреннего.

Ответ 2

Насколько я понимаю, это node, который не является листом.

Ответ 3

Внутренний node или внутренний node - любой node дерева с дочерними узлами и, следовательно, не является листом node. промежуточный node между корнем и узлы листа называются внутренними node.

Источник: http://en.wikipedia.org/wiki/Tree_data_structure

Ответ 4

Из "Введение в алгоритмы", под редакцией Томаса Х Кормена:

A node без какого-либо дочернего элемента называется "leaf node". Не-лист node является 'internal node'.

Ответ 5

Самый верный ответ неверен. Согласно математическим структурам для компьютерной науки Джудит Герстинг, внутренний node - это "A node без каких-либо дочерних элементов, называется листом дерева; все нелицы называются внутренними узлами"

Итак, например (I = INTERNAL NODE): I / \ * I /\ * *

Ответ 6

Внутренний node (также известный как внутренний node, inode для short или branch node) является любым node дерева, имеющего дочерние узлы. Аналогично, внешний node (также известный как внешний node, лист node или терминал node) - это любой node, у которого нет дочерних узлов.

быстро и просто.

Ответ 7

Внутренний node: a node, который не является корнем и имеет хотя бы один дочерний элемент.

Ответ 8

Как правило, внутренним node является любой node, который не является листом (a node без детей).

В расширенных бинарных деревьях (также деревья сравнения) внутренние узлы имеют два дочерних элемента, потому что каждый внутренний node соответствует сравнению, которое должно быть выполнено [The Art of Computer Programming (TAoCP) vol.3 Сортировка и поиск, обсуждение и рисунок в разделе 5.3.1, стр .181 (ред. 2). Кстати, использование этих деревьев для представления пар (и байтов) для турниров по ликвидации рассматривается в разделе 5.4.1 этого материала.]

Диаграмма Vinko отражает это различие, хотя корень node также всегда является либо внутренним node, либо листом node, в дополнение к тому, что он является единственным node без родителя.

Существует более широкое обсуждение в работе Кнута информационных структур и свойств деревьев [TAoCP vol.1 Фундаментальные алгоритмы, обсуждение длин путей в деревьях в разделе 2.3.4.5, p.p. 399-406 (ред. 3), включая упражнения (многие из них выработаны в конце книги)].

Полезно заметить, что деревья двоичного поиска (где внутренние узлы также содержат одиночные значения, а также до двух детей) несколько отличаются [TAoCP vol.3, раздел 6.2.2]. Номенклатура все еще работает.

Ответ 9

Двоичное дерево может иметь нуль, один узел и может иметь максимум два узла. Бинарное дерево имеет левый node и правый node сам по себе.

Ответ 10

Внутренний node или внутренний node - это любой node дерева с дочерними узлами и, следовательно, не является листом node или промежуточным node между корневым и листовым узлами называется внутренний node

Ответ 11

A node, который имеет хотя бы один дочерний элемент.

Ответ 12

Я внутренний node не включает корень. И полное двоичное дерево, как терминология, говорит, что каждый внутренний node должен иметь точные 2 узла. Но в простом двоичном дереве каждый внутренний node имеет почти два узла, т.е. Он не может содержать более двух узлов, но менее 2 допустимо

Ответ 13

Внутренний node - a node с хотя бы одним ребенком. Внешний node - a node без детей.