Мне нужно создать рекурсивный алгоритм, чтобы увидеть, является ли двоичное дерево бинарным деревом поиска, а также подсчитать, сколько там полных ветвей (родительский узел с левым и правым дочерними узлами) с предполагаемой глобальной переменной подсчета. Это назначение для моего класса структур данных.
Пока у меня есть
void BST(tree T) {
if (T == null) return
if ( T.left and T.right) {
if (T.left.data < T.data or T.right.data > T.data) {
count = count + 1
BST(T.left)
BST(T.right)
}
}
}
Но я не могу понять это. Я знаю, что этот алгоритм не решит проблему, потому что счет будет равен нулю, если второе утверждение if не соответствует действительности.
Может ли кто-нибудь помочь мне в этом?
algorithms
recursion
trees
OghmaOsiris
источник
источник
<
определяется оператор сравнения на узлах?true
илиfalse
?Ответы:
Как уже отмечали другие в комментариях, у вас действительно есть две несвязанные функции: проверка, является ли дерево деревом поиска, и подсчет полных ветвей. Если это не требуется для конкретного назначения, я бы написал две отдельные функции.
Давайте посмотрим, сколько подсчитывает полные ветви в первую очередь. Это означает подсчет узлов, у которых есть и левый, и правый потомки. Затем вам нужно увеличить счетчик (
count = count + 1
), когда обаT.left
иT.right
ненулевые (неT.left.data
иT.right.data
: данные не имеют значения для этой задачи).Кроме того, вам нужно исследовать левое поддерево, даже если правое поддерево пусто, и вам нужно исследовать правое поддерево, даже если левое поддерево пусто. Так что смотрите, куда вы помещаете рекурсивные вызовы.
Чтобы проверить, является ли дерево поисковым, вам нужно проверить значения данных. У вас уже есть что-то близкое к правильному сравнению; не совсем верно. Напишите несколько примеров деревьев с различными формами (не очень большие, от 2 до 5 узлов) и запустите свой алгоритм на них, чтобы увидеть, что происходит.
Вам все еще нужно найти какое-то место, чтобы поставить результат проверки достоверности. Опять же, посмотрите, где вы делаете рекурсивные вызовы (если вы делаете только эту часть, есть несколько решений, но на этом этапе не беспокойтесь, если вы видите только одно).
Наконец, как только вам удалось написать обе функции по отдельности, и вы проверили их на нескольких примерах, аккуратно соедините их (если этого требует задание).
источник
В таких вещах часто легче думать задом наперед, поэтому сначала подумайте, что вам нужно. Из вашего описания, давайте перечислим их:
Хорошо, это довольно короткий список, это должно быть управляемым. Давайте начнем с пустого метода, и я добавлю описание того, что должно происходить.
Теперь действительность. Как вы проверяете действительность? В чате вы сказали, что дерево действительно, «если ... все левые дети меньше, чем родитель, а правые дети больше, чем родитель». Я уверен, что вы хотели разрешить равенство. Это было бы
t.left.value <= t.value <= t.right.value
.Но что, если один из детей пропал? Из того, что вы сказали, я думаю, вы знаете, что узел все еще действителен, если один из них (или оба отсутствуют). Давайте добавим это, немного перестроив:
Хорошо, теперь мы знаем, действителен ли этот узел. Как мы можем проверить, является ли все дерево действительным? Он не находится в массиве, поэтому мы, вероятно, не можем / не хотим циклически проходить по нему. Ваше задание дает ответ: рекурсия. Но как мы накапливаем ответ, используя рекурсию? У нас есть доступ к трем частям информации, является ли этот узел действительным, и результат вызовов, спрашивающих, действительны ли левый и правый узлы. Очевидно, дерево действительно только в том случае, если все три из них верны.
Если вы обращаете внимание, это даже говорит нам, что наша функция должна вернуть.
Теперь, как мы интегрируем подсчет? Вы говорите, что имеет значение («родительский узел с левыми и правыми дочерними узлами»), и это не должно быть трудно перевести в реальный код. Проверьте, выполняется ли это условие, и увеличьте счетчик соответствующим образом. Просто помните, что это должно быть где-то, где это будет достигаться каждый раз, когда это правда.
И, конечно, я пропустил некоторые детали, такие как условие остановки рекурсии и проверки на ноль.
источник
Мои три комментария выше - три подсказки к проблемам с вашим кодом.
node1.value < node2.value
if
верен, вы уверены, что это то, что вы хотели сделать? Кстати, вы можете перепроверить, что оператор if делает то, что вы хотите.источник