Форум программистов, компьютерный форум CyberForum.ru

Дерево - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.81
kjahert
48 / 48 / 5
Регистрация: 08.04.2011
Сообщений: 124
04.05.2011, 17:36     Дерево #1
Условие:
Программа построения дерева, где узел(корень) - ФИО препода, а инф. поля (наверное левая\правая ветки) имеют записи: 1)должность(string[10]), 2)предметы что преподает. Написать процедуру печати построеного бинарного дерева(полная инфа про препода)

Кто нибудь знает как выполнить это задание, т.е. как в корень записать симв. строку, какие if 'ы и while'ы использовать, в какую часть дерева записывать записи?

В наличии имеються функции добавления первого введенного элемента в корень и ввода остальных узлов и вывода дерева print_tree ну и структура с *left, *right и
некоторым d что похоже есть num

Добавлено через 55 секунд
По структуре надо
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
#include <iostream.h>
 
struct node
{
 int d;
 node *left;
 node *right;
};
node * first(int d);
node * search_insert(node *root, int d);
void print_tree(node *root, int l);
 
void main()
{
    int n, i, what;
    cout<<"input n \n";
    cin>>n;
    cout<<"input first what \n";
    cin>>what;
    node *root = first(what);
    for (i = 1; i<n; i++)
    {
    cout<<"input what \n";
    cin>>what;
    search_insert(root, what);
    }
    print_tree(root, 0);
 
}
 
node * first(int d)
{
    node *pv = new node;
    pv->d    = d;
    pv->left = 0;
    pv->right = 0;
    return pv;
}
 
node * search_insert(node *root, int d)
{
    node *pv = root, *prev;
    int found = 0;
    while (pv && !found){
       prev = pv;
       if   (d == pv->d) found = 1;
       else if  (d <  pv->d)pv     = pv->left;
       else         pv     = pv->right;
    }
    if (found) return pv;
    node *pnew  = new node;
    pnew->d     = d;
    pnew->left  = 0;
    pnew->right = 0;
    if (d < prev->d)
       prev->left  = pnew;
    else
       prev->right = pnew;
    return pnew;
}
 
void print_tree(node *p, int level)
{
    if (p)
    {
    print_tree(p->left, level+1);
    for (int i = 0; i<level; i++)
    cout << "    ";
    cout <<  p->d << endl;
    print_tree(p->right, level + 1);
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.05.2011, 17:36     Дерево
Посмотрите здесь:

дерево C++
C++ Дерево...
C++ B-дерево
C++ Дерево
Напишите программу, которая бы читала дерево в формате (а) и затем печатала бы это дерево в формате (б). C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
04.05.2011, 17:53     Дерево #2
kjahert, уверены в правильности задания? звучит как-то глупо...
kjahert
48 / 48 / 5
Регистрация: 08.04.2011
Сообщений: 124
04.05.2011, 17:59  [ТС]     Дерево #3
Ну я понял так:
корень:ФИО
в левую ветку идет: должность
в правую: предметы(дисциплины), причем их несколько , должность одна ФИО наверное разные

Добавлено через 59 секунд
должность одна
ФИО несколько
предметы несколько
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
04.05.2011, 18:00     Дерево #4
kjahert, бинарные деревья не для того придуманы, а реализовать эту задачу через бинарное дерево невозможно в принципе.
Цитата Сообщение от kjahert Посмотреть сообщение
должность одна
ФИО несколько
предметы несколько
Несколько корней у дерева?
kjahert
48 / 48 / 5
Регистрация: 08.04.2011
Сообщений: 124
04.05.2011, 18:10  [ТС]     Дерево #5
ХИХИ!
Дословное условие:
Розробити програму побудови двійкового дерева, вузол якого містить в якості ключа прізвище та ім'я по батькові викладача, а в якості інформаційного поля запис:
посада(string[10]);
дисципліни, які викладає(масив з рядкових змінних);
Написати процедуру друку побудованого двійкового дерева (повна інформація про викладача)

Russian version:

Разработать программу построения двоичного дерева, узел которого содержит в качестве ключа фамилию и имя отчество преподавателя, а в качестве информационного поля запись:
должность(string[10]);
дисциплины, которые выкладывает(массив из строчных переменных);
Написать процедуру печати построенного двоичного дерева (полная информация о преподавателе)

Может и вправду бред?
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
04.05.2011, 18:13     Дерево #6
Цитата Сообщение от kjahert Посмотреть сообщение
Разработать программу построения двоичного дерева, узел которого содержит в качестве ключа фамилию и имя отчество преподавателя, а в качестве информационного поля запись:
должность(string[10]);
дисциплины, которые выкладывает(массив из строчных переменных);
Написать процедуру печати построенного двоичного дерева (полная информация о преподавателе)
Ну вот так бы сразу и сказали. Теперь все понятно. Надо построить дерево, в котором элементами будут объекты типа "учитель". Сейчас сделаем... ждите.
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
04.05.2011, 18:48     Дерево #7
писал когда то давно, может пригодится
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
#ifndef TREEITEM_H
#define TREEITEM_H
#pragma once
 
#include <vector>
 
using namespace std;
 
typedef int Index;
 
template <typename TYPE> class TreeItem
{
    template <typename TYPE> friend class Tree;
private:
    Index index; /*Индекс */
    TYPE value; /*Содержимое*/
    TreeItem<TYPE> *parent; /*CCылка на предка */
    vector<TreeItem<TYPE>*> child; /*CCылки на детей */
 
public:
    TreeItem<TYPE>(const Index &val);
    /* */
 
    TreeItem<TYPE>(const TreeItem<TYPE> &Q);
    /*Конструктор копии*/
 
    TreeItem<TYPE> operator=(const TreeItem<TYPE> &Q);
    /*Equal */
    
    Index children();
    /*Возвращает количество детей */
 
    TreeItem<TYPE>* operator[](const Index &index); 
    /*Возвращает ссылку на i-ого сына, i = index*/
    
    TreeItem<TYPE>* getParent(); 
    /*Возвращает ссылку на предка*/
 
    TYPE getValue ();
    /*Возвращает содержиомое элемента дерева*/
 
    void setValue (const TYPE &item);
    /*Задаёт содержимое элемента дерева. Value = item. Не написано!!!*/
 
    TYPE getIndex ();
    /*Возвращает индекс элемента дерева*/
 
    ~TreeItem() {
        delete this;
    }
    
};
 
template <typename TYPE> TreeItem<TYPE>::TreeItem<TYPE>(const Index &val) {
        parent = 0;
        index = val;
        value = 0;
}
 
template <typename TYPE> TreeItem<TYPE>::TreeItem<TYPE>(const TreeItem<TYPE> &Q) {
        index = Q.index;
        value = Q.value;
        parent = Q.parent;
        child = Q.child;
}
 
template <typename TYPE> Index TreeItem<TYPE>::children() {
        //Возвращает количество сыновей
        return child.size();
}
 
template <typename TYPE> TreeItem<TYPE>* TreeItem<TYPE>::operator[](const Index &index) {
        //Возвращает ссылку на i-ого сына, i = index
        return child[index];
}
 
template <typename TYPE> TreeItem<TYPE>* TreeItem<TYPE>::getParent() {
        return parent;
}
 
template <typename TYPE> TYPE TreeItem<TYPE>::getValue() {
    return value;
    
}
 
template <typename TYPE> TYPE TreeItem<TYPE>::getIndex() {
    return index;
    
}
 
/*template <typename TYPE> TreeItem TreeItem::operator=(const TreeItem<TYPE> &Q) {
        TreeItem tmp(Q.value);
        //value = Q.value;
        //parent = Q.parent;
        tmp.numOfChilds = Q.numOfChilds;
        tmp.child = Q.child;
 
        return tmp;
}*/
 
#endif
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
#ifndef TREE_H
#define TREE_H
#pragma once
 
#include "TreeItem.h"
#include <vector>
 
using namespace std;
 
typedef int Index;
 
template <typename TYPE> class Tree
{
    
public:
    Tree();
 
    void add(const Index &index);
    /*Добавляет сына к предку с индексом val */
 
    TreeItem<TYPE>& operator[](const Index &index);
    /*Возвращает ссылку на TreeItem с номером index */
 
    Index size();
    /*Возвращает размер дерева */
 
    bool empty();
    /*TRUE if enpty  */
 
    void clear ();
    /*Удаляет все элементы дерева, КРОМЕ КОРНЯ! */
 
    ~Tree();
    /* */
 
private:
    vector<TreeItem<TYPE>*> tree;
    /* */
};
 
template <typename TYPE> Tree<TYPE>::Tree() { 
        TreeItem<TYPE> *tmp = new TreeItem<TYPE>(0);
        tree.push_back(tmp);
}
 
template <typename TYPE> void Tree<TYPE>::add(const Index &index) {
        //TreeItem tmp(tree.size());
        TreeItem<TYPE> *tmp = new TreeItem<TYPE>(tree.size());
        //tree[val].child.push_back(&tmp);
        tree.push_back(tmp); //
        tree[tree.size() - 1]->parent = tree[index];
        tree[index]->child.push_back(tree[tree.size() - 1]);
        //(tree[index]->)++;
        
}
 
template <typename TYPE> TreeItem<TYPE>& Tree<TYPE>::operator[](const Index &index) {
        return *tree[index]; 
}
 
template <typename TYPE> Index Tree<TYPE>::size() {
        return tree.size();
}
 
template <typename TYPE> bool Tree<TYPE>::empty() {
        return (tree.size() == 0);
}
 
template <typename TYPE> void Tree<TYPE>::clear () {
    tree.erase((tree.begin() + 1), tree.end());
}
 
template <typename TYPE> Tree<TYPE>::~Tree() {
        clear();
}
 
#endif
Добавлено через 5 минут
только в привате вектор лежит. Некоторым этом может не понравится, можно легко переделать чтобы была только ссылка на корень и выпилить оператор[], вот тогда будет полноценное дерево
kjahert
48 / 48 / 5
Регистрация: 08.04.2011
Сообщений: 124
04.05.2011, 19:49  [ТС]     Дерево #8
fasked, Это и есть ответ?(от pito211) или есть по примеру моей структуры?
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
05.05.2011, 00:50     Дерево #9
kjahert, конкретно по примеру Вашей структуры нет, но есть более-менее похожий вариант. Получайте

teacher.h
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#ifndef KJAHERT_TEACHER_H
#define KJAHERT_TEACHER_H
 
#define TEACHER_NAME_LENGTH 30
#define TEACHER_DISC_LENGTH 10
#define TEACHER_POST_LENGTH 10
#define TEACHER_NUMBER_DISC  3
 
struct teacher {
    char name[TEACHER_NAME_LENGTH];
    char post[TEACHER_POST_LENGTH];
    char disc[TEACHER_NUMBER_DISC][TEACHER_DISC_LENGTH];
};
 
#endif /* KJAHERT_TEACHER_H */
tree.h
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#ifndef KJAHERT_TREE_H
#define KJAHERT_TREE_H
 
#include <stdio.h>
#include "teacher.h"
 
struct binary_tree_node;
 
struct binary_tree
{
    struct binary_tree_node *root;
};
 
struct binary_tree *binary_tree_new();
void binary_tree_delete(struct binary_tree *);
void binary_tree_clear(struct binary_tree *tree);
void binary_tree_remove(struct binary_tree *tree, const char *key); 
void binary_tree_insert(struct binary_tree *tree, struct teacher *item);
 
void binary_tree_print(FILE *stream, struct binary_tree *tree);
 
#endif /* KJAHERT_TREE_H */
tree.c
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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
 
#include "tree.h"
 
struct binary_tree_node {
    struct teacher item;
    struct binary_tree_node *left;
    struct binary_tree_node *right;
};
 
struct binary_tree_node *binary_tree_node_new(struct binary_tree_node *left,
                                              struct binary_tree_node *right)
{
    struct binary_tree_node *node = 
           (struct binary_tree_node *)calloc(1, sizeof(struct binary_tree_node));
 
    if (node) {
        node->left = left;
        node->right = right;
    }
    
    return node;
}
 
void binary_tree_insert(struct binary_tree *tree, struct teacher *item) {
    struct binary_tree_node *node = tree->root;
    struct binary_tree_node *parent = NULL;
    
    assert(tree);
    assert(item);
    
    while (node) {
        parent = node;
        if (strcmp(node->item.name, item->name) == -1)
            node = node->left;
        else
            node = node->right;
    }
    
    node = binary_tree_node_new(NULL, NULL);
    node->item = *item; // memcpy(&node->item, item, sizeof(*item)); //
    printf("%p NODE created\n", node);
    
    if (!parent) {
        tree->root = node;
    }
    else {
        if (strcmp(parent->item.name, item->name) == -1)
            parent->left = node;
        else
            parent->right = node;
    }
}
 
void binary_tree_remove(struct binary_tree *tree, const char *key) {
    struct binary_tree_node *node = tree->root;
    struct binary_tree_node *child = NULL;
    struct binary_tree_node *parent = NULL;
    struct binary_tree_node *removed = NULL;
    struct binary_tree_node *most_left = NULL;
    struct binary_tree_node *most_left_parent = NULL;
 
    assert(key);
    assert(tree);
 
    while (node && strcmp(node->item.name, key)) {
        parent = node;
        if (strcmp(node->item.name, key) == -1)
            node = node->left;
        else
            node = node->right;
    }
 
    if (node) {
        if (!node->left || !node->right) {
            removed = node;
            if (node->left)
                child = node->left;
            else if (node->right)
                child = node->right;
            
            if (!parent) {
                tree->root = child;
            }
            else {
                if (parent->left == node)
                    parent->left = child;
                else
                    parent->right = child;
            }
        }
        else {
            most_left = node->right;
            most_left_parent = node;
            
            while (most_left->left) {
                most_left_parent = most_left;
                most_left = most_left->left;
            }
            
            node->item = most_left->item;
            removed = most_left;
            
            if (most_left_parent->left == most_left)
                most_left_parent->left = NULL;
            else
                most_left_parent->right = NULL;
        }
 
        printf("%p NODE deleted\n", removed);
    } 
}
 
void binary_tree_clear(struct binary_tree *tree) {
    assert(tree);
    while (tree->root) {
        binary_tree_remove(tree, tree->root->item.name);
    }
}
 
struct binary_tree *binary_tree_new() {
    struct binary_tree *p = (struct binary_tree *)calloc(1, sizeof(struct binary_tree));
    printf("%p TREE created\n", p);
    
    return p;
}
 
void binary_tree_delete(struct binary_tree *tree) {
    if (tree) {
        binary_tree_clear(tree);
        
        printf("%p TREE deleted\n", tree);
        free(tree);
    }
}
 
void binary_tree_postorder_print(FILE *stream, struct binary_tree_node *node) {
    int i;
    if (node) {
        binary_tree_postorder_print(stream, node->left);
        binary_tree_postorder_print(stream, node->right);
        
        fprintf(stream, "%10s: %s\n%10s: %s\n%10s:\n", "name", node->item.name, "post", node->item.post, "disciplines");
        for (i = 0; *(node->item.disc[i]); ++i) {
            fprintf(stream, "%10s: %s\n", "", node->item.disc[i]);
        }
    }
}
 
void binary_tree_print(FILE *stream, struct binary_tree *tree) {
    assert(tree);
    binary_tree_postorder_print(stream, tree->root);
}
main.c
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
#include "tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct teacher *input_info(FILE *stream, struct teacher *t) {
    int i;
    
    printf ("INPUT info for %p\n", t);
    printf ("NAME: ");
    fgets(t->name, TEACHER_NAME_LENGTH, stream);
    t->name[strlen(t->name) - 1] = '\0';
    
    printf ("POST: ");
    fgets(t->post, TEACHER_POST_LENGTH, stream);
    t->post[strlen(t->post) - 1] = '\0';
    
    for (i = 0; i < TEACHER_NUMBER_DISC; ++i) {
        printf ("DISC: ");
        fgets(t->disc[i], TEACHER_DISC_LENGTH, stream);
        t->disc[i][strlen(t->disc[i]) - 1] = '\0';
    }
    
    return t;
}
 
int main()
{
    struct binary_tree *tree;
    struct teacher t;
    int i;
    
    if ((tree = binary_tree_new()) == NULL) {
        fprintf(stderr, "allocate memory error\n");
        exit(1);
    }
    
    for (i = 0; i < 3; ++i) {
        memset(&t, 1, sizeof(t));
        binary_tree_insert(tree, input_info(stdin, &t));
    }
    
    binary_tree_print(stdout, tree);
    
    binary_tree_delete(tree);
    return 0;
}
В файле main.c приводится пример работы с деревом. Создается 3 записи типа teacher. Количество дисциплин у каждого по три, можно сделать неограниченное, но это надо возиться, для примера пойдет и так (тем более смысл работы тут именно в дереве). Функции для дерева только необходимое: добавление элемента, удаление элемента по ключу и post-order обход дерева для вывода содержимого.

В коде программы много отладочной информации, в первую очередь для контроля памяти - чтобы утечек не было. Перед каждым вызов malloc/calloc и перед каждым вызовом free. По номерам указателей можно видеть, что утечек нет. Конечно отладочную информацию можно убрать.

В таком примере программа работает следующим образом:
Код
// старт программы
00542E70 TREE created

// ввод информации с клавиатуры
INPUT info for 0028FEF2
NAME: IVANOV
POST: DIRECTOR
DISC: 01
DISC: 02
DISC: 03
00540E78 NODE created
INPUT info for 0028FEF2
NAME: SIDOROV
POST: TEACHER
DISC: 02
DISC: 03
DISC: 05
00540ED0 NODE created
INPUT info for 0028FEF2
NAME: PETROV
POST: TEACHER
DISC: 01
DISC: 06
DISC: 07
00540F28 NODE created

// вывод информации начинается с этого момента

      name: PETROV
      post: TEACHER
disciplines:
          : 01
          : 06
          : 07
      name: SIDOROV
      post: TEACHER
disciplines:
          : 02
          : 03
          : 05
      name: IVANOV
      post: DIRECTOR
disciplines:
          : 01
          : 02
          : 03
00540E78 NODE deleted
00540ED0 NODE deleted
00540F28 NODE deleted
00542E70 TREE deleted
Комментарии я повставлял сам, чтобы Вам понятнее было, где какая часть работает.
Возникнут вопросы - задавайте их здесь.

Удачи
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
05.05.2011, 06:24     Дерево #10
Цитата Сообщение от kjahert Посмотреть сообщение
fasked, Это и есть ответ?(от pito211) или есть по примеру моей структуры?
это только дерево. Используй его для своих целей
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
05.05.2011, 06:34     Дерево #11
Цитата Сообщение от kjahert Посмотреть сообщение
Условие:
Программа построения дерева, где узел(корень) - ФИО препода, а инф. поля (наверное левая\правая ветки) имеют записи: 1)должность(string[10]), 2)предметы что преподает. Написать процедуру печати построеного бинарного дерева(полная инфа про препода)
Во-первых корень троже узел, но не каждый узел - корень. Во-вторых элменты дерева должны быть однотипными. В-третьих любая ветвь - это только совокупность узлов. В-четвёртых деревол не может иметь полей.
kjahert
48 / 48 / 5
Регистрация: 08.04.2011
Сообщений: 124
05.05.2011, 10:21  [ТС]     Дерево #12
Спасибо всем и fasked'у особенно

