Рекурсия: равномерное размещение вершин дерева на экране

@utwo · Регистрация: 10.10.2009

Студворк — интернет-сервис помощи студентам

Всем привет! С праздниками!

Возникли проблемы с следующей задачкой. С чего начать?
Может какой-нибудь сырой код для наглядности и понимания?

Прoгрaммa oтoбрaжaeт нa экрaнe cтруктуру дaнных - дeрeвo.
Для рaвнoмeрнoгo рaзмeщeния вeршин прoгрaммa дoлжнa «знaть»
для кaждoй вeршины интeрвaл пoзиций экрaнa, кoтoрый выдeлeн
для дaннoгo пoддeрeвa, и кoличecтвo вeршин в пoддeрeвe. caмo
дeрeвo мoжнo зaдaть cтaтичecки (инициaлизaция).

Спасибо за любой ответ!

@Aye Aye · 07.01.2010, 15:51

старо как мир:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct node // узел дерева
{
         int info; //значние хранимое узлом
         node *left, right;//леове, правое поддерево соответственно
};
void print(int n) //само собой void print(int) принадлежит классу или структуре - дереву.
{
      if (right) right->print(n+1); //спускаемся по правой ветке доконца, какапливаем количство отступов (n+1)
      for (int i=0;i<n;i++) cout << "    "; //вот, спустились, дальше нукуда, распечатываем елемент.
      cout << info << endl;                 //когда рекусрсия разворачивается печатаются и все остальные элементы. через которые мы спускались
      if (left) left->print(n+1); //незабывем спуститься и по правой ветке, что бы сделат тоже самое
}
int main()
{
    //...
    tree T;//дерево T
    //заполнение дерева
    T.print(1);//вывод дерева на экран
}

@utwo · 07.01.2010, 16:05 **[ТС]**

Aye Aye
Спасибо Огромное за быстрый ответ! +100

Честно говоря по комментам не совсем понял. Можно по подробнее описать?
Старо как мир? Это потому что уже обсуждалось неоднократно и очень давно. Если не сложно ткните пальцем плз..где и когда.

@Aye Aye · 07.01.2010, 16:27

тыкаю пальцем: ТЫК

без использования классов получится. но будь внимателен, у структур нет деструкторов. надо будет как следует продумать удаление дерва из памяти. (точно так же как у меня в примере, только надо вызвать удаление всех элементов в конце работы с деревом)

@utwo · 07.01.2010, 16:34 **[ТС]**

Сообщение от Aye Aye

тыкаю пальцем: ТЫК

без использования классов получится. но будь внимателен, у структур нет деструкторов. надо будет как следует продумать удаление дерва из памяти. (точно так же как у меня в примере, только надо вызвать удаление всех элементов в конце работы с деревом)

Значит template и class можно заменить на структуры, но только теперь остается корректно удалить дерево.

@Aye Aye · 07.01.2010, 17:01

нет, еще надо будет везде вместо шаблонных типов T и I поставить конкретные типы, int, например.
ну и вообще просмотреть весь код, может еще что то надо поменять... в main() надо удалить конкретизацию шаблонов

@utwo · 10.01.2010, 19:19 **[ТС]**

Aye Aye,
будет возможность помочь переделать код без классов и шаблонов?

Немного переделал код, оставил только функционал добавления и просмотра

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
using namespace std;
 
template <class T,class I> class node
{
      private:
              T x; //ключ
              I info;//информация
              node* LL; //left link
              node* RL; //right link
      public:
             node(){x=0;LL=0;RL=0;};
             ~node()
             {
                  if (LL) LL->~node();
                  if (RL) RL->~node();
                  if (LL) {delete LL; LL=0;}
                  if (RL) {delete RL; RL=0;}
             }
             void putx(T new_x,I new_info){this -> x=new_x;this -> info=new_info;}
             void null_leftlink(){this -> LL=0;}
             void null_rightlink(){this -> RL=0;}
             void add(T new_x, I new_info)
             {
                  if (LL&&(new_x < x)) LL->add(new_x,new_info);
                  if (RL&&(new_x > x)) RL->add(new_x,new_info);
                  
                  if (!LL&&(new_x < x))
                  {
                          node* N=new node;
                          N->x=new_x;
                          N->info=new_info;
                          N->LL=0;
                          N->RL=0;
                          LL=N;
                  }
                  if (!RL&&(new_x > x))
                  {
                          node* N=new node;
                          N->x=new_x;
                          N->info=new_info;
                          N->LL=0;
                          N->RL=0;
                          RL=N;
                  }
             }
             void print(int tab)
             {
                  if (RL) RL-> print(tab + 1);
                     for(int i=1;i!=tab;i++)cout << "  "; cout <<this->x << "-"<< this->info << endl;
                  if(LL) LL->print(tab + 1);      
             }
 
 
};
 
template <class T,class I> class tree
{
      private:
              node <T,I>* link;
      public:
             tree(){link=0;};
             void add(T new_x,I new_info)
             {
                  if (link) link->add(new_x,new_info);
                  else
                  {
                      node<T,I>* N=new node<T,I>;
                      N->putx(new_x,new_info);
                      N->null_leftlink();
                      N->null_rightlink();
                      link=N;
                  }
             };
             void print(){if(link)link->print(1);else cout << "No tree existing\n";}
             
           
          
};
 
int main()
{
 
    tree <int,char> *T=new tree <int,char>; // создание дерева
    //menu
    int choos=0;
    const int exit=3;
    while (choos!=exit)
    {
          cout << "  1-add;\n"
                  "  2-print;\n"
                  "  3-exit;\n"
                  "enter-> "; cin >> choos; system("cls");
          switch (choos){
                 case 1: {
                         int key; //ключ.
                         char val; //значение
                         cout << "enter key: "; cin >> key;
                         cout << "enter int value: "; cin >> val; 
                         T->add(key,val); 
                         break;
                 }
                 case 2: T->print(); break;
          }
    }
    delete T; //удаление дерева, используется деструктор.
}

@Aye Aye · 10.01.2010, 21:32

вот, вместо шаблонных классов структуры:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
using namespace std;
 
struct node
{
             int x; //êëþ÷
             char info;//èíôîðìàöèÿ
             node* LL; //left link
             node* RL; //right link
             node(){x=0;LL=0;RL=0;};
             ~node()
             {
                  if (LL) LL->~node();
                  if (RL) RL->~node();
                  if (LL) {delete LL; LL=0;}
                  if (RL) {delete RL; RL=0;}
             }
             void putx(int new_x,char new_info){this -> x=new_x;this -> info=new_info;}
             void null_leftlink(){this -> LL=0;}
             void null_rightlink(){this -> RL=0;}
             void add(int new_x, char new_info)
             {
                  if (LL&&(new_x < x)) LL->add(new_x,new_info);
                  if (RL&&(new_x > x)) RL->add(new_x,new_info);
                  
                  if (!LL&&(new_x < x))
                  {
                          node* N=new node;
                          N->x=new_x;
                          N->info=new_info;
                          N->LL=0;
                          N->RL=0;
                          LL=N;
                  }
                  if (!RL&&(new_x > x))
                  {
                          node* N=new node;
                          N->x=new_x;
                          N->info=new_info;
                          N->LL=0;
                          N->RL=0;
                          RL=N;
                  }
             }
             void print(int tab)
             {
                  if (RL) RL-> print(tab + 1);
                     for(int i=1;i!=tab;i++)cout << "  "; cout <<this->x << "-"<< this->info << endl;
                  if(LL) LL->print(tab + 1);      
             }
 
 
};
 
struct tree
{
             node* link;
             tree(){link=0;};
             void add(int new_x,char new_info)
             {
                  if (link) link->add(new_x,new_info);
                  else
                  {
                      node* N=new node();
                      N->putx(new_x,new_info);
                      N->null_leftlink();
                      N->null_rightlink();
                      link=N;
                  }
             };
             void print(){if(link)link->print(1);else cout << "No tree existing\n";}
};
 
int main()
{
 
    tree *T=new tree; // ñîçäàíèå äåðåâà
    //menu
    int choos=0;
    const int exit=3;
    while (choos!=exit)
    {
          cout << "  1-add;\n"
                  "  2-print;\n"
                  "  3-exit;\n"
                  "enter-> "; cin >> choos; system("cls");
          switch (choos){
                 case 1: {
                         int key; //êëþ÷.
                         char val; //çíà÷åíèå
                         cout << "enter key: "; cin >> key;
                         cout << "enter int value: "; cin >> val; 
                         T->add(key,val); 
                         break;
                 }
                 case 2: T->print(); break;
                  }
    }
    delete T; //óäàëåíèå äåðåâà, èñïîëüçóåòñÿ äåñòðóêòîð.
}

