Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 17.11.2010, 18:24   #1
Skilluser
 
Регистрация: 17.11.2010
Сообщений: 7
Восклицание проход по дереву на c++

Добрый вечер всем. препод в качестве проверки моих знаний попросил меня написать программу, которая выдает список всех вышестоящих узлов в дереве)))) вообще без понятия как ее делать, так что прошу помощи... знаю только, что надо рекурсией проходить по дереву и все...
для наглядности:
во вложении пример дерева. программа должна вывести:
e-c-b-a
f-c-b-a
g-d-b-a
h-d-b-a
k-t-a
n-t-a
само дерево построить смогу, а вот алгоритм-врдяли. так что прошу помощи!
Изображения
Тип файла: png 1.png (10.9 Кб, 117 просмотров)
Skilluser вне форума Ответить с цитированием
Старый 17.11.2010, 20:02   #2
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Цитата:
само дерево построить смогу
Программой? Строй!
Все ж зависит от того как ты опишешь структуру элемента дерева.
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 17.11.2010, 22:52   #3
Skilluser
 
Регистрация: 17.11.2010
Сообщений: 7
По умолчанию

Почему программой? вот пример кода (данные другие):

Код:
#include <iostream>
#include <string>
using namespace std;
struct elem;
struct elem{
  string value;
  elem* left;
  elem* right;
};
int main(int argc, char* argv[]){
  elem* root = new elem;
  root->value = "A";
  root->left = new elem;
  root->right = new elem;
  root->left->value = "B";
  root->right->value = "C";
  root->right->left =new elem;
  root->right->right =new elem;
  root->left->left =new elem;
  root->left->right =new elem;
  root->right->left->value ="D";
  root->right->right->value ="E";
  root->left->left->value ="F";
  root->left->right->value ="G";
 
  return 0;
}

Последний раз редактировалось Stilet; 18.11.2010 в 09:22.
Skilluser вне форума Ответить с цитированием
Старый 18.11.2010, 00:02   #4
RUSt88
Участник клуба
 
Регистрация: 29.12.2009
Сообщений: 1,166
По умолчанию

добавь в структуру дерева элементам указатель на родителя и вся задача будет легко решена

или даже без этого, идти нужно от корня дерева, записывать элементы по к-рым проходишься, и так идти до нужного элемента
прогер C\C++\C#\Delphi
ася: [семь 3]-[97]-[1 шесть]
RUSt88 вне форума Ответить с цитированием
Старый 18.11.2010, 00:24   #5
Skilluser
 
Регистрация: 17.11.2010
Сообщений: 7
По умолчанию

