Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

03.03.2013, 23:13. Просмотров 871. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.03.2013, 23:13
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Бинарное поисковое дерево. Максимальные пути (C++):

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру - C++
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру. вот...

Поисковое дерево - C++
Всем здравствуйте! Помогите, пожалуйста. Необходимо в c++ сгенерировать 22 неповторяющихся трехзначных числа и составить поисковое дерево,...

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

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой - C++
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Бинарное дерево - C++
Необходимо построить бинарное дерево с методами inorder_tree_walk, tree_search, tree_minimum, tree_successor, tree_insert и tree_delete....

Бинарное дерево - C++
Подскажите алгоритм распечатки дерева на экран горизонтально, не вертикально, как обычно это делают. struct tree { int k;...

1
АннаАнна
1 / 1 / 0
Регистрация: 15.09.2014
Сообщений: 10
14.02.2016, 15:28 #2
Анжи, понимаю, что уже много времени прошло, но может вы помните, в чем тогда была ваша ошибка?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.02.2016, 15:28
Привет! Вот еще темы с ответами:

Бинарное дерево - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; int last; void add(double volue) { //double *arr = new...

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

Бинарное дерево - C++
Разработать и реализовать на языке С следующие функции работой с бинарным деревом: 1. Создание пустого дерева 2. Добавление элемента в...

Дерево бинарное - C++
Интересует вопрос, при добавлении нового элемента куда я его должен буду помещать, на какую ветку. Допустим есть дерево с корнем 5 и...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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