Добавлено через 16 минут
fasked,
Буду разбираться потому как преподу надо только с одной структурой node* как у меня
Теоретически возможно переделать (я не прошу вас этого делать) под мой пример структур и функций, в одной программе, без использования других структур, teacher.h tree.h... ??
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
05.05.2011, 13:33     Дерево #13
Цитата Сообщение от kjahert Посмотреть сообщение
Теоретически возможно переделать (я не прошу вас этого делать) под мой пример структур и функций, в одной программе, без использования других структур, teacher.h tree.h... ??
Без структуры teacher обойтись, увы, не получится.
А tree - это всего лишь обертка для node. Так что конечно, можно выкинуть. В таком случае заменяйте в сигнатурах функций указатель binary_tree *, на binary_tree_node *, ну и соответственно в теле каждой из функции tree->root изменяйте на доступ без структур, то есть просто root. Контролировать в main тогда следует не структуру binary_tree, а binary_tree_node соответственно, которая будет указателем на корень дерева.

Добавлено через 35 минут
Цитата Сообщение от pito211 Посмотреть сообщение
это только дерево. Используй его для своих целей
На самом деле это сложно назвать бинарным деревом, еще похоже, что память течет, да и вообще ТС на Си пишет.
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
20.05.2011, 10:13     Дерево #14
Цитата Сообщение от fasked Посмотреть сообщение
Без структуры teacher обойтись, увы, не получится.
А tree - это всего лишь обертка для node. Так что конечно, можно выкинуть. В таком случае заменяйте в сигнатурах функций указатель binary_tree *, на binary_tree_node *, ну и соответственно в теле каждой из функции tree->root изменяйте на доступ без структур, то есть просто root. Контролировать в main тогда следует не структуру binary_tree, а binary_tree_node соответственно, которая будет указателем на корень дерева.

Добавлено через 35 минут

На самом деле это сложно назвать бинарным деревом, еще похоже, что память течет, да и вообще ТС на Си пишет.
бинарное дерево является подмножеством понятия дерево.
поэтому имея данный класс не составит труда сделать с помощью него бин дерево, или замутить производный класс BinTree например. А вот из бинарного дерева сделать дерево не получится

а насчёт утечек я и неспорю, там нигде нет деструкторов. Но класс писался по принципу "быстрее и чтоб работало", а кому надо тот и добавит три строки в treeitem.h и три строки в tree.h если кто собирается строить на нём грандизные проекты, а в учебных целях преподу показать думаю прокатит и так

Добавлено через 14 минут
да и вообще ТС на Си пишет
cin cout и struct... в заголовке С и не пахло
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.05.2011, 10:25     Дерево #15
Цитата Сообщение от kjahert Посмотреть сообщение
ФИО наверное разные
Корень может быть только один, иначе это нифига не дерево, дпаже не коряга. Если ФИО - корень и ФИО могут быть разные, то у тебя разве что лес получится.

Добавлено через 4 минуты
Цитата Сообщение от kjahert Посмотреть сообщение
Разработать программу построения двоичного дерева, узел которого содержит в качестве ключа фамилию и имя отчество преподавателя, а в качестве информационного поля запись:
должность(string[10]);
дисциплины, которые выкладывает(массив из строчных переменных);
Написать процедуру печати построенного двоичного дерева (полная информация о преподавателе)
А теперь сраывни с этим бредом:
Цитата Сообщение от kjahert Посмотреть сообщение
Условие:
Программа построения дерева, где узел(корень) - ФИО препода, а инф. поля (наверное левая\правая ветки) имеют записи: 1)должность(string[10]), 2)предметы что преподает. Написать процедуру печати построеного бинарного дерева(полная инфа про препода)
Тебе в каждом узле задано хранить должность и предметы, то есть построить дерево структур, а не одну структуру представить деревом.