Цитата:
Сообщение от RUSt88 Посмотреть сообщение
или даже без этого, идти нужно от корня дерева, записывать элементы по к-рым проходишься, и так идти до нужного элемента
спасибо за ответ, но все же не понял, точнее не знаю, как это сделать... я так понимаю, что по пути к конечному "листу" дерева, надо как-то записывать адрес каждого встречающегося "листа", а потом, дойдя до конца, выводить прошлый адрес. но хз как это сделать. если можно, то покажите готовый код, плиз.
Код:
#include <iostream>
#include <string>
using namespace std;
struct elem;
struct elem{
  string value;
  elem* left;
  elem* right;
};
void prohod(elem *root){
  if (root->left == 0 || root->right ==0){
    ...???
  }
  else{
    ...???
  }
}
int main(int argc, char* argv[]){
  ...
  return 0;
From Stilet: Код Си выделяй тегом по кнопке # а не как PHP.

Последний раз редактировалось Stilet; 18.11.2010 в 09:24.
Skilluser вне форума Ответить с цитированием
Старый 18.11.2010, 01:38   #6
RUSt88
Участник клуба
 
Регистрация: 29.12.2009
Сообщений: 1,166
По умолчанию

держи нямку

Код:
struct elem {
  string data;
  elem *right;
  elem *left;
  elem *parent;
};

void Prohod(elem *tmp, elem *root) {
  elem *t = tmp;
  while (t != root) {
    cout << t->data << " - ";
    t = t->parent;
  }
  cout << root->data;
}
прогер C\C++\C#\Delphi
ася: [семь 3]-[97]-[1 шесть]
RUSt88 вне форума Ответить с цитированием
Старый 18.11.2010, 11:25   #7
Skilluser
 
Регистрация: 17.11.2010
Сообщений: 7
По умолчанию

спасибо еще раз, но препод дал условие: надо проходить по дереву рекурсивно....
а с этим кодом программа почему-то не работает... по-моему условие цикла не правильное, программа просто не осстанавливается и ничего не выводит. ...
Код:
#include <iostream>
#include <string>
using namespace std;
struct elem;
struct elem{
  string value;
  elem* left;
  elem* right;
  elem* parent;
};
int prohod(elem *tmp, elem *root) {
  elem *t = tmp;
  while (t != root) {
    cout << t->value << " - ";
    t = t->parent;
  }
  cout << root->value;
}

int main(int argc, char* argv[]){
  elem* root = new elem;
  root->value = "E";
  root->left = new elem;
  root->right = new elem;
  root->left->value = "B";
  root->right->value = "G";
  root->right->left =new elem;
  root->right->right =new elem;
  root->left->left =new elem;
  root->left->right =new elem;
  root->right->left->value ="F";
  root->right->right->value ="H";
  root->left->left->value ="A";
  root->left->right->value ="C";
  elem* tmp;
  prohod(tmp,root);
  return 0;
}
Skilluser вне форума Ответить с цитированием
Старый 18.11.2010, 17:08   #8
RUSt88
Участник клуба
 
Регистрация: 29.12.2009
Сообщений: 1,166
По умолчанию

ты что вообще передаешь процедуре????
NULL указатель!!! а нужно передать процедуре указатель на элемент, от к-рого нужно сделать проход до корня

Код:
  root->left->right->value ="C";
  elem* tmp = root->left->right;
  prohod(tmp, root);
вот так правильно

Цитата:
int prohod(elem *tmp, elem *root)
а зачем тут функция-то? это просто процедура, ничего не возвращающая, то бишь void
прогер C\C++\C#\Delphi
ася: [семь 3]-[97]-[1 шесть]

Последний раз редактировалось Stilet; 18.11.2010 в 20:39.
RUSt88 вне форума Ответить с цитированием
Старый 18.11.2010, 20:38   #9
casekey
Пользователь
 
Регистрация: 03.11.2010
Сообщений: 95
По умолчанию

Дерево выводим рекурсивно, сначала все левые ветки текущего, затем правые.
За точность не ручаюсь, т.к проверить негде, но подгоняемо вообщем

Код:
void TreeView(elem *root);
{
elem *x;
x = root;
if (x != NULL)
    {
    TreeView(x->left);
    cout << x->value;
    TreeView(x->right);
    }
}
casekey вне форума Ответить с цитированием
Старый 18.11.2010, 23:41   #10
Skilluser
 
Регистрация: 17.11.2010
Сообщений: 7
По умолчанию

Цитата:
Сообщение от casekey Посмотреть сообщение
Дерево выводим рекурсивно, сначала все левые ветки текущего, затем правые.
За точность не ручаюсь, т.к проверить негде, но подгоняемо вообщем

Код:
void TreeView(elem *root);
{
elem *x;
x = root;
if (x != NULL)
    {
    TreeView(x->left);
    cout << x->value;
    TreeView(x->right);
    }
}
это совсем не то, что нужно.. это код простой линеаризации дерева. а мне нужен список вышестоящих узлов...



RUSt88, сделал все, как ты написал.. но выдает ошибку: Ошибка сегментирования(((
Skilluser вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск по бинарному дереву интеграл Общие вопросы C/C++ 3 01.05.2010 11:52
С++. Отыскать проход по лабиринту Romer9999 Помощь студентам 1 17.06.2009 23:33
Проход по дереву. Ozerich Общие вопросы Delphi 1 05.10.2008 17:33
TreeView и PageControl (переключение вкладок по дереву) Nevy Общие вопросы C/C++ 5 17.08.2008 19:17