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

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

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

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

03.03.2013, 23:13. Просмотров 825. Ответов 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++ сгенерировать 22 неповторяющихся трехзначных числа и составить поисковое дерево,...

Составить поисковое дерево - C++
Короче программа должна из случайно сформированного массива mas1, составить поисковое дерево(то бишь программа должна сделать так чтобы в...

Бинарное дерево из слов - C++
Вроде разобралась в принципе заполнения обычного бинарного дерева из чисел. но как быть в случае,если дерево необходимо заполнить...

Бинарное дерево. Поиск. - C++
Здравствуйте. Дано задание, создать бинарное дерево с возможностью добавления, удаления элементов и поиск. Знаю, что тут ничего сложного и...

STL бинарное дерево - C++
Доброго времени суток!:) Изучаю STL, пока поверхностно прошелся по контейнерам, но не встретил деревьев... хотя set, multiset, map и...

ребят!)бинарное дерево - C++
может кто знает как в С++ в программу впихнуть переводчик...??с русского на английский??может кто делал уже помогите..приведите пример хотя...

Класс бинарное дерево - C++
Здравствуйте. Требуется написать англо-русский словарь на основе бинарного дерева. Не полностью понимаю, как будет выглядеть класс....

Переделать в бинарное дерево - C++
#include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; struct Node{ int info; Node* next; }; class Spisok { ...

Создать бинарное дерево - C++
Есть обычное дерево. Узел описывается struct nod int Value; int Number_Of_Sons; nod *Son Число сыновей может быть до пяти. ...

Структуры. Бинарное дерево. - C++
Поставлена такая задача. Является ли двоичное дерево линейным списком вершин? Реализовать надо на динамических структурах. PS....


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

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

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