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

Question

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

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

Answer 1

Да и да.

Answer 2

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

(изменяемое) двоичное дерево, BiTree, может быть в пустом состоянии или не пустым состояние:

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

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

Answer 3

Какое пустое дерево, конечно, зависит от вашей реализации, равно как и значение слова «действительный», но в целом я бы сказал «да» на оба вопроса. Пустое дерево представляет случай, когда набор сущностей, в который вы вставили, пуст, а один узел - случай, когда набор содержит одну сущность.

Answer 4

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

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

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

MyTree tree = null

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

Answer 5

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

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

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

Да. Это тройник с одним элементом.

Answer 6

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

Answer 7

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

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