рекурсивно найти среднее значение двоичных значений дерева псевдокод

Question

Мне нужно найти среднее значение двоичного дерева рекурсивно.

Это псевдо-код в порядке?

avg (T) 
if (|T| = 1) 
    return value 
sumleft = sumleft + avg(Tleft) 
sumright = sumright + avg(Tright) 
sum = value + sumleft + sumright 
return sum/(|Tleft| + |Tright| +1) 

Answer 1

Нет, этот код является неправильным. В рекурсивных вызовах вызываемый абонент возвращает [*] в среднем, тогда как вызывающий обслуживает его, как если бы это было сумма.

[*] Хорошо, если бы это было правильно, а это не так.

Answer 2

Как сказал NPE, код неверен, поскольку функция возвращает среднее значение, которое вызывающий использует как сумму. Простое исправление в код псевдо будет:

avg(T) = 
    if (|T| = 1) 
    return value 
    sumleft = |Tleft | * avg(Tleft) 
    sumright = |Tright| * avg(Tright) 
    sum = value + sumleft + sumright 
    return sum/(|Tleft| + |Tright| + 1) 

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

sum(T) = 
    if (|T| = 1) 
    return value 
    return sum(Tleft) + value + sum(Tright) 
avg(T) = 
    return sum(T)/|T|