Что такое & # 8220; внутренний узел & # 8221; в бинарном дереве поиска?

StackOverflow https://stackoverflow.com/questions/265809

  •  06-07-2019
  •  | 
  •  

Вопрос

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

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

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

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

Это было полезно?

Решение 

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

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

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

Другие советы

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

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

  

Узел без дочернего элемента называется «конечным узлом». Нелистовый узел является   'внутренний узел'.

  

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

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

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

Так, например (I = ВНУТРЕННЕЕ УЗЕЛ): <Код>    я   / \  * Я      / \     * *

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

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

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

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

В расширенных бинарных деревьях (также деревьях сравнения) все внутренние узлы имеют двух дочерних элементов, поскольку каждый внутренний узел соответствует сравнению, которое необходимо выполнить [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]. Номенклатура все еще работает, хотя.

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

Внутренний узел & # 8211; узел с хотя бы одним потомком. Внешний узел & # 8211; узел без детей.

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top