Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/9: Рейтинг темы: голосов - 9, средняя оценка - 5.00
4 / 4 / 4
Регистрация: 06.03.2011
Сообщений: 319
1

Дерево - исправить ошибки в коде

27.04.2011, 22:07. Показов 1695. Ответов 17
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравсвуйте пытаюсь разобраться в деревьях............пока только создаю. выпадают ошибки.как их исправить?

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
#include "stdafx.h"
#include "iostream"
#include<conio.h>
 
using namespace std;
 
struct Tree
{
    int data;
    Tree* left;
    Tree* right;
}
 
 
 
void Add(Tree*root, int i);
{
    Tree*new_el;
    new_el=new Tree;
    new_el->data=i;
    new_el->left=NULL;
    new_el->right=NULL;
 
    if(i<root->data)
    {if(root->left==NULL)
            root->left=new_el;
        else 
        {
            Add(root->left,i);
            delete new_el;
        }
    }
    if(i>root->data)
    {if(root->right==NULL)
            root->right=new_el;
        else 
        {
            Add(root->right,i);
            delete new_el;
        }
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
 
    Tree*root;
    root=new Tree;
    root->data=NULL;
    root->left=NULL;
    root->right=NULL;
    for(int i=-100;i<=100;i++)
        Add(root,i);
    return 0;
}
Добавлено через 4 минуты
Вот ошибки

Error 1 error C2628: 'Tree' followed by 'void' is illegal (did you forget a ';'?)
Error 2 error C2447: '{' : missing function header (old-style formal list?)
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.04.2011, 22:07
Ответы с готовыми решениями:

Ошибки при компиляции - исправить ошибки в коде
Помогите исправить ошибки , не понимаю в чем может быть причина ... #include &lt;conio.h&gt;...

Исправить ошибки в коде
Делаю программу на языке Си в компиляторе Borland C++ #include &lt;stdio.h&gt; #include &lt;conio.h&gt;...

Исправить ошибки в коде
...

Исправить ошибки в коде
Требования: - добавить комментарии к программному коду; - проверить правильность именования...

17
Эксперт С++
623 / 467 / 57
Регистрация: 28.01.2011
Сообщений: 605
27.04.2011, 22:20 2
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

struct Tree
{
int data;
Tree* left;
Tree* right;
};
1
4 / 4 / 4
Регистрация: 06.03.2011
Сообщений: 319
27.04.2011, 22:55  [ТС] 3
Цитата Сообщение от Ma3a Посмотреть сообщение
struct Tree
{
int data;
Tree* left;
Tree* right;
};
Спасибо большое....не подскажите почему при выведе на экране получились нули(((((
или вывод не правильный?
C
1
2
for(int i=-100;i<=100;i++)
cout<<root->data<<" ";

ноль как я понимаю из за этой строчки
C
1
root->data=NULL;
если заместа NULL записать любочи число то будет выволится это число много раз....
если писать !=NULL то выводится число -842150451 много раз
как сделать так чтобы были разные числа?

Добавлено через 20 минут
C
1
2
srand(time(NULL));  
root->data=rand()%100-rand()%100;
меняется значения при каждой компиляции но все значения одинаковы......
0
Эксперт С++
623 / 467 / 57
Регистрация: 28.01.2011
Сообщений: 605
27.04.2011, 23:10 4
Цитата Сообщение от yuliyayuliya28 Посмотреть сообщение
root->data=NULL;
Да, нуль из-за этой строчки.
C++
1
2
for(int i=-100;i<=100;i++)
cout<<root->data<<" ";
так у вас и будет выводиться много раз одно и то же число, потому что вы выводите только значение у корневого узла, а остальные не трогаете.

Судя по всему, вам надо распечатать дерево, для этого придется пройти каждый узел дерева, можно сделать например так:

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
void print_tree(Tree * root, int indent = 0)
    {
    if(root != NULL)
        {
        for(int i = 0; i < indent; ++i)
            cout << ' ';
        cout << root->data << endl;
        if(root->left != NULL)
            print_tree(root->left,indent + 4);
        if(root->right != NULL)
            print_tree(root->right,indent + 4);
        }
    }
...
int _tmain(int argc, _TCHAR* argv[])
{
 
        Tree*root;
        root=new Tree;
        root->data=NULL;
        root->left=NULL;
        root->right=NULL;
        for(int i=-100;i<=100;i++)
                Add(root,i);
        print_tree(root);
        return 0;
}
1
4 / 4 / 4
Регистрация: 06.03.2011
Сообщений: 319
27.04.2011, 23:29  [ТС] 5
Ой ой ой а почему они выводятся такими как бы диагоналями?
0
Эксперт С++
623 / 467 / 57
Регистрация: 28.01.2011
Сообщений: 605
27.04.2011, 23:34 6
Сделано для того, чтобы "подчеркнуть" иерархичность струкруры, так по-моему лучше видно, где какая ветка дерева и что кому принадлежит.
Если не особо перевариваете, то перепишите так
C++
1
2
3
4
5
6
7
8
9
10
11
void print_tree(Tree * root)
        {
        if(root != NULL)
                {
                cout << root->data << endl;
                if(root->left != NULL)
                        print_tree(root->left);
                if(root->right != NULL)
                        print_tree(root->right);
                }
        }
тогда будут просто выводиться по одному на строке элементы дерева в порядке обхода слева-направо.
1
4 / 4 / 4
Регистрация: 06.03.2011
Сообщений: 319
29.04.2011, 21:08  [ТС] 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
void deep_walk(Tree * root)
       {
 
        stack = create_stack();
        stack_push(stack, root);
            while((Tree*root=stack_pop(stack))!=NULL)
            {
                do
                {
                    printf("%c",root->data);
                    if (root->left !=NULL)
                    {
                       if (root->left !=NULL);
                       stack_push(stack, root->right)
                       root=root->left;
                    }
                    else
                        root=root->right;
                        )
                }
                while (root!=NULL)
            }
       }
0
Эксперт С++
623 / 467 / 57
Регистрация: 28.01.2011
Сообщений: 605
29.04.2011, 21:46 8
Во-первых, синтаксические ошибки. А во-вторых, мне что-то не очень понятно, что у вас тут творится, явно не обход в глубину.

Поиск в глубину( считаем, что сначала посещаем узел дерева, а потом переходим к левой подветке, а еще потом к правой) состоит в том, что посещаем узлы "до упора", пока левая ветка не кончится, потом перебираемся на правую ветку, и так тоже пока не кончится.
Попробуйте так, если нужно со стеком( и еще определитесь с тем, вы на C или на C++ пишете, а пока приведу код на c++ ):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stack>
...
void DepthFirstSearch(Tree* root) {
    stack<Tree*> nodeStack;
    Tree *curr = root;
    for (;;) {
        if (curr != NULL) {
            cout << curr->data << ' ';
            nodeStack.push(curr);
            curr = curr->left;
            continue;
            }   
        if (nodeStack.empty()) {
            return;
            }   
        curr = nodeStack.top();
        nodeStack.pop();
        curr = curr->right;
        }
    }
1
4 / 4 / 4
Регистрация: 06.03.2011
Сообщений: 319
29.04.2011, 22:00  [ТС] 9
В методичке было так......пыталась по переправить на свой случай но не получилось
Обход в глубину.Для того чтобы обойти некоторое поддерево, сначала пройдем корень этого поддерева,затем спустимся в его левое поддерево,а правое поддерево запомним в стеке. Если оба поддерева пусты, то очередное поддерево надо извлечь из стека.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void deep_walk(node *root){
   stsck=create_stack();
   stack_push(stack,root)
//Пока в стеке есть узлы
   while((node *n = stack_pop(stack)) !=NULL){
      do{
//Выводим текущую вершину
     printf("%c",n->key);
     if (n->left !=NULL){
//Помещаем в стек левое поддерево
          if (n->right !=NULL)
              stack_push(stack,n->right);
         n=n->left;
         }else n=n->right;
    }while (n!=NULL)
    }
}
0
Эксперт С++
623 / 467 / 57
Регистрация: 28.01.2011
Сообщений: 605
29.04.2011, 22:13 10
И снова синтаксические ошибки, ну да ладно, если хотите на своем примере, то чуток подправить его и должно работать:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void deep_walk(Tree *root){
   stsck=create_stack();
   stack_push(stack,root);
//Пока в стеке есть узлы
    while((Tree *n = stack_pop(stack)) !=NULL){
      do{
//Выводим текущую вершину
     printf("%d ",n->data);
     if (n->left !=NULL){
//Помещаем в стек левое поддерево
          if (n->right !=NULL)
              stack_push(stack,n->right);
         n=n->left;
         }else n=n->right;
    }while (n!=NULL);
    }
}
0
4 / 4 / 4
Регистрация: 06.03.2011
Сообщений: 319
29.04.2011, 22:15  [ТС] 11
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void DepthFirstSearch(Tree* root) {
    stack<Tree*> nodeStack;
    Tree *curr = root;//тут мы кокому то указателю присваемаем голову;
    for (;;) {
        if (curr != NULL) {//Если он не нулевой
            cout << curr->data << ' ';//выписываем его значение
            nodeStack.push(curr); ?
            curr = curr->left; ?
            continue;
            }   
        if (nodeStack.empty()) {//если он пустой
            return;
            }   
        curr = nodeStack.top();?
        nodeStack.pop();?
        curr = curr->right;?
        }
Не могли вы пояснить ваш код?
0
Эксперт С++
623 / 467 / 57
Регистрация: 28.01.2011
Сообщений: 605
29.04.2011, 22:22 12
Цитата Сообщение от yuliyayuliya28 Посмотреть сообщение
Tree *curr = root;//тут мы кокому то указателю присваемаем голову;
Это указатель, который будет указывать на каждый узел, который мы будем проходить в процессе обхода(а голову присваиваем, потому что начинаем от корня дерева).

Цитата Сообщение от yuliyayuliya28 Посмотреть сообщение
nodeStack.push(curr); ?
Помещаем этот узел в стек после того, как распечатали его значение, чтобы потом, когда текущая ветка кончится, можно было вернуться по нему обратно.
Цитата Сообщение от yuliyayuliya28 Посмотреть сообщение
curr = curr->left; ?
Заходим дальше в левое поддерево
Цитата Сообщение от yuliyayuliya28 Посмотреть сообщение
if (nodeStack.empty()) {//если он пустой
если стек вершин, куда мы можем возвращаться, пуст( то есть мы уже посетили все вершины, которые есть в дереве ), то просто выходим из цикла.
Цитата Сообщение от yuliyayuliya28 Посмотреть сообщение
curr = nodeStack.top();?
nodeStack.pop();?
В "текущий" узел помещаем указатель на узел на вершине стека и выбрасываем его из стека(то есть просто возвращаемся назад по дереву).
Цитата Сообщение от yuliyayuliya28 Посмотреть сообщение
curr = curr->right;?
пробуем перейти в правое поддерево.( вот на этом моменте тоже полезно сравнение curr с NULL, так как если правой подветки нет, то curr будет равен NULL и мы просто возьмем из стека последний посещенный узел и продолжим дальше )
1
4 / 4 / 4
Регистрация: 06.03.2011
Сообщений: 319
29.04.2011, 22:27  [ТС] 13
Цитата Сообщение от Ma3a Посмотреть сообщение
Это указатель, который будет указывать на каждый узел, который мы будем проходить в процессе обхода(а голову присваиваем, потому что начинаем от корня дерева).


Помещаем этот узел в стек после того, как распечатали его значение, чтобы потом, когда текущая ветка кончится, можно было вернуться по нему обратно.

Заходим дальше в левое поддерево

если стек вершин, куда мы можем возвращаться, пуст( то есть мы уже посетили все вершины, которые есть в дереве ), то просто выходим из цикла.

В "текущий" узел помещаем указатель на узел на вершине стека и выбрасываем его из стека(то есть просто возвращаемся назад по дереву).

пробуем перейти в правое поддерево.( вот на этом моменте тоже полезно сравнение curr с NULL, так как если правой подветки нет, то curr будет равен NULL и мы просто возьмем из стека последний посещенный узел и продолжим дальше )
Спасибо большое что всё разжевали.......хоть чтото поняла...дальше попробую обходы смотреть
0
4 / 4 / 4
Регистрация: 06.03.2011
Сообщений: 319
02.05.2011, 23:19  [ТС] 14
Правильно ли создаю функцию поиска значения в дереве?не работает....помогите пожалуйста
C
1
2
3
4
5
6
7
8
void Tree_search(Tree*root, int k)
{   if (root == NULL || k == root->data)
      return root;
   if (k < root->data)
      return Tree_search(root->left, k);
   else
      return Tree_search(root->right, k);
}
0
Эксперт С++
623 / 467 / 57
Регистрация: 28.01.2011
Сообщений: 605
02.05.2011, 23:45 15
yuliyayuliya28, не работает, видимо, потому, что функцию вы написали типа void, а она должна возвращать указатель на узел дерева, то есть Tree *.

C
1
2
3
4
5
6
7
8
Tree * Tree_search(Tree*root, int k)
{   if (root == NULL || k == root->data)
      return root;
   if (k < root->data)
      return Tree_search(root->left, k);
   else
      return Tree_search(root->right, k);
}
Нехороший поиск, но учитывая то, как вы формируете дерево, должен работать.
1
4 / 4 / 4
Регистрация: 06.03.2011
Сообщений: 319
03.05.2011, 00:11  [ТС] 16
Спасибо...а как сделать так нашел или нет элемент ?
0
Эксперт С++
623 / 467 / 57
Регистрация: 28.01.2011
Сообщений: 605
03.05.2011, 00:18 17
yuliyayuliya28, здесь достаточно посмотреть возвращаемое значение Tree_search. Если указатель, который вернула эта функция равен NULL, то значение не было найдено, иначе, нашелся элемент с указанным значением.

Добавлено через 4 минуты
То есть можно так проверить:

C++
1
2
3
4
5
Tree * found;
...
found = Tree_search(root,k); // как-то там раньше задаем k
if(found) cout << "элемент найден, значение узла = " << found->data;
else cout << "элемент с заданным значением не найден";
1
4 / 4 / 4
Регистрация: 06.03.2011
Сообщений: 319
03.05.2011, 00:30  [ТС] 18
Спасибо....в целом и с поиском немного поняла
0
03.05.2011, 00:30
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.05.2011, 00:30
Помогаю со студенческими работами здесь

Исправить ошибки в коде
#include&lt;conio.h&gt; #include&lt;stdio.h&gt; #include&lt;string.h&gt; int main() { struct uchenik {...

Исправить ошибки в коде
Перескакивает через строчку. Подскажите пожалуйста что не так? #include &lt;stdio.h&gt; int main ()...

Исправить ошибки в коде
#include &lt;stdio.h&gt; int N,M; int a; int KP,KV; int o,oN,t; int i,j; void next(int x){ ...

Исправить ошибки в коде
При написании кода для задачи:Даны натуральное число n, действительные числа A1,A2,...,An.Получить...


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

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