Добавлено через 3 минуты
Цитата Сообщение от pito211 Посмотреть сообщение
бинарное дерево является подмножеством понятия дерево.
поэтому имея данный класс не составит труда сделать с помощью него бин дерево.
Бинарное или двоичное дерево отличается тем, что каждый его узел имеет жёсткое ограничеение на количество своих потомков, а эти потомки называются левым и правым, чего нет в дереве общего вида. Поэтому двоичное дерево проще сделать с ноля, чем переделывать в него корягу общего вида.
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
20.05.2011, 10:49     Дерево #16
Цитата Сообщение от taras atavin Посмотреть сообщение
Бинарное или двоичное дерево отличается тем, что каждый его узел имеет жёсткое ограничеение на количество своих потомков, а эти потомки называются левым и правым, чего нет в дереве общего вида. Поэтому двоичное дерево проще сделать с ноля, чем переделывать в него корягу общего вида.
от общего к частному легко перейти. В данном случае children[0] можно считать как левый, а children[1] как правый потомок и контролировать это в теле программы. Но учитывая наличие готового к работе класса Tree, тут просто грех не воспользоваться наследованием
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.05.2011, 10:56     Дерево #17
В данном случае частное проще, чем переход к частному.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
20.05.2011, 11:53     Дерево #18
Цитата Сообщение от pito211 Посмотреть сообщение
т общего к частному легко перейти. В данном случае children[0] можно считать как левый, а children[1] как правый потомок и контролировать это в теле программы. Но учитывая наличие готового к работе класса Tree, тут просто грех не воспользоваться наследованием
Помимо того, что в бинарном дереве строгое количество потомков, есть еще и определенные алгоритмы вставки/удаления/поиска элементов. И что именно здесь наследовать? Название разве что...
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
20.05.2011, 13:12     Дерево #19
да собственно почти все функции дерева пригодятся и в бинарном дереве.

