11 / 11 / 3
Регистрация: 06.08.2011
Сообщений: 208
1

Сформировать бинарное дерево поиска и определить максимальную глубину дерева

18.01.2018, 06:39. Показов 5527. Ответов 30
Метки нет (Все метки)

Добрый день всем.
По задаче необходимо сформировать бинарное дерево поиска и определить максимальную глубину дерева.
Перед завершением программы освободить память.
Оно у меня явно не правильно работает
И не пойму как для него функцию удаления элементов написать
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
#include <iostream>
#include <conio.h>
 
using namespace std;
//Наша структура
struct node
{
    int info; //Информационное поле
    node *l, *r;//Левая и Правая часть дерева
};
 
node * tree=NULL; //Объявляем переменную, тип которой структура Дерево
 
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a,node **t)
{
    if ((*t)==NULL) //Если дерева не существует
    {
        (*t)=new node; //Выделяем память
        (*t)->info=a; //Кладем в выделенное место аргумент a
        (*t)->l=(*t)->r=NULL; //Очищаем память для следующего роста
        return; //Заложили семечко, выходим
    }
       //Дерево есть
        if (a>(*t)->info) push(a,&(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
        else push(a,&(*t)->l); //Иначе кладем его влево
}
 
/*ФУНКЦИЯ УДАЛЕНИЯ ЭЛЕМЕНТОВ ДЕРЕВA*/
void delete_node(){
    if (t==NULL) return; //Если дерево пустое, то удалять нечего, выходим
    else //Иначе
    { //найти максимальный элемент
               
    }
}
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print (node *t,int u)
{
    if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
    print(t->l,++u);//С помощью рекурсивного посещаем левое поддерево
    for (int i=0;i<u;++i) cout<<"|";
    cout<<t->info<<endl; //И показываем элемент
    u--;
    }
    print(t->r,++u); //С помощью рекурсии посещаем правое поддерево
}
 
/*Функция поиска максимального элемента*/
int getMaxDepth(node* tree, int depth) {
if (tree == NULL)
return depth;
return max(getMaxDepth(tree->l, depth + 1), getMaxDepth(tree->r, depth + 1));
}
 
int main(int argc, char *argv[])
{
    int n; //Количество элементов
    int s; //Число, передаваемое в дерево
    cout<<"Vvod kol-vo elementov ";
    cin>>n; //Вводим количество элементов
 
    for (int i=0;i<n;++i)
    {
    cout<<"Enter Digit:";
    cin>>s; //Считываем элемент за элементом
 
    push(s,&tree); //И каждый кладем в дерево
    }
    cout<<"Node\n";
    print(tree,0);
    cout << "Max = "<<getMaxDepth(tree, 0);
    getch();
    return 0;
}
Выводит
Сформировать бинарное дерево поиска и определить максимальную глубину дерева
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.01.2018, 06:39
Ответы с готовыми решениями:

Бинарное дерево поиска (определить максимальную глубину)
Всем привет! Делаю лабу, написал основу, но не могу понять, как сделать последний пункт задания,...

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

Бинарное дерево поиска - улучшение "визуализации" дерева
Здравствуйте, есть программа, формирующая выводящая на экран бинарное дерево поиска, значения...

Рекурсия: определить, помещена ли строка в бинарное дерево поиска
Помогите пожалуйста исправить ошибку. Задание:&quot;Разработать рекурсивную функцию, которая определяет,...

30
"C with Classes"
1498 / 1296 / 489
Регистрация: 16.08.2014
Сообщений: 5,443
Записей в блоге: 1
18.01.2018, 07:04 2
Ирина197708, страшное сишное бинарное дерево, на С++ проще можно описать. Бог помощь.

Добавлено через 3 минуты
по мне так БДП самое простое из деревьев
1
11 / 11 / 3
Регистрация: 06.08.2011
Сообщений: 208
18.01.2018, 07:04  [ТС] 3
Можно еще проще?
0
"C with Classes"
1498 / 1296 / 489
Регистрация: 16.08.2014
Сообщений: 5,443
Записей в блоге: 1
18.01.2018, 07:29 4
Ирина197708, начало есть
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstddef>
 
class BinaryTree
{
private:
    struct Node
    {
        Node* left;
        Node* right;
 
        size_t key;
        int value;
    };
 
public:
    int Find(std::size_t);
    void Insert(std::size_t, int);
    void Remove(std::size_t);
};
1
11 / 11 / 3
Регистрация: 06.08.2011
Сообщений: 208
18.01.2018, 07:40  [ТС] 5
_stanislav, size_t key что будет?

C++
1
2
3
4
5
6
7
8
    struct Node
    {
        Node* left;  //Левая ветвь
        Node* right; //Правая ветвь
 
        size_t key;  // Это что будет, корень?
        int value; //Значение которое кладем
    };
И что будет являться параметром функции
C++
1
2
3
void BinaryTree::Find(????){
    
}
По идее должен быть int value
0
"C with Classes"
1498 / 1296 / 489
Регистрация: 16.08.2014
Сообщений: 5,443
Записей в блоге: 1
18.01.2018, 08:13 6
Цитата Сообщение от Ирина197708 Посмотреть сообщение
size_t key; *// Это что будет, корень?
это ключ для поиска
1
11 / 11 / 3
Регистрация: 06.08.2011
Сообщений: 208
18.01.2018, 08:41  [ТС] 7
Ну не знаю, не запутаюсь ли я в структуре, которая еще и обернута классом... Может лучше от класса избавится и работать напрямую со структурой?
0
"C with Classes"
1498 / 1296 / 489
Регистрация: 16.08.2014
Сообщений: 5,443
Записей в блоге: 1
18.01.2018, 09:23 8
Ирина197708, пока вот
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
#include <cstddef>
 
class BinaryTree
{
private:
    struct Node
    {
        Node* left;
        Node* right;
 
        std::size_t key;
        int value;
 
        Node(Node* l = nullptr,
             Node* r = nullptr,
             std::size_t k = 0,
             int v = -1
            ) : left(l),
                right(r),
                key(k),
                value(v)
        {
            // ...
        }
    };
 
    Node* root;
 
public:
    BinaryTree() : root(nullptr) {}
 
    int Find(std::size_t k)
    {
        // ...
        return 0;
    }
    void Insert(std::size_t k, int v)
    {
        // ...
    }
    void Remove(std::size_t k)
    {
        // ...
    }
};
 
int main(int argv, char* argc[] )
{
    BinaryTree binaryTree;
 
    return 0;
}
Добавлено через 1 минуту
Цитата Сообщение от Ирина197708 Посмотреть сообщение
ожет лучше от класса избавится и работать напрямую со структурой?
думаю что с классом удобней, там работа с указателями будет
1
11 / 11 / 3
Регистрация: 06.08.2011
Сообщений: 208
18.01.2018, 10:44  [ТС] 9
указатели для меня самое страшное, вечно с ними геммор какой то...
Спасибо, за код.
И сразу мне выдал: nullprt was not declarated.
на этой строке.
C++
1
2
3
4
5
6
7
8
        Node(Node* l = nullptr,
             Node* r = nullptr,
             std::size_t k = 0,
             int v = -1
            ) : left(l),
                right(r),
                key(k),
                value(v)
разобралась:
CONFIG += c++11 добавлен, пишу в qt

Добавлено через 13 минут
Ну вот как и знала что запутаюсь.
C++
1
2
3
4
5
6
7
    void Insert(std::size_t k, int v)
    {
        if(Node.key == NULL ){ //Если корень пустой
            Node.key = v;
        }
        // ...
    }
Какой то бред пишу...
0
"C with Classes"
1498 / 1296 / 489
Регистрация: 16.08.2014
Сообщений: 5,443
Записей в блоге: 1
18.01.2018, 10:57 10
Цитата Сообщение от Ирина197708 Посмотреть сообщение
if(Node.key == NULL ){ //Если корень пустой
C++
1
if(root == nullptr ){ //Если корень пустой
я сейчас тоже сяду писать, давно хотел реализовать себе в коллекцию
0
11 / 11 / 3
Регистрация: 06.08.2011
Сообщений: 208
18.01.2018, 10:58  [ТС] 11
C++
1
2
3
4
5
6
7
8
9
    void Insert(std::size_t k, int v)
    {
        BinaryTree* BinTree = new BinaryTree; //Выделили память
 
        if(BinTree->root == NULL ){ //Если корень пустой
            BinTree->root = v;
        }
        // ...
    }
Переписала, выдает ошибку
C:\Users\admin\Documents\lr\main.cpp:45: ошибка: invalid conversion from 'int' to 'BinaryTree::Node*' [-fpermissive]
BinTree->root = v;
^
0
"C with Classes"
1498 / 1296 / 489
Регистрация: 16.08.2014
Сообщений: 5,443
Записей в блоге: 1
18.01.2018, 11:08 12
Цитата Сообщение от Ирина197708 Посмотреть сообщение
Переписала, выдает ошибку
тогда так, что бы ошибку исправить
C++
1
2
3
4
5
6
7
8
9
    void Insert(std::size_t k, int v)
    {
        if(this->root == nullptr){ //Если корень пустой
            this->root = new BinaryTree; //Выделили память
            this->root ->key = k;
            this->root ->value = v;
        }
        // ...
    }
или без this, а то слишком много стрелок
C++
1
2
3
4
5
6
7
8
9
    void Insert(std::size_t k, int v)
    {
        if(root == nullptr){ //Если корень пустой
            root = new BinaryTree; //Выделили память
            root->key = k;
            root->value = v;
        }
        // ...
    }
Добавлено через 2 минуты
пардон
C++
1
2
3
4
5
6
if(root == nullptr)
{
    root = new Node;
    root->key = k;
    root->value = v;
}
1
11 / 11 / 3
Регистрация: 06.08.2011
Сообщений: 208
18.01.2018, 11:15  [ТС] 13
C++
1
2
3
4
5
6
7
8
9
    void Insert(std::size_t k, int v)
        {
            if(root == nullptr){ //Если корень пустой
                root = new BinaryTree; //Выделили память
                root->key = k;  //индекс структуры
                root->value = v;  // значение которое положим
            }
            // ...
        }
C:\Users\admin\Documents\lr\main.cpp:43: ошибка: cannot convert 'BinaryTree*' to 'BinaryTree::Node*' in assignment
root = new BinaryTree;
^

Второй вариант отработал:
C++
1
2
3
4
5
6
7
8
9
10
    void Insert(std::size_t k, int v)
        {
        if(root == nullptr)
        {
            root = new Node;
            root->key = k;
            root->value = v;
        }
            // ...
        }
0
"C with Classes"
1498 / 1296 / 489
Регистрация: 16.08.2014
Сообщений: 5,443
Записей в блоге: 1
18.01.2018, 11:22 14
Ирина197708,
C++
1
2
3
4
5
6
7
8
9
    void Insert(std::size_t k, int v)
    {
        if(root == nullptr)
        {
            root = new Node();
            root->key = k;
            root->value = v;
        }
    }
root это не BinaryTree. это Node

Добавлено через 6 минут
Ирина197708, надо добавить return
C++
1
2
3
4
5
6
7
8
9
10
11
    void Insert(std::size_t k, int v)
    {
        if(root == nullptr)
        {
            root = new Node();
            root->key = k;
            root->value = v;
 
            return;
        }
    }
0
11 / 11 / 3
Регистрация: 06.08.2011
Сообщений: 208
18.01.2018, 11:24  [ТС] 15
Да, дошло до меня))
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
   void Insert(std::size_t k, int v)
        {
        if(root == nullptr)
        {
            root = new Node;
            root->key = k;
            root->value = v;
            return;
        }
          //Дерево есть
        if(v > root->value) Insert(v, right->r); //если аргумент v больше чем текущий элемент, кладем его в право
 
        }
Теперь загвоздка в том как положить значение в правый элемент, и под них тоже ведь надо выделить сначало память?
0
"C with Classes"
1498 / 1296 / 489
Регистрация: 16.08.2014
Сообщений: 5,443
Записей в блоге: 1
18.01.2018, 11:29 16
Цитата Сообщение от Ирина197708 Посмотреть сообщение
Теперь загвоздка в том как положить значение в правый элемент, и под них тоже ведь надо выделить сначало память?
1
11 / 11 / 3
Регистрация: 06.08.2011
Сообщений: 208
18.01.2018, 11:34  [ТС] 17
Что то я не догоняю...
C++
1
if(v > root->value) Insert(root->right, v); //если аргумент v больше чем текущий элемент, кладем его в право
ошибка: invalid conversion from 'BinaryTree::Node*' to 'std::size_t {aka unsigned
0
"C with Classes"
1498 / 1296 / 489
Регистрация: 16.08.2014
Сообщений: 5,443
Записей в блоге: 1
18.01.2018, 11:36 18
Ирина197708, я хочу добавить метод Insert в структуру Node, он будет рекурсивный, а метод BinaryTree::Insert
будет не рекурсивный. и вызывать Node::Insert из BinaryTree::Insert
1
11 / 11 / 3
Регистрация: 06.08.2011
Сообщений: 208
18.01.2018, 11:59  [ТС] 19
Так и знала что запутаюсь.., не понимаю, как передать значение в правую ветку.
C++
1
if(v > root->value) BinaryTree::Insert(Node::insert(root->right, v));
C:\Users\admin\Documents\lr\main.cpp:50: ошибка: 'insert' is not a member of 'BinaryTree::Node'
if(v > root->value) BinaryTree::Insert(Node::insert(root->right, v));
0
"C with Classes"
1498 / 1296 / 489
Регистрация: 16.08.2014
Сообщений: 5,443
Записей в блоге: 1
18.01.2018, 12:03 20
Ирина197708,
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
#include <cstddef>
 
class BinaryTree
{
private:
    struct Node
    {
        Node* left;
        Node* right;
 
        std::size_t key;
        int value;
 
        Node(Node* l = nullptr, Node* r = nullptr) :
            left(l), right(r)
        {
            // ...
        }
 
        void Insert(std::size_t k, int v)
        {
            if(k > key)
            {
                if (right) right->Insert(k, v);
                else
                {
                    right = new Node();
                    right->key = k;
                    right->value = v;
                }
 
            }
            else if (k < key)
            {
                if (left) left->Insert(k, v);
                else
                {
                    right = new Node();
                    right->key = k;
                    right->value = v;
                }
            }
            else
            {
                key = k;
                value = v;
            }
        }
    };
 
    Node* root;
 
public:
    BinaryTree() : root(nullptr) {}
 
    int Find(std::size_t k)
    {
        // ...
        return 0;
    }
    void Insert(std::size_t k, int v)
    {
        if(root == nullptr)
        {
            root = new Node();
            root->key = k;
            root->value = v;
 
            return;
        }
 
        root->Insert(k, v);
    }
    void Remove(std::size_t k)
    {
        // ...
    }
};
Добавлено через 4 минуты
Ирина197708, будем считать что метод добавления у нас есть?
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.01.2018, 12:03

Преобразовать идеальное бинарное дерево в бинарное дерево поиска
Всем привет, я создал идельное бинарное дерево и написал к нему функции. Как мне теперь можно...

Найти максимальную глубину дерева
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; using std::cout; using std::cin; using std::endl; ...

Найти максимальную глубину дерева
найти максимальную глубину дерева

Найти максимальную и минимальную глубину дерева
1)вести дерево с клавиатуры 2)определить max глубину дерева 3)определить min глубину дерева


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

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

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