@utwo · 10.01.2010, 21:38 **[ТС]**

глюк

@utwo · 12.01.2010, 11:08 **[ТС]**

Aye Aye, спасибо большое! Все прекрасно работает!

Но вот теперь нужно внести небольшие изменения:

Элeмeнт дeрeвa coдeржит либo дaнныe (cтрoкa oгрaничeннoй
длины), либo укaзaтeли нa прaвoe и лeвoe пoддeрeвья. Стрoки в
дeрeвe получаются упoрядoчeны. Нaпиcaть функцию включeния нoвoй cтрoки.
Обрaтить внимaниe нa тo, чтo элeмeнт c укaзaтeлями нe coдeржит
дaнных, и при включeнии нoвoй вeршины вeршину c дaнными
cлeдуeт зaмeнить нa вeршину c укaзaтeлями.

Если я правильно понял, дерево мое теперь должны выглядеть таким образом?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@utwo 3 / 3 / 0 Регистрация: 10.10.2009 Сообщений: 108

	Рекурсия: равномерное размещение вершин дерева на экране 07.01.2010, 14:26. Показов 1240. Ответов 9 Метки нет (Все метки) Всем привет! С праздниками! Возникли проблемы с следующей задачкой. С чего начать? Может какой-нибудь сырой код для наглядности и понимания? Прoгрaммa oтoбрaжaeт нa экрaнe cтруктуру дaнных - дeрeвo. Для рaвнoмeрнoгo рaзмeщeния вeршин прoгрaммa дoлжнa «знaть» для кaждoй вeршины интeрвaл пoзиций экрaнa, кoтoрый выдeлeн для дaннoгo пoддeрeвa, и кoличecтвo вeршин в пoддeрeвe. caмo дeрeвo мoжнo зaдaть cтaтичecки (инициaлизaция). Спасибо за любой ответ! 0

@utwo 3 / 3 / 0 Регистрация: 10.10.2009 Сообщений: 108
	07.01.2010, 16:05 [ТС]
	Aye Aye Спасибо Огромное за быстрый ответ! +100 Честно говоря по комментам не совсем понял. Можно по подробнее описать? Старо как мир? Это потому что уже обсуждалось неоднократно и очень давно. Если не сложно ткните пальцем плз..где и когда. 0

@Aye Aye 373 / 287 / 97 Регистрация: 17.12.2009 Сообщений: 567
	07.01.2010, 16:27
	тыкаю пальцем: ТЫК без использования классов получится. но будь внимателен, у структур нет деструкторов. надо будет как следует продумать удаление дерва из памяти. (точно так же как у меня в примере, только надо вызвать удаление всех элементов в конце работы с деревом) 1

@Aye Aye 373 / 287 / 97 Регистрация: 17.12.2009 Сообщений: 567
	07.01.2010, 17:01
	нет, еще надо будет везде вместо шаблонных типов T и I поставить конкретные типы, int, например. ну и вообще просмотреть весь код, может еще что то надо поменять... в main() надо удалить конкретизацию шаблонов 1

@utwo 3 / 3 / 0 Регистрация: 10.10.2009 Сообщений: 108
	10.01.2010, 21:38 [ТС]
	глюк 0

@utwo 3 / 3 / 0 Регистрация: 10.10.2009 Сообщений: 108
	12.01.2010, 11:08 [ТС]
	Aye Aye, спасибо большое! Все прекрасно работает! Но вот теперь нужно внести небольшие изменения: Элeмeнт дeрeвa coдeржит либo дaнныe (cтрoкa oгрaничeннoй длины), либo укaзaтeли нa прaвoe и лeвoe пoддeрeвья. Стрoки в дeрeвe получаются упoрядoчeны. Нaпиcaть функцию включeния нoвoй cтрoки. Обрaтить внимaниe нa тo, чтo элeмeнт c укaзaтeлями нe coдeржит дaнных, и при включeнии нoвoй вeршины вeршину c дaнными cлeдуeт зaмeнить нa вeршину c укaзaтeлями. Если я правильно понял, дерево мое теперь должны выглядеть таким образом? 0