Member 14531119 Ответов: 3

Является ли эта функция подсчетом суммы левых ребер двоичного дерева?

Что (x)
Если (X=null)
Возврат -1

Еще
L=что(слева(x))+1
If (right(x))=null)
Возвращение Л

Else return L + what(right(x))

Что я уже пробовал:

Все, что следует
What (x)
    If (X=null)
       Return -1

Else
      L=what(left(x))+1
      If (right(x))=null)
           Return L

Else return L + what(right(x))

Dave Kreskowiak

Что это за чертовщина? Это не C/C++, оооочень.....

Stefan_Lang

- Что это за чертовщина?"
Это странно. По - видимому, ' = ' может означать как сравнение, так и присвоение-удачи авторам компилятора! ;-p

3 Ответов

Рейтинг:
2

OriginalGriff

Нет. Я понятия не имею, на каком языке это написано, но, вероятно, он не будет компилироваться в нем - если ничего другого компиляторы не придирчивы к количеству открытых скобок, соответствующих количеству закрытых скобок, так что это:

If (right(x))=null)
Не будет компилироваться ни на одном языке.
На первый взгляд, это какой-то псевдокод, и вам нужно будет реализовать его в C++, чтобы проверить его должным образом.

И тестирование - это часть вашей задачи, наряду с устранением любых возникающих проблем.

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

Рейтинг:
18

Stefan_Lang

Я понятия не имею, на каком языке это должно быть, но я рискну предположить, что этот код может сделать:

1. "Что" - это имя функции, которая принимает один аргумент и возвращает некоторое значение

2. Судя по названию этой темы, x, вероятно, является двоичным деревом.

3. "If (X=null)", вероятно, относится к строчному параметру функции x - либо это опечатка, либо язык не зависит от регистра.

4. отступ вводит в заблуждение - это двойное вложенное if/else, последнее else должно быть отступом;

5. существуют вспомогательные функции left(..) и right (..), которые, вероятно, доставляют левую и правую ветви x соответственно.

6. Есть три возможных пути:
а) если x равно нулю, то результат равен -1
Б) если x не равно нулю и нет правой ветви, то результат рекурсивно вычисляется из чего(left_branch_of_x) и добавляется +1. В связи с этим возникает вопрос: для чего нужен +1?
в) Если x не равно нулю и существует правая ветвь, то результат рекурсивно вычисляется как сумма What() из обеих ветвей. Плюс 1.

7. интересным моментом в пункте 6 является то, что случай, когда левая ветвь является нулевой, не рассматривается: когда это произойдет, What() будет вызван с нулевым аргументом, что приведет к возвращаемому значению -1. На один уровень выше стека вызовов этот -1 нейтрализует +1 из суммирования, и возвращаемое значение будет результатом того, что() применяется к правой ветви.

8. Теперь давайте применим идеи из 6. и 7. в обратном направлении, от основания дерева:
а) на нижнем уровне и левая, и правая ветви равны нулю, поэтому результатом будет то, что(null)+1 = -1+1 = 0
Б) на один уровень выше мы имеем один из трех случаев: левая ветвь = null, правая ветвь = null, или обе ветви не являются null. Ветви, которые не являются нулевыми, дают 0 в качестве результата, поэтому возможные результаты уровня 1 таковы: (null)+1+0 = 0, если левая ветвь равна нулю, 0+1 = 1, если правая ветвь равна нулю, и 0+1+0 = 1, если обе ветви не равны нулю.
До сих пор остается в силе тезис о том, что результатом является число левых ветвей.
в) на уровне N мы имеем, опять же, три случая:
(1) левая ветвь=null -> результат равен -1+1+что(правая ветвь) = что(правая ветвь)
(2) левая ветвь не равна нулю, а правая ветвь равна нулю -> результат такой, что(левая ветвь)+1
(3) оба не нулевые -> результат-это то, что(левая ветвь)+1+что(правая ветвь)
Во всех трех случаях, если рекурсивный вызов функции What() выдает число левых ветвей, то результатом на этом уровне будет опять-таки число левых ветвей.

Результат: да, учитывая предположения от 1. до 5., эта функция вычисляет количество левых ветвей двоичного дерева.

Рейтинг:
0

KarstenK

Вам нужно узнать об этом бинарное дерево сначала, чтобы понять задачу правильно, чем вам нужно посетить некоторые Изучите учебник по C++ .

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