Двоичные деревья

[arseniiv]

Ну, мне кажется, что указатель, но давайте ещё и позицию найдём. Надеюсь, что-то из двух пойдёт.

Извините, поиск в ширину не годится, если элементы есть в нелистьях. У вас они же там есть?

Нужен симметричный обход дерева. Это значит, посещаем сначала левое поддерево, потом вершину текущего дерева, потом правое поддерево. Если мы будем возвращать количество обойдённых узлов, можно будет найти индекс того, который нам нужен: он является корнем какого-нибудь поддерева. Если при проверке, равно ли начение в корне данному, вышло, что да — вернём как индекс (начинающийся с нуля) количество уже обойдённых вершин, что вернёт нам функция обхода, применённая к левому поддереву. Если не вышло, то возвратим сумму количества обойдённых в левом и правом поддеревьях узлов и ещё единицы (за счёт корня).

[Alexu007]

Что представляет из себя дерево? Как там данные организованы? Мне кажется, если знать ответы на эти вопросы, то и решить задачу труда не составит.

[arseniiv]

А недосуг заглянуть на предыдущие страницы?

-- Вт дек 27, 2011 18:50:54 --

Да и решение я уже привёл.

[denis_stell]

arseniiv
Задание про адрес здал,всё таки нужно было только указатель найти,а не позицию
Стыдно говорить,но у меня проблемы начались с нахождением суммы внутренних узлов дерева

[arseniiv]

(Точнее, суммы знаений узлов.) А с рекурсивной или нерекурсивной процедурой (вроде же две надо было сделать), или с обоими?

[denis_stell]

arseniiv
рекурсивную подпрограмму ,для суммы
нерекурсивную - для нахождения адреса
поэтому для нерекурсивной

[arseniiv]

Извините, я так и не понял, рекурсивную или нерекурсивную.

Ну начнём с рекурсивной. Как не залезать в листья — уже разобрались. Теперь я тут на псевдокоде напишу функцию, потому что не знаю, как промежуточное написать, и пусть меня модераторы скушают.

sum(Node^ a)

if (a = nil) or ((a^.left = nil) and (a^.right = nil))
    // передали несуществующее поддерево, или попали в лист
    return 0
else
    // сумма составляется из «подсумм» и числа в вершине
    return sum(a^.left) + sum(a^.right) + a^.value

Если теперь это надо нерекурсивным, используем, например, поиск в глубину. Понадобится стек из Node^ и, конечно, переменная, накпаливающая сумму.
Сначала в стек положим корень дерева. Потом будем повторять одно и тоже, пока в стеке будет хоть один элемент: возьмём верхний элемент и, если он не лист, добавим число, хранящееся в нём, к сумме, а затем положим на стек вершину левого поддерева, если она не nil, а затем вершину правого, если она тоже не nil (можно и в обратном порядке). Собственно, может даже показаться проще, чем рекурсией.