помогите пожалуйста с задачей по информатике...

[evgen07]

Восстановите полное бинарное дерево по прямому порядку и опишите его прохождение в обратном и симметричном порядке.

помогите пожалуйста написать программу на Си...=(((

[Circiter]

Напомните, что подразумевается, скажем, под прямым порядком?

[evgen07]

Прямой порядок прохождения бинарного дерева
1.попасть в корень
2.пройти в прямом порядке левое поддерево
3.пройти в прямом порядке правое поддерево

Прохождение бинарного дерева в обратном порядке
1.пройти в обратном порядке левое поддерево
2.пройти в обратном порядке правое поддерево
3.попасть в корень

Прохождение бинарного дерева в симметричном порядке
1.пройти в симметричном порядке левое поддерево
2.попасть в корень
3.пройти в симметричном порядке правое поддерево

[Circiter]

Ok, всё правильно. (Правда ещё четвертый обход в ширину до кучи забыли. :) )

Следующий вопрос таков, а что называется полным двоичным деревом? Заметьте, что слово "полное" крайне важно в вашей задаче -- без него она, если не ошибаюсь, не имеет (однозначного) решения. Рекомендую вам нарисовать на бумажке какое-нибудь полное дерево, выполнить прямой обход дерева и выписать полученную последовательность вершин. Закономерность (а значит и намек на решение) улавливается достаточно легко.

[Circiter]

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

Допустим, вы написали код для обхода двоичного дерева в прямом порядке. Этот алгоритм можно немного переделать, а именно, вместо того, чтобы выводить узлы существующего дерева мы будем эти узлы создавать -- сначала корень, потом (рекурсивно) левое поддерево, затем правое поддерево. Обязательно в таком порядке, т.е. сверху-вниз и слева-направо.

Этот алгоритм будет строить пустое полное дерево, но нам нужно его ещё и заполнять данными из входной строки. Для этого достаточно к коду создания каждого узла добавить ещё и код чтения очередного символа входной последовательности, а как только символы закончатся, построение дерева следует завершить.

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

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

P.S.: Я мог что-то и упустить, давайте попробуем сначала этот способ, а потом может быть ещё кто-нибудь чего-нибудь ценного да и подскажет.