С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
azbest
41 / 41 / 8
Регистрация: 12.03.2013
Сообщений: 148
#1

Бинарное дерево с шаблоном - C++

13.07.2014, 23:19. Просмотров 315. Ответов 8
Метки нет (Все метки)

Пишу бинарное дерево типа BST<Key, Value>. Значениями хочу сделать любые типы данных. По-этому пришол к шаблонам, но с реализацией не выходит особенно с двумя типами. Наверное плохо понял принцип работы.
Кусок кода:

заголовочный файл
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
#ifndef BSTREE_H_INCLUDED
#define BSTREE_H_INCLUDED
//#define Value int
 
template <typename Key, typename Value>
 
struct Node {
private:
    Key key;         // ключ
    Value val;       // значение
    Node* left;      // указатель на левое поддерево
    Node* right;     // указатель на правое поддерево
    int N;           // количество эментов в поддереве
public:
    Node(Key key, Value val, int N) {
        this.key = key; this.val = val; this.N = N;
    }
};
 
template <typename Key, typename Value>
class BST {
private:
    Node<Key, Value> root;
 
    int size(Node<Key, Value> x) {
        return (x == NULL)?0:x.N;
    }
......
public:
    BST() {
        root = NULL;
    }
 
    int size() {
        return size(root);
    }
клиентская часть
C++
1
2
    BST<int, int> bst();
    bst.size();   ! тут ошибка
request for member 'size' in 'bst', which is of non-class type 'BST<int, int>()'
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.07.2014, 23:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Бинарное дерево с шаблоном (C++):

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

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

Бинарное дерево - C++
Необходимо построить бинарное дерево с методами inorder_tree_walk, tree_search, tree_minimum, tree_successor, tree_insert и tree_delete....

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

Бинарное дерево - C++
Здравствуйте, нужно помощь в написании программы. Условие: Каждая вершина бинарного дерева содержит: - 2 указателя (на каждый...

Бинарное дерево - C++
Не получается написать функцию для вывода дерева на экран. Работает она как-то не правильно. Помогите, пожалуйста, срочно. ВОт часть кода: ...

8
AlexVRud
461 / 172 / 45
Регистрация: 04.07.2014
Сообщений: 481
14.07.2014, 02:30 #2
1. key, ..., N - приватные члены класса, а ты их пытаешься использовать.
2. x в size - это не ссылка в твоём определении, звёздочку забыл.
0
castaway
Эксперт С++
4916 / 3024 / 370
Регистрация: 10.11.2010
Сообщений: 11,081
Записей в блоге: 10
Завершенные тесты: 1
14.07.2014, 07:19 #3
size - private метод, а не public.
size должен принимать один параметр, где он?
0
azbest
41 / 41 / 8
Регистрация: 12.03.2013
Сообщений: 148
14.07.2014, 10:11  [ТС] #4
Цитата Сообщение от castaway Посмотреть сообщение
size - private метод, а не public.
у меня два метода size() один приватный с одним принимаемым параметром (для внутреннего использования) и один публичный без параметра
Цитата Сообщение от azbest Посмотреть сообщение
int size() { return size(root); }
так что там все ок.

Цитата Сообщение от AlexVRud Посмотреть сообщение
key, ..., N
я же их использую внутри класса так что можно, или не понял намека.

Цитата Сообщение от AlexVRud Посмотреть сообщение
x в size - это не ссылка в твоём определении, звёздочку забыл.
переделал на ссылки но безрезультатно
C++
1
2
3
4
5
6
7
8
9
private:
    int size(Node<Key, Value>* x) {
        return (x == NULL)?0:x->N;
    }
.......
public:
    int size() {
        return size(&root);
    }
0
castaway
Эксперт С++
4916 / 3024 / 370
Регистрация: 10.11.2010
Сообщений: 11,081
Записей в блоге: 10
Завершенные тесты: 1
14.07.2014, 10:49 #5
Нам надо было догадаться что их там два?
Чего ещё мы не знаем?
0
azbest
41 / 41 / 8
Регистрация: 12.03.2013
Сообщений: 148
14.07.2014, 10:58  [ТС] #6
Цитата Сообщение от castaway Посмотреть сообщение
Нам надо было догадаться что их там два?
в куске кода предоставленом в первом посте было указано два метода size().

а что еще Вы хотите знать?)
под спойлером весь код загловочного файла
Кликните здесь для просмотра всего текста

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
#ifndef BSTREE_H_INCLUDED
#define BSTREE_H_INCLUDED
//#define Value int
 
#include <queue>
 
template <typename Key, typename Value>
 
struct Node {
private:
    Key key;        // ключ
    Value val;      // значение
    Node* left;     // указатель на левое поддерево
    Node* right;    // указатель на правое поддерево
    int N;          // количество эментов в поддереве
public:
    Node(Key key, Value val, int N) {
        this.key = key; this.val = val; this.N = N;
    }
};
 
template <typename Key, typename Value>
class BST {
private:
    Node<Key, Value> root;
 
    int size(Node<Key, Value>* x) {
        return (x == NULL)?0:x->N;
    }
 
    Value get(Node<Key, Value> x, Key key) {
        if (x == NULL) return NULL;
        int cmp = compareTo(key, x.key);
        if      (cmp < 0) return get(x.left, key);
        else if (cmp > 0) return get(x.right, key);
        else return x.val;
    }
 
    Node<Key, Value> put(Node<Key, Value> x, Key key, Value val){
        if (x == NULL) return new Node<Key, Value>(key, val, 1);
        int cmp = compareTo(key, x.key);
        if      (cmp < 0) x.left = put(x.left, key, val);
        else if (cmp > 0) x.right = put(x.right, key, val);
        else x.val = val;
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
 
    Node<Key, Value> floor(Node<Key, Value> x, Key key) {
        if (x == NULL) return NULL;
        int cmp = compareTo(key, x.key);
        if (cmp == 0) return x;
        if (cmp < 0) return floor(x.left, key);
        Node<Key, Value> t = floor(x.right, key);
        if (t != NULL) return t;
        else           return x;
    }
 
    int rank(Key key, Node<Key, Value> x) {
        if (x == NULL) return 0;
        int cmp = compareTo(key, x.key);
        if      (cmp < 0) return rank(key, x.left);
        else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
        else return size(x.left);
    }
 
    void inorder(Node<Key, Value> x, queue<Key> q) {
        if (x == NULL) return;
        inorder(x.left, q);
        q.enqueue(x.key);
        inorder(x.right, q);
    }
public:
    BST() {
        root = NULL;
    }
 
    int size() {
        return size(&root);
    }
 
    Value get(Key key) {
        return get(root, key);
    }
 
    void put(Key key, Value val) {
        put(root, key, val);
    }
 
    Key min() {
        if (root == NULL) return NULL;
        Node<Key, Value> tmp = root;
        while (tmp.left != NULL) tmp = tmp.left;
        return tmp.key;
    }
 
    Key max() {
        if (root == NULL) return NULL;
        Node<Key, Value> tmp = root;
        while (tmp.right != NULL) tmp = tmp.right;
        return tmp.key;
    }
 
    Key floor(Key key) {
        Node<Key, Value> x = floor(root, key);
        if (x == NULL) return NULL;
        return x.key;
    }
 
    int rank(Key key) {
        return rank(key, root);
    }
 
    queue<Key> keys() {
        queue<Key> q = new queue<Key>();
        inorder(root, q);
        return q;
    }
};
 
#endif // BSTREE_H_INCLUDED
0
castaway
14.07.2014, 11:57
  #7

Не по теме:

Виноват. Проблемы с прокруткой в телефоне.

0
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
14.07.2014, 12:32 #8
Проблема одна.
C++
1
BST<int, int> bst();
не является объектом, это указатель на функцию, под именем bst, которая не принимает ничего и возвращает BST<int, int>. Просто уберите скобки.
1
azbest
41 / 41 / 8
Регистрация: 12.03.2013
Сообщений: 148
14.07.2014, 14:24  [ТС] #9
с этим все ок, дальше правда ошибок понавылазило)) но это совсем другая история.
спасибо.
0
14.07.2014, 14:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.07.2014, 14:24
Привет! Вот еще темы с ответами:

Бинарное дерево - C++
Как организовать вывод бинарного дерева?

Бинарное дерево - C++
Привет Делаю бинарное дерево, пытаюсь добавить элемент. Что делаю не так? Класс дерева struct node{ int data; //поле...

Бинарное дерево - C++
Здравствуйте, Корень создаёться вот так TREE *root=NULL; непонятно почему функия добовления использует указатель на указатель ...

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


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

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

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