0 / 0 / 0
Регистрация: 03.12.2016
Сообщений: 30
1

Поиск в бинарном дереве

11.12.2017, 23:50. Показов 8048. Ответов 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
#include "stdafx.h"
#include<iostream>
using namespace std;
 
struct Node //Node - Это звено дерева
{
    int x; //x - Число, которое я буду записывать в дерево
    Node *l, *r; //Адресные поля. Адрес левой части и Адрес правой части (от left,right)
};
 
void show(Node *&Tree) //Функция обхода
{
    if (Tree != NULL) //Пока не встретится пустое звено
    {
        show(Tree->l); //Рекурсивная функция для вывода левого поддерева
        cout << Tree->x; //Отображаем корень дерева
        show(Tree->r); //Рекурсивная функци для вывода правого поддерева
    }
}
 
/*Добавили очистку памяти*/
void del(Node *&Tree) {
    if (Tree != NULL) //Пока не встретится пустое звено
    {
        del(Tree->l); //Рекурсивная функция прохода по левому поддереву
        del(Tree->r); //Рекурсивная функци для прохода по правому поддереву
        delete Tree; //Убиваем конечный элемент дерева
        Tree = NULL; //Может и не обязательно, но плохого не будет
    }
 
}
 
void add_node(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_node(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_node(x, MyTree->r); //При помощи рекурсии заталкиваем элемент на свободный участок
        else //Если элемент получил свой участок, то
        {
            MyTree->r = new Node;  //Выделяем память правому подзвену. Именно подзвену, а не просто звену
            MyTree->r->l = MyTree->r->r = NULL; //У правого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой
            MyTree->r->x = x; //Записываем в правое подзвено записываемый элемент 
        }
    }
 
 
 
}
 
int main()
{
    Node *Tree = NULL;  //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой
    for (int i = 5; i>0; i--) add_node(i, Tree);
    show(Tree,);
    del(Tree); //чистка памяти
    cin.get();
 
    return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.12.2017, 23:50
Ответы с готовыми решениями:

Поиск в Бинарном Дереве!
Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента....

Поиск дубликатов в бинарном дереве
Требуется создать функцию поиска дубликатов ИНФОРМАЦИОННОЙ ЧАСТИ, НЕ КЛЮЧА в бинарном дереве. ...

Поиск предка элемента в бинарном дереве
Вот функция поиска предка в бинарном дереве поиска: tree* predok(tree* root, tree* potomok, int...

Поиск одинаковых элементов в бинарном дереве
Нужно вывести на экран все повторяющиеся элементы в бинарном дереве. # include &lt;iostream&gt; #...

5
6 / 6 / 4
Регистрация: 11.12.2017
Сообщений: 29
12.12.2017, 02:14 2
Приблизительно так :

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void find(Node *&Tree, int x)
{
    if (Tree != NULL)
    {
        if(Tree->x == x ){
            cout << Tree->x;
            cout << " left = "<<Tree->l->x;
            cout << " right = " << Tree->r->x;
            return;
        }
        find(Tree->l,x);
        find(Tree->r,x);
    }
}
1
0 / 0 / 0
Регистрация: 03.12.2016
Сообщений: 30
12.12.2017, 04:20  [ТС] 3
Большое спасибо! Работает все, кроме вывода правой вершины. После вывода левой программа прерывается.. Не подскажете, что с этим можно сделать?
0
6 / 6 / 4
Регистрация: 11.12.2017
Сообщений: 29
12.12.2017, 18:24 4
Я не дописал думал вы сами догадаетесь. Нужно проверять, чтобы не равно NULL было.

C++
1
2
3
4
5
6
if (NULL != Tree->l){
 cout << " left = "<<Tree->l->x;
}
if (NULL != Tree->r){
 cout << " right = " << Tree->r->x;
}
0
0 / 0 / 0
Регистрация: 03.12.2016
Сообщений: 30
13.12.2017, 07:25  [ТС] 5
я то догадался, написал, но оно все равно не работает))
0
6 / 6 / 4
Регистрация: 11.12.2017
Сообщений: 29
13.12.2017, 21:20 6
А конкретнее? Что не работает?
0
13.12.2017, 21:20
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.12.2017, 21:20
Помогаю со студенческими работами здесь

Поиск ключа в бинарном дереве поиска
Здравствуйте! Помогите ещё с задачками) 1.Поиск ключа в бинарном дереве поиска (точное...

Поиск одинаковых элементов в бинарном дереве.
Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента. Вывести...

Поиск суммы последовательных узлов в бинарном дереве
Дано: бинарное дерево (Например созданное по этому алгоритму). Число S. Нужно найти...

Реализовать поиск и удаление элемента по индексу в бинарном дереве
Здравствуйте подскажите пожалуйста как сделать удаление и поиск по индексу. #include&lt;iostream&gt; ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru