Что такое «внутренний узел» в бинарном дереве поиска?

Question

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

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

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

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

Answer 1

Обычно внутренним узлом является любой узел, который не является листом (узел без дочерних элементов).

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

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

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

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

Answer 2

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

Answer 3

Узел, у которого есть хотя бы один дочерний элемент.