2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 помогите пожалуйста с задачей по информатике...
Сообщение30.01.2012, 23:43 
Восстановите полное бинарное дерево по прямому порядку и опишите его прохождение в обратном и симметричном порядке.

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

 
 
 
 Re: помогите пожалуйста с задачей по информатике...
Сообщение31.01.2012, 02:11 
Напомните, что подразумевается, скажем, под прямым порядком?

 
 
 
 Re: помогите пожалуйста с задачей по информатике...
Сообщение31.01.2012, 11:10 
Прямой порядок прохождения бинарного дерева
1.попасть в корень
2.пройти в прямом порядке левое поддерево
3.пройти в прямом порядке правое поддерево

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

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

 
 
 
 Re: помогите пожалуйста с задачей по информатике...
Сообщение31.01.2012, 22:22 
Ok, всё правильно. (Правда ещё четвертый обход в ширину до кучи забыли. :) )

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

 
 
 
 Re: помогите пожалуйста с задачей по информатике...
Сообщение01.02.2012, 01:55 
Ну хорошо, чтобы не тянуть кота за хвост, намечу один из возможных путей для решения вашей задачки.

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

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

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

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

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

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group