Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
0 / 0 / 0
Регистрация: 28.02.2016
Сообщений: 198
1

Как в программе происходит прямой обход по бинарному дереву?

24.05.2018, 16:40. Просмотров 368. Ответов 0
Метки нет (Все метки)


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
#include "stdafx.h"
#include <iostream> 
using namespace std;
struct Node
{
    Node *l, *r; //левое и правое поддерево
    int x; //Некоторые данные
};
 
/*ФУНКЦИЯ ДОБАВЛЕНИЯ ЗВЕНА В ДЕРЕВО*/
void add(int x, Node *&MyTree) //Функция добавления звена в дерево
{
    if (NULL == MyTree)  //То, о чем я в самом начале писал. Если дерева нет, то сеем семечко
    {
        MyTree = new Node; //Выделяем память под звено дерева
        MyTree->x = x; //Записываем данные в звено
        MyTree->l = MyTree->r = NULL; //Подзвенья инициализируем пустотой во избежание ошибок
    }
 
    if (x<MyTree->x)   //Если нововведенный элемент x меньше чем элемент x из семечка дерева, уходим влево
    {
        if (MyTree->l != NULL) add(x, MyTree->l); //При помощи рекурсии заталкиваем элемент на свободный участок
        else //Если элемент получил свой участок, то
        {
            MyTree->l = new Node;  //Выделяем память левому подзвену. Именно подзвену, а не просто звену
            MyTree->l->l = MyTree->l->r = NULL; //У левого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой
            MyTree->l->x = x; //Записываем в левое подзвено записываемый элемент 
        }
    }
 
    if (x>MyTree->x)   //Если нововведенный элемент x больше чем элемент x из семечка дерева, уходим вправо
    {
        if (MyTree->r != NULL) add(x, MyTree->r); //При помощи рекурсии заталкиваем элемент на свободный участок
        else //Если элемент получил свой участок, то
        {
            MyTree->r = new Node;  //Выделяем память правому подзвену. Именно подзвену, а не просто звену
            MyTree->r->l = MyTree->r->r = NULL; //У правого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой
            MyTree->r->x = x; //Записываем в правое подзвено записываемый элемент 
        }
    }
 
}
 
/*ОБХОД В ПРЯМОМ ПОРЯДКЕ*/
void Show(Node *&tree)
{
    if (NULL == tree)    return;    //Если дерева нет, выходим
 
    cout << tree->x << endl; //Посетили узел
    Show(tree->l); //Обошли левое поддерево   
    Show(tree->r); //Обошли правое поддерево   
}
int main()
{
    int x; //Некоторые данные
    Node *MyTree = NULL; //Указатель на нашу структуру. Инициализируем во избежание ошибок
 
    for (int i = 0; i<7; i++) //В дереве будет 7 узлов
    {
        cout << "X = "; cin >> x; //Ввели X с клавиатуры
        add(x, MyTree); //Добавили X в дерево
    }
 
    Show(MyTree);
Вот нашел, добавления элемента в дерево понят, а вот обход нет, она правильно выводит прямой обход по дереву, но как он это делает, как он знает, что надо начала по левой стороне идти и в той же левой стороне выводить потом правые элементы, тут же нету никакх встроенных функций, которые бы это делали????
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.05.2018, 16:40
Ответы с готовыми решениями:

Итератор по бинарному дереву
Всем привет! Помогите пожалуйста! Пишу бинарное дерево, нужно реализовать итератор по нему. Не...

Подключение к бинарному дереву списка
Вот есть такой вот код. Не могу подключить к моему узлу бинарного дерева односвязный список ...

Итератор для обхода по бинарному дереву
Кхм. Попытался реализовать итератор для обхода по бинарному дереву... Наткнулся на запару. Дерево...

Поиск по бинарному дереву целочисленных значений
Здравствуйте! Очень нужна помощь данном, надеюсь что простом, задании. Заранее спасибо!:-[ ...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.05.2018, 16:40

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Поиск по бинарному дереву, построение бинарного дерева
Сделал 3 процедуры: 1. строит бинарное дерево 2. рекурсивная процедура помогает 1-ой найти...

Довести до ума программу про бинарному дереву
Здравствуйте. Помогите пожалуйста привести до ума задачу: организовать бинарное дерево по заданной...

Обход по дереву
Доброго вам дня всем! Есть некоторые вопросы по одной задаче из теории. Прошу помочь в них...

Разница между понятиями "Обход в прямом направлении" и "Итерационный прямой обход"
Ребятаа, обьясните чем различается: Обход в прямом направлении и Итерационный прямой обход ...


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

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

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