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

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

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

Деревья С++ (функция, которая получает указатель на корень дерева и возвращает длину самой длинной ветки на дереве) - C++

20.06.2013, 12:37. Просмотров 594. Ответов 4
Метки нет (Все метки)

Здравствуйте!
Помогите, пожалуйста, в написании функции ,которая получает указатель на корень дерева и возвращает длинну самой длинной ветки на дереве , которая заканчивается одним листком и на каждом узле ветви есть только один ''ребенок".
В прикрепленном файле ,например, дерево ,в котором самая длинная ветка это номера-5,7,6.
Заранее благодарна(скоро экзамен).
Миниатюры
Деревья С++ (функция, которая получает указатель на корень дерева и возвращает длину самой длинной ветки на дереве)  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.06.2013, 12:37     Деревья С++ (функция, которая получает указатель на корень дерева и возвращает длину самой длинной ветки на дереве)
Посмотрите здесь:
C++ Нужно вывести на экран содержимое самой длинной ветки бинарного дерева
C++ Функция, которая получает в качестве параметров два целых числа и возвращает сумму
C++ Функция, которая получает два параметра и возвращает результат деления первого параметра на второй
C++ Найти длину самой длинной возрастающей подпоследовательности в массиве
C++ Определить длину самой длинной подстроки из подряд стоящих букв «е»
Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1. C++
C++ Определить длину самой длинной цепочки единиц в переменной unsigned long a
Определить длину самой длинной цепочки единиц в переменной unsigned long a; C++
Найти длину самой длинной последовательности подряд идущих нулевых элементов массива C++
Найти место вхождения в строку самой длинной последовательности пробелов и определить ее длину C++
Вывести количество возрастающих последовательностей в массиве, а также длину самой длинной из них C++
C++ Функция удаления листа (или ветки) бинарного дерева

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
20.06.2013, 13:10     Деревья С++ (функция, которая получает указатель на корень дерева и возвращает длину самой длинной ветки на дереве) #2
нужно делать обход в глубину на дереве.
1aprela
0 / 0 / 0
Регистрация: 06.04.2013
Сообщений: 14
20.06.2013, 13:24  [ТС]     Деревья С++ (функция, которая получает указатель на корень дерева и возвращает длину самой длинной ветки на дереве) #3
Я знаю но функция не работает...
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
20.06.2013, 13:25     Деревья С++ (функция, которая получает указатель на корень дерева и возвращает длину самой длинной ветки на дереве) #4
какая функция? почему я ее не вижу?
1aprela
0 / 0 / 0
Регистрация: 06.04.2013
Сообщений: 14
20.06.2013, 14:54  [ТС]     Деревья С++ (функция, которая получает указатель на корень дерева и возвращает длину самой длинной ветки на дереве) #5
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//-----------------------------------------------------------------------------
//--------------------------Including Section----------------------------------
//-----------------------------------------------------------------------------
#include <iostream>
#include <cmath>
#include <new>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <new>
#include <fstream>
//-----------------------------------------------------------------------------
//------------------------------Using Section----------------------------------
//-----------------------------------------------------------------------------
using std::cin;
using std::cout;
using std::nothrow;
using std::cerr;
using std::endl;
using namespace std;
//-----------------------------------------------------------------------------
//----------------------------Functions Section--------------------------------
//-----------------------------------------------------------------------------
struct Node
{
    int _data;
    struct Node *_left,
                *_right;
};
 
struct Node * BuildTheBST();
void InsertIntoTheBST(struct Node **point_to_root,int num);
struct Node * AllocateNewNode(int num);
int TheLongestBranch( const struct Node *root,double &branch);
void FreeTheSpace(struct Node *&root);
//-----------------------------------------------------------------------------
//------------------------------Main Section-----------------------------------
//-----------------------------------------------------------------------------
int main()
{
    struct Node * root = NULL;
 
    double branch = 0;
 
    root = BuildTheBST();
    TheLongestBranch(root,branch);
    cout << branch;
 
 
    FreeTheSpace(root);
    return(EXIT_SUCCESS);
}
//-----------------------------------------------------------------------------
//-----------Function that reads the numbers into BST--------------------------
//-----------------------------------------------------------------------------
struct Node * BuildTheBST()
{
    struct Node * root = NULL;
    int num;
 
    cin >> num;
    while(!cin.eof())
    {
        InsertIntoTheBST(&root,num);
        cin >> num;
    }
 
    return (root);
}
//-----------------------------------------------------------------------------
//-----------Function that inserts numbers into BST----------------------------
//-----------------------------------------------------------------------------
void InsertIntoTheBST(struct Node **point_to_root,int num)
{
    while(*point_to_root != NULL)
        if (num <= (*point_to_root)->_data)
            point_to_root = &((*point_to_root)->_left);
        else
            point_to_root = &((*point_to_root)->_right);
 
    (*point_to_root) = AllocateNewNode(num);
}
//-----------------------------------------------------------------------------
//-----------Function that allocates new nodes---------------------------------
//-----------------------------------------------------------------------------
struct Node * AllocateNewNode(int num)
{
    struct Node * NewNode = NULL;
 
    NewNode = new(nothrow) struct Node;
 
    if(NewNode == NULL)
    {
        cerr <<"Can't allocate memory\n";
        exit(EXIT_FAILURE);
    }
 
 
    NewNode->_data = num;
    NewNode->_right =NULL;
    NewNode->_left = NULL;
 
    return (NewNode);
}
//-----------------------------------------------------------------------------
//-----------Function that finds the min_depth_leaf----------------------------
//-----------------------------------------------------------------------------
int TheLongestBranch(const struct Node *root,double &branch)
{
    const struct Node *point_to_node=root;
    if (point_to_node==NULL)
        return (0);
 
    if (point_to_node->_left!=NULL && point_to_node->_right!=NULL)
    {
        if ((point_to_node->_left==NULL && point_to_node->_right!=NULL)||(point_to_node->_left!=NULL && point_to_node->_right==NULL))
        {
            TheLongestBranch(point_to_node->_left,++branch);
            TheLongestBranch(point_to_node->_right,++branch);
        }
        else
        {
 
            TheLongestBranch(point_to_node->_left,branch);
            TheLongestBranch(point_to_node->_right,branch);
        }
 
    }
 
    if (point_to_node->_left==NULL && point_to_node->_right==NULL)
    return (branch);
 
}
//-----------------------------------------------------------------------------
//-----------Function that frees space-----------------------------------------
//-----------------------------------------------------------------------------
void FreeTheSpace(struct Node *& root)
{
    if(root == NULL)
        return;
 
    FreeTheSpace(root->_left);
    FreeTheSpace(root->_right);
 
    delete root;
}
Yandex
Объявления
20.06.2013, 14:54     Деревья С++ (функция, которая получает указатель на корень дерева и возвращает длину самой длинной ветки на дереве)
Ответ Создать тему
Опции темы

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