Является ли null бинарным деревом?

Question

Так я видел несколько примеров, таких как

How to validate a Binary Search Tree?

http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/

Они возвращают 1, или истинное дерево является нулевым. Расширение вопросов немного - если я должен был найти, если TreeSmall является поддеревом TreeBig, а мой TreeSmall - null, должно ли возвращаемое значение checkSubtree(smallTree) истинным или ложным? A true указывает, что TreeSmall был tree со значением null. Для меня это не имеет смысла.

Answer 1

В чистой информатике null является действительным двоичным деревом. Он называется пустым двоичным деревом. Точно так же, как пустой набор все еще является допустимым набором. Кроме того, двоичное дерево с единственным корневым узлом и без детей также является допустимым (но не пустое). См. this Stack Overflow answer для получения дополнительной информации.

В практической реализации есть два способа сделать это.

1. Предположим, что действительное двоичное дерево должно иметь хотя бы один узел и не допускать пустые деревья. У каждого узла нет детей.Все рекурсивные методы в этом дереве не опускаются до уровня null. Скорее, они останавливаются, когда видят, что левый дочерний или правый дочерний узел узла имеет значение NULL. Эта реализация работает до тех пор, пока вы не передадите null в любое место, где ожидается дерево.

2. Предположим, что null является допустимым двоичным деревом (формально, просто пустым деревом). В этой реализации вы сначала проверяете, является ли указатель нулевым, прежде чем выполнять какие-либо операции над ним (например, проверка для детей влево/вправо и т. Д.). Эта реализация работает для любого указателя на дерево. Вы можете свободно передавать нулевые указатели на методы, ожидающие дерева.

Оба способа работы. Преимущество второй реализации заключается в гибкости. Вы можете передать null ко всему, что ожидает дерево, и оно не приведет к возникновению исключения. Первая реализация имеет то преимущество, что не тратит время на спуск на «дочерние узлы», которые являются нулевыми, и вам не нужно использовать нулевые проверки в начале каждой функции/метода, который работает на узле. Вместо этого вам просто нужно выполнить нулевые проверки для детей.

Answer 2

Это зависит от приложения и является вопросом определения.

Edit:

Например Википедия «определяет» а BST следующим образом:

В информатике бинарное дерево поиска (BST), иногда также называют упорядоченную или отсортированный бинарное дерево, является структура данных двоичного дерева на основе узлов, которая обладает следующими свойствами:

• Левое поддерево узла содержит только узлы с ключами, меньшими, чем ключ узла.
• Правильное поддерево узла содержит только узлы с ключами, большими, чем ключ узла.
• Левое и правое поддерево должны также быть двоичным деревом поиска.
• Там не должно быть повторяющихся узлов

Давайте проверим те, для null:

• левое поддерево не существует, так что нет узлов, нарушающих это правило -> проверить
• аналогично первому -> проверить
• , если все эти тесты пройдены, это также проходит, так как оба поддерева имеют значение null -> check
• , конечно, не дублирует -> проверить

Так этим определением null является допустимым BST. Вы можете инвертировать это, также требуя «должен быть один корневой узел». Это не влияет на какие-либо практические свойства BST, но может быть в явном приложении.

Answer 3

Ex falso sequitur quodlibet - так как «null» ничего не значит, его можно интерпретировать как нечто. Это действительно вопрос дизайна. Некоторые люди могут утверждать, что checkSubTree() должен бросить что-то вроде исключения IllegalArgumentException в этом случае. Другим подходом было бы введение специального типа типизированного объекта или экземпляра, который представляет пустое дерево (см. NullObjectPattern). Такой нулевой объект будет деревом по всем учетным записям, например. EmptyTree instanceof Tree, а null instanceof Tree всегда будет ложным.