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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ работа с множествами http://www.cyberforum.ru/cpp-beginners/thread799936.html
я думаю что не обходимо задавать их как массивы, не могу разобраться как. Задание звучит так: 3 множества A,B,C уже заданы заранее любые по желанию необходимо выполнить следующие действия и вывести результат A ∩ (B \ C)
C++ Работа с InternetCanonicalizeUrl() в WinInet Подскажите пожалуйста. Почему функция fl = InternetCanonicalizeUrl(sentData,tmpData,count,NULL); не перекодирует строку в Url http://www.cyberforum.ru/cpp-beginners/thread799932.html
C++ Подскажите алгоритм к примеру, пожалуйста ( Дано натуральное число n. Рассчитать P )
Сам пример такой: Дано натуральное число n. Рассчитать P = (1+1/1)*(1+1/2)2*...(1+1/n)n. Мой вопрос заключается в том, что как можно пользуясь циклическим оператором (for) и не используя функции (pow) возносить каждую образующеюся в скобках дробь в степень. Понимаю, что что бы вознести число в степень, надо его умножать само на себя (прошу подсказать как зделать это в программе). Если кому не...
C++ Проблемы с вызовом функции
Проблемы с вызовом 3 функции,тип(Void); Подскажите в чем ошибка. #include <iostream> using namespace std; ////Обьявление char func1(unsigned int); char func2(int,float,double);
C++ Функция которая создаёт прямоугольник http://www.cyberforum.ru/cpp-beginners/thread799919.html
Написать функцию, которая создает прямоугольник из указанных пользователем символов с указанным параметрами
C++ Через функцию определить гласную букву Написать функцию glasn, которая возвращает 1, если символ, полученный функцией в качестве аргумента, является глас ной буквой русского алфавита, и 0 — в противном случае. подробнее

Показать сообщение отдельно
Анжи
0 / 0 / 0
Регистрация: 28.02.2013
Сообщений: 11
03.03.2013, 23:13     Бинарное поисковое дерево. Максимальные пути
Помогите пожалуйста!

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

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

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

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

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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 15:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru