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

Бинарное дерево

09.12.2016, 21:25. Показов 735. Ответов 2
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Необходимо построить бинарное дерево с методами inorder_tree_walk, tree_search, tree_minimum, tree_successor, tree_insert и tree_delete. Компилятор ругается на строки с tree->root. В коде не работают функции insert и delete, остальное, думаю, правильно. Код делался сугубо по Корману. На фото список ошибок. Подскажите, как исправить программу?
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
#include "stdafx.h"
#include <stdlib.h>
 
struct tree {
    int key;
    struct tree *parent, *left, *right;
    struct tree *root;
};
 
void inorder_tree_walk(struct tree *x) {
    if (x != NULL)
    {
        inorder_tree_walk(x->left);
        printf("%d ", x->key);
        inorder_tree_walk(x->right);
    }
}
 
struct tree *tree_search(struct tree *x, int key) {
    if (x == NULL || key == x->key)
        return x;
    if (key < (x->key)) {
        return tree_search(x->left, key);
    }
    else{
        return tree_search(x->right, key);
    }
}
 
struct tree *tree_minimum(struct tree *x) {
    while (x->left != NULL)
        x = x->left;
        return x;
}
 
struct tree *tree_successor(struct tree *x) {
    struct tree *y;
    if (x->right != NULL) {
        return tree_minimum(x->right);
    }
    y = x->parent;
 
        while (y != NULL && x == y->right) {
            x = y;
            y = y->parent;
            return y;
        }
}
 
struct tree *tree_insert(struct tree *x, int key) 
{
    struct tree *z = NULL;
    struct tree *y = NULL;
    x = tree->root;
    while (x != NULL)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;
 
    if (y == NULL)
    {
        tree->root = z;
    }
 
    else if (z->key < y->key)
        y->left = z;
 
    else
        y->right = z;
}
 
struct tree *tree_delete(struct tree *tree, int key) {
    
    struct tree *z;
    struct tree *x;
    struct tree *y;
 
    if (z->left == NULL || z->right == NULL) {
        y = z;
    }
 
    else y = tree_successor(z);
 
    if (y->left != NULL)
        x = y->left;
    else x = y->right;
 
    if (x != NULL)
        x->parent = y->parent;
 
    if (y->parent = NULL)
        tree->root = x;
 
    else if (y = y->parent->left)
        y->parent->left = x;
 
    else y->parent->right = x;
 
    if (y != z)
    z->key = y->key;
 
    return y;
}
 
int main() {
    tree *root = NULL;
    root = tree_insert(root, 7);
    root = tree_insert(root, 13);
    root = tree_insert(root, 8);
    root = tree_insert(root, 23);
    root = tree_insert(root, -7);
    root = tree_insert(root, 13);
    root = tree_insert(root, 31);
    root = tree_insert(root, 5);
    inorder_tree_walk(root);
    printf("\n\n");
 
    tree *tmp;
    tmp = tree_minimum(root);
    printf("minimum = %d\n", tmp->key);
 
    root = tree_delete(root, 8);
    root = tree_delete(root, -7);
    root = tree_delete(root, 31);
    inorder_tree_walk(root);
    printf("\n\n");
 
    tmp = tree_search(root, 13);
    if (tmp == NULL) {
        printf("no element\n");
    }
    else {
        printf("found element\n");
    }
    getchar();
}
Миниатюры
Бинарное дерево  
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.12.2016, 21:25
Ответы с готовыми решениями:

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

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Бинарное дерево
Помогите, пожалуйста. Осталась последняя задача в контрольной. Не знаю даже, как к ней...

Бинарное Дерево
struct Tree { int value; Tree *l, *r; }; void add(Tree *&amp;obj, int value) { if (obj ==...

2
0 / 0 / 2
Регистрация: 11.10.2015
Сообщений: 42
10.12.2016, 00:15  [ТС] 2
еще периодически выскакивает исключение, что "значение was nullptr"

Добавлено через 2 часа 30 минут
Переделала код, оказывается tree нельзя использовать.

Теперь показывает исключение "mytree was nullptr"

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
#include "stdafx.h"
#include <stdlib.h>
 
struct tree {
    int key;
    struct tree *parent, *left, *right;
    struct tree *root;
};
 
void inorder_tree_walk(struct tree *x) {
    if (x != NULL)
    {
        inorder_tree_walk(x->left);
        printf("%d ", x->key);
        inorder_tree_walk(x->right);
    }
}
 
struct tree *tree_search(struct tree *x, int key) {
    if (x == NULL || key == x->key)
        return x;
    if (key < (x->key)) {
        return tree_search(x->left, key);
    }
    else{
        return tree_search(x->right, key);
    }
}
 
struct tree *tree_minimum(struct tree *x) {
    while (x->left != NULL)
        x = x->left;
        return x;
}
 
struct tree *tree_successor(struct tree *x) {
    struct tree *y;
    if (x->right != NULL) {
        return tree_minimum(x->right);
    }
    y = x->parent;
 
        while (y != NULL && x == y->right) {
            x = y;
            y = y->parent;
            return y;
        }
}
 
struct tree *tree_insert(struct tree *mytree, int key) 
{
    struct tree *x = NULL;
    struct tree *z = NULL;
    struct tree *y = NULL;
 
    x = mytree->root;
    while (x != NULL)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;
 
    if (y == NULL)
    {
        mytree->root = z;
    }
 
    else if (z->key < y->key)
        y->left = z;
 
    else
        y->right = z;
    return 0;
}
 
struct tree *tree_delete(struct tree *tree, int key) {
    
    struct tree *z = NULL;
    struct tree *x;
    struct tree *y;
 
    if (z->left == NULL || z->right == NULL) {
        y = z;
    }
 
    else y = tree_successor(z);
 
    if (y->left != NULL)
        x = y->left;
    else x = y->right;
 
    if (x != NULL)
        x->parent = y->parent;
 
    if (y->parent = NULL)
        tree->root = x;
 
    else if (y = y->parent->left)
        y->parent->left = x;
 
    else y->parent->right = x;
 
    if (y != z)
    z->key = y->key;
 
    return y;
}
 
int main() {
    tree *root = NULL;
    root = tree_insert(root, 7);
    root = tree_insert(root, 13);
    root = tree_insert(root, 8);
    root = tree_insert(root, 23);
    root = tree_insert(root, -7);
    root = tree_insert(root, 13);
    root = tree_insert(root, 31);
    root = tree_insert(root, 5);
    inorder_tree_walk(root);
    printf("\n\n");
 
    tree *tmp;
    tmp = tree_minimum(root);
    printf("minimum = %d\n", tmp->key);
 
    root = tree_delete(root, 8);
    root = tree_delete(root, -7);
    root = tree_delete(root, 31);
    inorder_tree_walk(root);
    printf("\n\n");
 
    tmp = tree_search(root, 13);
    if (tmp == NULL) {
        printf("not found\n");
    }
    else {
        printf("found\n");
    }
    getchar();
}
0
Комп_Оратор)
Эксперт по математике/физике
8949 / 4703 / 629
Регистрация: 04.12.2011
Сообщений: 13,999
Записей в блоге: 16
10.12.2016, 01:35 3
Kvitkaa, бинарное дерево это трехсвязный список в Вашем случае и предполагает твёрдые навыки выделения памяти.
Вот эти строки говорят о грустном:
C++
1
2
tree *root = NULL;
root = tree_insert(root, 7);
Пусть имена и неудачны. Не это сейчас важно. Смотрите, Вы объявили указатель. Сбросили его в ноль (в принципе не подсудно). Далее Вы пытаетесь вызвать метод класса как свободную функцию и это не получается. И слава богу. Потому, что в методе (если бы он был вызван на экземпляре как положено) происходит разыменование переданного указателя.
Надо вернутся к самому началу. Массивы в динамической памяти. Односвязный список потом написать. Зачем дерево?
0
10.12.2016, 01:35
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.12.2016, 01:35
Помогаю со студенческими работами здесь

Бинарное дерево
Друзья, помогите реализовать задачу в виде бинарного дерева: Оператор мобильной связи...

Бинарное дерево
Написать программу для создания, на основе конструктора,дерева из объектов двух типов. Объекты...

Бинарное дерево
Привет Делаю бинарное дерево, пытаюсь добавить элемент. Что делаю не так? Класс дерева...

Бинарное дерево
Помогите пожалуйста с программой. Нужно сделать обход, слева и справа(функции get_left и...


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

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

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