Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Kristina_S
4 / 1 / 14
Регистрация: 09.10.2015
Сообщений: 186
#1

Обход Бинарного дерева - C++

04.08.2016, 14:30. Просмотров 526. Ответов 1
Метки нет (Все метки)

Задача: написать функцию, помощью которой можно получить n-тый элемент бинарного дерева по возрастанию.
в узлах хранятся целые числа.
вот с алгоритмом уже проблемы
Мои мысли:пройтись по дереву "in-order" ,но,где хранить значения. и как оттуда доставать.
Наверняка,существует изящное решение.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.08.2016, 14:30
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Обход Бинарного дерева (C++):

Обход бинарного дерева
Прошу Вас, помогите школьнику, незнающему деревья, завтра срочно надо сдать работу, я никак не могу реализовать... 1. В заданном...

Обход бинарного дерева С++
Нужна помощь! Просмотрел много источников, но так и не нашёл своего ответа...Суть задачи состоит в том что, мне нужно при обходе...

Обход бинарного дерева
может есть у кого такой пример или похожий??или часть какая нибудь?

НЕрекурсивный обход бинарного дерева
уважаемые программисты! нужно написать алгоритм обхода бинарного дерева без использования рекурсии, а с помощью стека. Проверить на...

Обход бинарного дерева без рекурсии
нужно написать алгоритм обхода бинарного дерева без использования рекурсии, а с помощью стека. Проверить на дереве int, но в самом коде...

Как осуществлять обход бинарного дерева?
Хочу создать клас бинарное дерево, но не знаю чем это дерево я буду проходить, как двигатса от одного узла к дргому.(без создания...

1
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.08.2016, 08:17 #2
Лучший ответ Сообщение было отмечено vavun как решение

Решение

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
147
148
149
150
151
152
153
154
155
156
///////////////////////////////////////////////////////////////////////////////
//Задача: написать функцию, с помощью которой можно получить n-тый
//элемент бинарного дерева по возрастанию.
//в узлах хранятся целые числа.
///////////////////////////////////////////////////////////////////////////////
//2.
///////////////////////////////////////////////////////////////////////////////
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <memory>
///////////////////////////////////////////////////////////////////////////////
struct  T_node;
///////////////////////////////////////////////////////////////////////////////
typedef std::shared_ptr     < int       >    T_int_ptr;
typedef std::shared_ptr     < T_node    >    T_tree;
///////////////////////////////////////////////////////////////////////////////
struct  T_node
{
    //-------------------------------------------------------------------------
    T_int_ptr   val_ptr_    {};
    T_tree      left_       {};
    T_tree      right_      {};
    //-------------------------------------------------------------------------
    void    insert( int     val )
    {
        if( !val_ptr_ )
        {
            val_ptr_.reset
                (
                    new int( val )
                );
        }
        else
        {
            if( val < *val_ptr_ )
            {
                if( !left_ )
                {
                    left_.reset( new T_node );
                }
                left_->insert( val );
            }
            else   if( val > *val_ptr_ )
            {
                if( !right_ )
                {
                    right_.reset( new T_node );
                }
                right_->insert( val );
            }//else
        }//else
    }
    //-------------------------------------------------------------------------
    bool    successfully_for_ind_set_elem
        (
            int             ind,
            int         &   val,
            T_int_ptr       counter_ptr     =   nullptr
        )
    {
        if( !counter_ptr )
        {
            counter_ptr.reset
                (
                    new int()
                );
        }//if
 
        bool    bool_res    =       left_
                                &&  left_->successfully_for_ind_set_elem
                                        (
                                            ind,
                                            val,
                                            counter_ptr
                                        );
 
        if( bool_res )
        {
            return  bool_res;
        }
 
        ++*counter_ptr;
 
        bool_res    =       *counter_ptr
                        ==  ind;
 
        if( bool_res )
        {
            val     =   *val_ptr_;
        }
 
        return      bool_res
 
                ||      right_
                    &&  right_->successfully_for_ind_set_elem
                            (
                                ind,
                                val,
                                counter_ptr
                            );
    }
    //-------------------------------------------------------------------------
    void    print()
    {
        int     ind     {};
        int     elem    {};
 
        while   (
                    successfully_for_ind_set_elem
                        (
                            ++ind,
                            elem
                        )
                )
        {
            std::cout   <<  elem
                        <<  ' ';
        }
 
        std::cout   <<  std::endl
                    <<  std::endl;
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
void    insert_val_in_tree_and_print
    (
        int     val,
        T_tree  tree
    )
{
    tree->insert(val);
 
    std::cout   <<  "insert "
                <<  val
                <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
    const   int     COUNT   {7};
    T_tree          tree    { new T_node };
 
    for( int  i{}; i < COUNT * 2; ++i )
    {
        insert_val_in_tree_and_print
            (
                rand() % COUNT + 1,
                tree
            );
 
        tree->print();
    }//for
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.08.2016, 08:17
Привет! Вот еще темы с решениями:

Бинарное дерево. Обход бинарного дерева (симметрический, прямой и обратный)
Привет всем! Мне надо в курсовой работе написать программу, которая строит бинарное дерево (по вводимым значениям) и потом обходит это...

Дополнить код, чтобы получился полноценный прямой обход бинарного дерева
Подскажите как дополнить код,что бы получился полноценный прямой обход бинарного дерева... #include &quot;stdafx.h&quot; #include &lt;iostream&gt; ...

"Рекурсивная функция" (Обход бинарного дерева)
Привет всем, встретился с такой рекурсивной ф-ей, которая обходит бинарное дерево и выводит его на экран. Не могу понять как она работает ...

Запись бинарного дерева в файл и восстановление из него этого дерева
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя - 1 указатель на структуру с данными, 2 и 3й указатель на...


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

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

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