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

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

Войти
Регистрация
Восстановить пароль
 
Анжи
0 / 0 / 0
Регистрация: 28.02.2013
Сообщений: 11
#1

Бинарное поисковое дерево. Максимальные пути - C++

03.03.2013, 23:13. Просмотров 807. Ответов 1
Метки нет (Все метки)

Помогите пожалуйста!

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

Алгоритм таков. Обратным обходом расставляем метки высоты и метки суммы вершин сыновей. Далее необходимо найти вершины с максимальной суммой, из них самую высокую и удалить ее.

Расставила метки, а вот как найти вершины с максимальной суммой и из них выбрать... Уже крыша едет, не соображаю. Помогите кто может!

Вот что у меня пока вышло

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <fstream>
using namespace std;
 
struct  Tree
{
    int value;
    int high;
    int max;
    Tree *Left;
    Tree *Right;
}
*Root = NULL; // указатель на вершину
 
void AddRoot(Tree* tree, int value) // добавление конкретного узла дерева
{
    if(value < tree->value)
    { 
        if(tree->Left != NULL) // если значение меньше, двигаемся по "левой ветке"
            AddRoot(tree->Left, value);
        else
        {  
            tree->Left = new Tree;
            tree->Left->value = value;
            tree->Left->Left = NULL;
            tree->Left->Right = NULL;
        }
    }
 
    if(value > tree->value) // иначе двигаемся по правой 
    { 
        if(tree->Right != NULL)
            AddRoot(tree->Right, value);
        else
        {
            tree->Right = new Tree;
            tree->Right->value = value;
            tree->Right->Left=NULL;
            tree->Right->Right=NULL;
        }
    }
 
    if(value == tree->value)                
        cout<< value<< " is already in tree"<< endl;
}
void add_Tree(int value)
{
    if(Root == NULL) // если дерево пустое - создадим первый узел
    {
       Root = new Tree;
       Root->value = value;
       Root->Left = NULL;
       Root->Right = NULL;
    }
    else
        AddRoot(Root, value); // если в вершине уже что-то есть - добавляем слева или справа 
}
int High(Tree* T)
{
     int a = 1, b = 0, c;
     if (T == NULL)
        return 0;
     c = High(T->Left);
     if (c > b)
         b = c;
     c = High(T->Right);
     if (c >b)
         b = c;
     return a + b;
}
int FindMaxHigh( Tree *T)
{
    int a = 1, b = 0, c;
     if (T == NULL)
        return 0;
     c = High(T->Left);
     b = High(T->Right);
     return c + b;
};
void Obhod1 (Tree* T)
{     
    if (T != NULL)
    {   
        if(T->Left !=0) Obhod1(T->Left);        
        if  (T->Right !=0) Obhod1(T->Right);
        
        T->high= High(T)-1;
        T->max=FindMaxHigh(T);
 
        cout<<T->value<<" "<<T->high<<" "<<T->max<<endl;
    }
};
void Out(Tree *T, ofstream &out)
 {
     if(T!=NULL)
     {
         out<<T->value<<"\r\n";
         Out(T->Left, out);
         Out(T->Right, out);
     }
 };
void print(Tree* T)
{   
    if (T != NULL)
    {   
        cout<< T->value<< " ";
        if(T->Left !=0) print(T->Left);
        if  (T->Right !=0) print(T->Right);
    }
};
 
int main()
{
    setlocale (LC_ALL, "Russian");
 
    Tree *T=new Tree;
    int el;     
    ifstream in("in.txt");
    if (in.bad()) return 1;
        while(!in.eof() && in>> el)
            add_Tree (el);     
        in.close();
 
    ofstream out("out.txt");
    Out(Root, out);
    print (Root);
    cout<<endl;
    Obhod1(Root);
    out.close();
    system("pause");
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.03.2013, 23:13     Бинарное поисковое дерево. Максимальные пути
Посмотрите здесь:

Бинарное дерево C++
C++ Бинарное дерево
Бинарное дерево C++
Бинарное дерево C++
бинарное дерево C++
C++ Бинарное дерево
C++ Составить поисковое дерево
Бинарное дерево C++
C++ Бинарное дерево
C++ Бинарное дерево
C++ Поисковое дерево
C++ Бинарное дерево

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
АннаАнна
1 / 1 / 0
Регистрация: 15.09.2014
Сообщений: 10
14.02.2016, 15:28     Бинарное поисковое дерево. Максимальные пути #2
Анжи, понимаю, что уже много времени прошло, но может вы помните, в чем тогда была ваша ошибка?
Yandex
Объявления
14.02.2016, 15:28     Бинарное поисковое дерево. Максимальные пути
Ответ Создать тему
Опции темы

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