Допустимы ли пустые двоичные деревья поиска?

Question

У меня есть два вопроса относительно бинарных деревьев поиска, оба о пустых деревьях.

1. Допустимо ли пустое дерево (null)?
2. Допустим ли корневой узел без дочерних элементов?

Answer 1

Да, и еще раз да.

Answer 2

Что именно представляет собой пустое дерево, конечно, зависит от вашей реализации, как и значение слова "действительный", но в целом я бы сказал "да" на оба вопроса.Пустое дерево представляет случай, когда набор объектов, которые вас интересуют, пуст, а одиночный узел - случай, когда набор содержит один объект.

Answer 3

Один узел без дочерних элементов, безусловно, допустим и в соответствии с Бинарная Древовидная структура:

(Изменяемое) двоичное дерево, BITree, может находиться в пустом или непустом состоянии состояние:

• Когда он пуст, он не содержит никаких данных.
• Когда он не пуст, он содержит объект данных, называемый корневым элементом, и 2 различных объекта BITree, называемых левым поддеревом и правым поддеревом.

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

Answer 4

Допустимо ли пустое дерево (null)?

Нет никакого дерева, если оно пустое.Следовательно, вопрос о достоверности не возникает.

Допустим ли корневой узел без дочерних элементов?

ДА.Это футболка, в которой есть только один элемент.

Answer 5

Я думаю, ты смешиваешь яблоки и апельсины:

1. null является значением в некоторых языках программирования, и оно связано с конкретным представлением вашей реализации структуры данных
2. "Пусто" - это свойство абстрактной структуры данных, которую мы называем "бинарным деревом поиска".

Итак, дерево - это упорядоченный набор:ни больше, ни меньше.Конечно, набор может быть пустым!Это означает, что в вашем реализация, что - то похожее на:

MyTree tree = null

представлять собой пустое дерево?Ну, это зависит от вашей модели.Вы можете подумать, например, что пустое поддерево должно быть представлено узлом без значения и со ссылками на обнуленные листья:в этой модели a null указатель не имеет смысла с логической точки зрения.Но это всего лишь один приближайся!Программировать с помощью подхода, основанного на sentinel, приятно, но он требует большого объема памяти:затем вы можете моделировать пустые узлы, используя только null.В этом случае a null указателем может быть пустое дерево.

Answer 6

Двоичное дерево может быть определено рекурсивно как:

A single node with either no children, or with two children - 
each of which is a binary tree.

Answer 7

Да, оба условия верны.Для двоичного дерева каждый узел может иметь ноль, одного или двух дочерних элементов.Если дерево имеет только корневой узел и никаких других узлов нет, то оно называется НУЛЕВЫМ деревом.