Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
2 / 2 / 2
Регистрация: 12.04.2014
Сообщений: 102
1

Создание бинарного дерева и ограничение на количество узлов в ней

12.05.2015, 12:46. Просмотров 1020. Ответов 9
Метки нет (Все метки)

В задании по созданию бинарного дерева есть условие на то, что узлов в дереве должно быть не больше 10. Пробую поставить такое ограничение в функции add_node с помощью счетчика и условия, что добавлять новые звенья нужно только до 10. Компилятор ругается на саму функцию. Вот ошибки, которые он мне выдает(все в TreeNode.cpp):
TreeNode::add_node: недопустимые локальные определения функций
функция-член "TreeNode::add_node" не может быть повторно объявлена вне соответствующего класса
Где ошибка? Правильно ли я реализовала саму идею на ограничение размера дерева?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//TreeNode.h
#pragma once
#ifndef __TREENODE_H__
#define __TREENODE_H__
#include <iomanip>
#include <string>
 
 
class TreeNode //Звено дерева
{  private:
    int key; //Ключ
    std::string polinom;//Строку записываем
    TreeNode *leftPtr,*rightPtr;
    public:
   void show(TreeNode *&Tree);
   void add_node(int x,std::string p,TreeNode *&MyTree);
};
#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
//TreeNode.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include "TreeNode.h"
 
 
 
 
void TreeNode::show(TreeNode *&Tree) //Функция обхода
{  
    {if (Tree!=NULL) 
    {
        show(Tree->leftPtr);
        std::cout<<Tree->key; 
        std::cout<<" ";
        std::cout<<Tree->polinom;
        std::cout<<"\n"; 
        show(Tree->rightPtr); 
    }
    }
 
    void TreeNode::add_node(int x,std::string p,TreeNode *&MyTree) //Фукция добавления звена в дерево
    { int count=0;
        {if(count<=10)
 
    if (NULL==MyTree)  
    {
        MyTree=new TreeNode; 
        MyTree->key=x;
        MyTree->polinom=p;
        MyTree->leftPtr=MyTree->rightPtr=NULL;
        count++;
    }
 
    if (x<MyTree->key)   
    {
        if (MyTree->leftPtr!=NULL) add_node(x,p,MyTree->leftPtr); 
        else 
        {
            MyTree->leftPtr=new TreeNode;  
            MyTree->leftPtr->leftPtr=MyTree->leftPtr->rightPtr=NULL; 
            MyTree->leftPtr->key=x;
            MyTree->leftPtr->polinom=p;
            count++;
        }
    }
 
    if (x>MyTree->key)   
    {
        if (MyTree->rightPtr!=NULL) add_node(x,p,MyTree->rightPtr); 
        else 
        {
            MyTree->rightPtr=new TreeNode;  
            MyTree->rightPtr->leftPtr=MyTree->rightPtr->rightPtr=NULL; 
            MyTree->rightPtr->key=x; 
            MyTree->rightPtr->polinom=p; 
            count++;
        }
    }
    }
    }

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
//KodTreeNode.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include "TreeNode.h"
 
 
int main()
{  SetConsoleCP(1251);
SetConsoleOutputCP(1251);
 
TreeNode *Tree=NULL;  
TreeNode Derevo;
std::ifstream imput_fail_key;
std::ifstream imput_fail_stroki;
imput_fail_key.open("key.txt", std::ios::in);
imput_fail_stroki.open("stroki.txt", std::ios::in);
if (!imput_fail_key.is_open()||!imput_fail_stroki.is_open()) // если файл не открыт
    std::cout << "Файл не может быть открыт!\n"; // сообщить об этом
std::cout << "Вывод содержимого файла key.txt и файла stroki.txt. \n";
while(!imput_fail_key.eof()&&!imput_fail_stroki.eof())
{   int k;
std::string line;
imput_fail_key>> k; // считали число из файла
getline(imput_fail_stroki, line);// считали строку из файла
std::cout << k << " " <<line<< std::endl;// напечатали это число и слово
Derevo.add_node(k, line.substr(0, 20), Tree);//возвращает 20 символов строки line начиная с позиции 0
 
}
std::cout << std::endl;
std::cout << "Исходное дерево:\n";
imput_fail_key.close();
imput_fail_stroki.close();
Derevo.show(Tree); 
 
std::cin.get();
return 0;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.05.2015, 12:46
Ответы с готовыми решениями:

Определить количество узлов на каждом уровне данного бинарного дерева
Помогите с этой задачей) Определить количество узлов на каждом уровне данного бинарного дерева....

В дереве бинарного поиска найти для него количество четных значений узлов дерева
В файле input.txt хранится последовательность целых чисел. По входной последовательности построить...

В рабочей программе добавить для дерева бинарного поиска нахождение отрицательных значений узлов дерева
Полностью готовая программа, но что дописать в мейне чтобы он выводил произведение отрицательных...

Подсчет узлов бинарного дерева
вот код программы: (defun node_counter(tree) (cond ((null tree) 0) ...

9
4 / 4 / 1
Регистрация: 12.02.2015
Сообщений: 46
12.05.2015, 12:53 2
Цитата Сообщение от lenarano Посмотреть сообщение
{ *
* * {if (Tree!=NULL)
* * {
Опаньки, а что это за { перед if? Она ничего не открывает...
0
2 / 2 / 2
Регистрация: 12.04.2014
Сообщений: 102
12.05.2015, 12:59  [ТС] 3
да. Исправила. Все равно ошибка.
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
void TreeNode::add_node(int x,std::string p,TreeNode *&MyTree) //Фукция добавления звена в дерево
    { 
        int count=0;
        if(count<=10)
            {if (NULL==MyTree)  
            {
                MyTree=new TreeNode; 
                MyTree->key=x;
                MyTree->polinom=p;
                MyTree->leftPtr=MyTree->rightPtr=NULL;
                count++;
            }
 
            if (x<MyTree->key)   
            {
                if (MyTree->leftPtr!=NULL) add_node(x,p,MyTree->leftPtr); 
                else 
                {
                    MyTree->leftPtr=new TreeNode;  
                    MyTree->leftPtr->leftPtr=MyTree->leftPtr->rightPtr=NULL; 
                    MyTree->leftPtr->key=x;
                    MyTree->leftPtr->polinom=p;
                    count++;
                }
            }
 
            if (x>MyTree->key)   
            {
                if (MyTree->rightPtr!=NULL) add_node(x,p,MyTree->rightPtr); 
                else 
                {
                    MyTree->rightPtr=new TreeNode;  
                    MyTree->rightPtr->leftPtr=MyTree->rightPtr->rightPtr=NULL; 
                    MyTree->rightPtr->key=x; 
                    MyTree->rightPtr->polinom=p; 
                    count++;
                }
            }
        }
    }
0
4 / 4 / 1
Регистрация: 12.02.2015
Сообщений: 46
12.05.2015, 13:05 4
Цитата Сообщение от lenarano Посмотреть сообщение
(NULL==MyTree)
Гениально) Сравниваешь NULL с переменной, надо наоборот.

Добавлено через 1 минуту
А можно поинтересуюсь? Каким компилятором и средой пользуешься? Они должны сообщать о таких ошибках.
0
2 / 2 / 2
Регистрация: 12.04.2014
Сообщений: 102
12.05.2015, 14:40  [ТС] 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
void TreeNode::add_node(int x,std::string p,TreeNode *&MyTree) //Фукция добавления звена в дерево
    {  
        int count=0;
        while(count<=10)
            {if (NULL==MyTree)  
            {
                MyTree=new TreeNode; 
                MyTree->key=x;
                MyTree->polinom=p;
                MyTree->leftPtr=MyTree->rightPtr=NULL;
                count++;
            }
 
            if (x<MyTree->key)   
            {
                if (MyTree->leftPtr!=NULL) add_node(x,p,MyTree->leftPtr); 
                else 
                {
                    MyTree->leftPtr=new TreeNode;  
                    MyTree->leftPtr->leftPtr=MyTree->leftPtr->rightPtr=NULL; 
                    MyTree->leftPtr->key=x;
                    MyTree->leftPtr->polinom=p;
                    count++;
                }
            }
 
            if (x>MyTree->key)   
            {
                if (MyTree->rightPtr!=NULL) add_node(x,p,MyTree->rightPtr); 
                else 
                {
                    MyTree->rightPtr=new TreeNode;  
                    MyTree->rightPtr->leftPtr=MyTree->rightPtr->rightPtr=NULL; 
                    MyTree->rightPtr->key=x; 
                    MyTree->rightPtr->polinom=p; 
                    count++;
                }
            }
        }
    }
Добавлено через 14 минут
получается,что счетчик срабатывает только один раз и становится равен 1 и потом, по каким-то причинам данные из файла перестают заполнятся в бинарное дерево. Может нужно что-то еще добавить в main?

Добавлено через 52 минуты
Если вместо while ставлю if, то выводится все из файла, т.е ограничение не срабатывает и счетчик все время сохраняет значение 1.
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
void TreeNode::add_node(int x,std::string p,TreeNode *&MyTree) //Функция добавления звена в дерево
{  
    int count=0;
    if(count<=10)
    {if (NULL==MyTree)  
    {
        MyTree=new TreeNode; 
        MyTree->key=x;
        MyTree->polinom=p;
        MyTree->leftPtr=MyTree->rightPtr=NULL;
        count++;
        std::cout <<count;
    }
 
    if (x<MyTree->key)   
    {
        if (MyTree->leftPtr!=NULL) add_node(x,p,MyTree->leftPtr); 
        else 
        {
            MyTree->leftPtr=new TreeNode;  
            MyTree->leftPtr->leftPtr=MyTree->leftPtr->rightPtr=NULL; 
            MyTree->leftPtr->key=x;
            MyTree->leftPtr->polinom=p;
            count++;
            std::cout <<count;
        }
    }
 
    if (x>MyTree->key)   
    {
        if (MyTree->rightPtr!=NULL) add_node(x,p,MyTree->rightPtr); 
        else 
        {
            MyTree->rightPtr=new TreeNode;  
            MyTree->rightPtr->leftPtr=MyTree->rightPtr->rightPtr=NULL; 
            MyTree->rightPtr->key=x; 
            MyTree->rightPtr->polinom=p; 
            count++;
            std::cout <<count;
        }
    }
    }
}
0
Kastaneda
12.05.2015, 14:49
  #6

Не по теме:

Цитата Сообщение от oppppp Посмотреть сообщение
Гениально) Сравниваешь NULL с переменной, надо наоборот.
А можно поинтересуюсь? Каким компилятором и средой пользуешься? Они должны сообщать о таких ошибках.
Это корректный код, более того есть даже рекомендация писать именно так, а не (Tree == NULL) во избежания случайного написания "=" вместо "==".

0
Tulosba
12.05.2015, 15:07
  #7

Не по теме:

Цитата Сообщение от Kastaneda Посмотреть сообщение
Это корректный код
Yoda conditions
А вообще, удивляться не приходится. Человек же и-дэ-е собрался писать :)

0
2 / 2 / 2
Регистрация: 12.04.2014
Сообщений: 102
12.05.2015, 15:17  [ТС] 8
Tulosba, Kastaneda, ребята, посмотрите код. Что-то не нахожу ошибку-знаний маловато.
0
Jesus loves me
Эксперт С++
5107 / 3120 / 352
Регистрация: 12.12.2009
Сообщений: 7,891
Записей в блоге: 2
12.05.2015, 20:52 9
Лучший ответ Сообщение было отмечено lenarano как решение

Решение

lenarano, мне проще было с нуля код написать, чем править твой. Вот держи (деструктор не забудь дописать)

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
#include <iostream>
class BST // binary search tree
{
public:
    BST(int limit) : head(NULL), limit_(limit)
    {
    }
 
    ~BST()
    {
        // освобождаем память, влом писать
    };
 
    void add(int key, const std::string &p)
    {
        add(key, p, head);
    }
 
    void print()
    {
        print(head, "");
    }
 
private:
    class node;
    void print(node *n, std::string spaces) // помнится нас в универе заставляли печатать дерево боком, сделал также
    {
        if (!n) {
            return;
        }
        print(n->right_, spaces + " ");
        std::cout << spaces << " (" << n->key_ << ")" << n->polinom_ << std::endl;
        print(n->left_, spaces + " ");
    }
 
    void add(int key, const std::string &p, node *&n)
    {
        if (n == NULL) {
            if (!limit_) {
                std::cout << "ERROR: Can't add new node, limit is reached" << std::endl;
                return;
            }
            n = new node(key, p);
            --limit_;
            return;
        }
 
        if (n->key_ == key) { // перезаписываем, надо?
            n->key_ = key;
            n->polinom_ = p;
            return;
        }
 
        if (key > head->key_) {
            add(key, p, n->right_);
        } else {
            add(key, p, n->left_);
        }
    }
 
    class node
    {
    friend class BST;
    public:
        node (int key, const std::string polinom) : key_(key), polinom_(polinom), left_(NULL), right_(NULL)
        {
        }
    private:
        int key_;
        std::string polinom_;
        node *left_;
        node *right_;
    } *head;
 
    int limit_;
};
 
int main()
{
    BST bst(10); // 10 это максимальное кол-во узлов в дереве, можно задать любое число
 
    bst.add(1, "ONE"); 
    bst.add(2, "TWO");
    bst.add(3, "THREE");
    bst.add(4, "FOUR"); 
    bst.add(5, "FIVE"); 
    bst.add(0, "SIX"); 
    bst.add(-1, "SEVEN");
    bst.add(-2, "EIGHT"); 
    bst.add(-3, "NINE"); 
    bst.add(-4, "TEN"); 
    bst.add(100, "SHOULD NOT REACH"); 
 
    bst.print();
}

Не по теме:

Цитата Сообщение от Tulosba Посмотреть сообщение
Человек же и-дэ-е собрался писат
а ну тогда я спокоен :)

1
2 / 2 / 2
Регистрация: 12.04.2014
Сообщений: 102
13.05.2015, 02:09  [ТС] 10
Kastaneda, спасибо. Я посмотрю. Кстати, нашла ошибку. Нужно было объявить статическую переменную для счетчика.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.05.2015, 02:09

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Монотонная последовательность узлов бинарного дерева поиска
Добрый день. есть бинарное дерево поиска и какое-то заданное число S. Нужно найти все монотонные...

Удаление узлов из бинарного дерева до даты, введенной с клавиатуры
В общем, такой вопрос. Используя классы, создать упорядоченное бинарное дерево, которое описывает...

Найти среднее арифметическое узлов бинарного дерева целых чисел
Помогите решить. Надо срочно!!! Создать бинарное дерево целых чисел. Вывести на экран значение...

Найти сумму значений узлов бинарного дерева, находящихся на нечетных уровнях
Помогите, пожалуйста с задачкой. :sorry: Найти сумму значений узлов бинарного дерева, находящихся...


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

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

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