C++
1
2
TreeItem<TYPE>* operator[](const Index &index); 
        /*Возвращает ссылку на i-ого сына, i = index*/
вместо него сделать две функции right и left, типа TreeItem<TYPE>* right {return this->operator[](0)}, TreeItem<TYPE>* left {return this->operator[](1)} то есть всё равно оператор индексирования пригодился
остальные все тоже не лишнии, за исключением add. Заместо неё addLeft и addRight можно написать. всяко проще дописать десять строк, чем писать с нуля класс к тому же узкопрофильный.

*******
алгоритмов поиска для бинарного дерева много - прямой обратный внутренний нафиг их в классе писать все, если пользователю будет нужен один из них. Пусть сам и напишет в теле программы какой ему надо.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.05.2011, 14:12     Дерево
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
20.05.2011, 14:12     Дерево #20
Цитата Сообщение от pito211 Посмотреть сообщение
да собственно почти все функции дерева пригодятся и в бинарном дереве.
Начнем с того, что в Вашем классе методов всего пять! Сейчас я объясню, почему же не подойдут оставшиеся четыре. Это не так уж и много. А заодно разберемся чем же так плох Ваш класс, Вы уж простите меня, но написан он через одно место, и Вы, кстати, сами в этом признались.

Метод add не подходит по, я надеюсь, всем понятным причинам. В бинарном дереве совершенно отличный, то есть другой, алгоритм вставки. Это объяснять, я думаю, не стоит.
Что принимает в качестве аргумента метод add? Я не верю своим глазам, но это индекс. Да-да, индекс. В комментарии написано, что метод должен добавить "сына" к "предку" с указанным индексом. Возникает вопрос: какого именно сына? Видимо никакого. Можно сказать, что этот метод резервирует место для последующей операции добавления или вставки, но никак не делает то, что следует из названия.

Идем дальше...
Метод size. Тут все просто, метод должен возвратить текущее количество элементов в дереве. Во всем дереве. Интересно, работает ли. Я не проверял, конечно, но закрадываются сомнения. Особенно с учетом того, что в самом TreeItem также лежит вектор. Я верю, что тут может быть хитрая схема индексации, но не доверяю.

Метод empty. Признаюсь, я был поражен. Кроме того, что Ваше дерево никогда не будет пустым, следовательно этот метод бесполезен, его реализация это тоже нечто. Да, работать будет. Но Вы в курсе зачем вообще существуют методы по имени empty? Совсем не только ради удобства, можно было бы всегда писать xxx.size() == 0, но нет, дело в другом. В структурах данных, основанных на списках (коим является и дерево) метод empty отрабатывает за O(1) операций, это элементарная операция. Метод size отрабатывает, как минимум, за линейное время O(n). Дело именно в скорости. У метода empty - фиксированное время работы, у метода size - нет.

Метод clear. Тоже странноватый. Судя по комментарию, опять же, должен удалить все кроме корня. М-м-м... И я опять в замешательстве. Реализация вроде как соответствует описанию. Правда есть утечка памяти.

Еще два интересных момента: конструктор и деструктор. В конструкторе создается (зачем?) корень. Я уже говорил, что дерево никогда не будет пустым, потому как корень у него создан изначально. В деструкторе вызывается метод clear - корень не удаляется. Опять потекла...

Operator[]... Имеет право на жизнь в бинарном дереве, но не в таком виде. Все дело в том, что к элементу дерева (даже иерархического, а тем более бинарного) нельзя обращаться по индексу. Ну вот нарисуйте дерево на бумажке... И какой индекс будет у каждого элемента? В бинарном дереве ясное дело к элементу обращаются по ключу. В n-арном дереве, наверное тоже по ключу, по ключу предка. Это же иерархия, верно? Значит элементы дерева должны быть упорядочены по определенному признаку.

Вообще, глупо на мой взгляд рассуждать о наследовании бинарного дерева от n-арного, конечно это частный случай, но он требует слишком значительных изменений. Бинарное дерева - структура данных специфичная, но используется она, кстати, чаще, гораздо чаще, чем n-арное дерево.

В класс TreeItem лезть уже не будем. Там еще можно какими-то костылями привернуть его к бинарному дереве. Но и так уже понятно, что Ваш класс дерева не имеет права на жизнь., его надо переписывать.
Можно было бы поспорить с Вами, если бы он был написан хорошо, ну или хотя бы просто правильно. Если бы все его методы работали ожидаемо, не было бы утечек памяти и т.д.

Да и вообще использовать вектор в качестве структуры для хранения решение не однозначное.
Вы знаете почему списки пишут на основе узлов, то есть это так называемые node-based структуры. Почему их не пишут на основе массивов и векторов? Малейшее изменение может привести к "катастрофе", например, вставка в середину - не очень благодарное занятие для векторов. Это же надо сдвинуть очень много элементов в право, а в node-based структуре это просто переопределение адресной части двух элементов.

А так, проще написать новый класс с нуля, чем использовать Ваш.

Добавлено через 12 минут
Цитата Сообщение от pito211 Посмотреть сообщение
алгоритмов поиска для бинарного дерева много - прямой обратный внутренний нафиг их в классе писать все, если пользователю будет нужен один из них. Пусть сам и напишет в теле программы какой ему надо.
После этой Вашей фразы можно заканчивать разговор
Читайте книги, алгоритм поиска в бинарном дереве один! Реализовать его правда можно рекурсивно или не рекурсивно. Вот и вся разница... мдэ... а я то распинался...
Yandex
Объявления
20.05.2011, 14:12     Дерево
Ответ Создать тему
Опции темы

Текущее время: 13:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru