Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
erioik
1 / 1 / 0
Регистрация: 22.10.2010
Сообщений: 26
#1

Деревья. - C++

27.03.2012, 22:31. Просмотров 421. Ответов 4
Метки нет (Все метки)

Условие
Найти и удалить (правым удалением), если существует, среднюю по значению из вершин дерева, у которых количество потомков в левом поддереве отличается от количества потомков в правом поддереве наибольшим образом.
Если у вершины отсутствует некоторое поддерево, то количество потомков в этом поддереве будем полагать равным 0.

Входные данные
tst.in содержит последовательность ключей дерева.

Выходные данные
tst.out содержит массив вершин, полученный прямым левым обходом итогового дерева.

Пример
tst.in
50
40
60
30
55
70
27
35
40
65
80
30

tst.out
50
30
27
35
60
55
70
65
80
Миниатюры
Деревья.  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.03.2012, 22:31     Деревья.
Посмотрите здесь:

деревья C++
деревья на С++ C++
деревья C++
C++ деревья
Деревья C++
C++ деревья
C++ Деревья
C++ Деревья
деревья C++
Деревья C++
Деревья C++
Деревья C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
27.03.2012, 22:41     Деревья. #2
Ну и? У тебя хоть код дерева без этих плясок с удалением есть?
erioik
1 / 1 / 0
Регистрация: 22.10.2010
Сообщений: 26
27.03.2012, 22:57  [ТС]     Деревья. #3
Да. мне бы танец исполнить.
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
27.03.2012, 23:01     Деревья. #4
Цитата Сообщение от erioik Посмотреть сообщение
Да.
Если да, то выкладывай! Быстро! Чего ж ты не выложил сразу свои наработки?
erioik
1 / 1 / 0
Регистрация: 22.10.2010
Сообщений: 26
27.03.2012, 23:25  [ТС]     Деревья. #5
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Если да, то выкладывай! Быстро! Чего ж ты не выложил сразу свои наработки?
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
108
109
110
#include <iostream>
#include <fstream>
using namespace std;
 
struct node
{
    int key;
    node *left;
    node *right;
};
class Tree
{
private:
    node *root;
public:
    int h;
    int mW;
    int toDel;
    ofstream out;
    Tree (){root = NULL;toDel=-1;h=0;out.open("out.txt",ios::out);}
    ~Tree(){out.close();}
    node** getTree (){return &root;}
    void built();
    void add (node**, int);
    void obhod (node**);
    void del (node **,int);
    void del1 (node **,node **);
};
    void Tree::built()
    {
        ifstream in ("in.txt");
        int el;
        in>>el;
        while (in)
        {
            add (&root,el);
            in>>el;
        }
        in.close();
    }
    void Tree::add(node** w,int x)
    {
        if (*w==NULL)
        {
            *w = new (node);
            (**w).key=x;
            (**w).left=NULL;
            (**w).right=NULL;
        }
        else
        {
            if (x < (**w).key)
            {
                add (&(**w).left, x);
            }
            if (x > (**w).key)
            {
                add (&(**w).right, x);
            }
        }
    }
    void Tree::obhod(node** w)
    {
        if (*w != NULL)
        {
            out<<((**w).key)<<endl;
            obhod (&(**w).left);
            obhod (&(**w).right);
        }
    }
 
void Tree::del (node **w,int k)
{
  node *q;
 
  if  (*w==NULL) {}
  else
     if  (k<(**w).key) del (&((**w).left),k);
     else
        if  (k>(**w).key) del (&((**w).right),k);
        else
          {
                    q = *w;
                    if  ((*q).right==NULL) {*w = (*q).left; delete q;}
                    else
                     if  ((*q).left==NULL) { *w = (*q).right; delete q; }
                     else  del1 (&((*q).right),&q);
          }
}
 
void Tree::del1 (node **r,node **q)
{
  node *s;
 
  if  ((**r).left==NULL)
  {
    (**q).key = (**r).key;
    *q = *r;
    s = *r; *r = (**r).right; delete s;
  }
  else  del1 (&((**r).left), q);
}
 
    int main ()
    {
        Tree A;
        A.built();
        A.obhod(A.getTree());
        return 0;
    }
Добавлено через 16 минут
кстати, удалить среднюю по значению величину, т.е. если если в итоге получается нечетное количество вершин с одинаковой разницой, то удалить нужно среднюю из них. если же их количество четно - ничего делать не нужно.
Yandex
Объявления
27.03.2012, 23:25     Деревья.
Ответ Создать тему
Опции темы

Текущее время: 03:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru