Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
draka08
1 / 1 / 2
Регистрация: 24.02.2016
Сообщений: 126
#1

Дополнить дерево бинарного поиска

02.12.2016, 16:14. Просмотров 829. Ответов 4
Метки нет (Все метки)

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

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
#include <iostream>
#include <iomanip>
#include "tree.h"
using namespace std;
int main()
{
    Tree<int> intTree;
    int intVal;
    cout << "Input 10 integer number: " << endl;
    
    for (int i = 0; i<10; i++)
    {
        cin >> intVal;
        intTree.insertNode(intVal);
    }
 
    cout << endl << "Prefix ordered Traversal" << endl;
    intTree.preOrderTraversal();
    cout << endl << "Infix ordered Traversal" << endl;
    intTree.inOrderTraversal();
    cout << endl << "Postfix ordered Traversal" << endl;
    intTree.postOrderTraversal();
    
    Tree<float> floatTree;
    float floatVal;
 
    cout << endl << endl << endl
        << "Input 10 float number: "
        << endl << setiosflags(ios::fixed | ios::showpoint)
        << setprecision(1);
 
    for (int i = 0; i<10; i++)
    {
        cin >> floatVal;
        floatTree.insertNode(floatVal);
    }
    cout << endl << "Prefix ordered Traversal" << endl;
    floatTree.preOrderTraversal();
    cout << endl << "Infix ordered Traversal" << endl;
    floatTree.inOrderTraversal();
    cout << endl << "Postfix ordered Traversal" << endl;
    floatTree.postOrderTraversal();
    cout << endl;
    return 0;
    system("pause");
}
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
#pragma once
#ifndef TREENODE_H
#define TREENODE_H
 
template<class NODETYPE>
class Tree;
 
template<class NODETYPE>
class TreeNode
{
    
    friend class Tree<NODETYPE>;
public:
    TreeNode(const NODETYPE&);
    NODETYPE getData() const; 
private:
    TreeNode *leftPtr; 
    NODETYPE data; 
    TreeNode *rightPtr; 
};
template<class NODETYPE>
TreeNode<NODETYPE>::TreeNode(const NODETYPE& d)
{
    data = d;
    leftPtr = rightPtr = NULL;
}
 
template<class NODETYPE>
NODETYPE TreeNode<NODETYPE>::getData() const
{
    return data;
}
#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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#pragma once
#ifndef TREE_H
#define TREE_H
#include <iostream>
#include <assert.h>
#include "treenode.h"
template<class NODETYPE>
class Tree
{
public:
    Tree(); 
 
    void insertNode(const NODETYPE&);
 
    void preOrderTraversal() const;
    void inOrderTraversal() const;
    void postOrderTraversal() const;
private:
 
    TreeNode<NODETYPE> *rootPtr;
 
    void insertNodeHelper(TreeNode<NODETYPE> **, const NODETYPE&);
    void preOrderHelper(TreeNode<NODETYPE> *) const;
    void inOrderHelper(TreeNode<NODETYPE> *) const;
    void postOrderHelper(TreeNode<NODETYPE> *) const;
};
 
template<class NODETYPE>
Tree<NODETYPE>::Tree() { rootPtr = NULL; }
template<class NODETYPE>
void Tree<NODETYPE>::insertNode(const NODETYPE& value)
{
    insertNodeHelper(&rootPtr, value);
}
template<class NODETYPE>
void Tree<NODETYPE>::insertNodeHelper(TreeNode<NODETYPE> ** ptr,
    const NODETYPE& value)
{
    if (*ptr == NULL)
    {
        *ptr = new TreeNode<NODETYPE>(value);
        assert(*ptr != NULL);
    }
    else
        if (value<(*ptr)->data)
            insertNodeHelper(&((*ptr)->leftPtr), value);
        else
            if (value>(*ptr)->data)
                insertNodeHelper(&((*ptr)->rightPtr), value);
            else
                cout << value << "Dub" << endl;
}
template<class NODETYPE>
void Tree<NODETYPE>::preOrderTraversal() const
{
    preOrderHelper(rootPtr);
}
template<class NODETYPE>
void Tree<NODETYPE>::preOrderHelper(TreeNode<NODETYPE> *ptr) const
{
    if (ptr != NULL)
    {
        cout << ptr->data << ' ';
        preOrderHelper(ptr->leftPtr);
        preOrderHelper(ptr->rightPtr);
    }
}
template<class NODETYPE>
void Tree<NODETYPE>::inOrderTraversal() const
{
    inOrderHelper(rootPtr);
}
template<class NODETYPE>
void Tree<NODETYPE>::inOrderHelper(TreeNode<NODETYPE> *ptr) const
{
    if (ptr != NULL)
    {
        inOrderHelper(ptr->leftPtr);
        cout << ptr->data << ' ';
        inOrderHelper(ptr->rightPtr);
    }
}
template<class NODETYPE>
void Tree<NODETYPE>::postOrderTraversal() const
{
    postOrderHelper(rootPtr);
}
template<class NODETYPE>
void Tree<NODETYPE>::postOrderHelper(TreeNode<NODETYPE> *ptr) const
{
    if (ptr != NULL)
    {
        postOrderHelper(ptr->leftPtr);
        postOrderHelper(ptr->rightPtr);
        cout << ptr->data << ' ';
    }
}
#endif
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.12.2016, 16:14
Ответы с готовыми решениями:

Дерево бинарного поиска
Всем привет! Есть рабочий код бинарного поиска template &lt;class Item, class...

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

Удаление элементов из бинарного дерева (не дерево поиска)
Задание заключается в создании бинарного дерева, из букв введенной строки,...

Создание бинарного дерево из бинарного файла
struct Bin { string name; string city; int players; int...

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

4
draka08
1 / 1 / 2
Регистрация: 24.02.2016
Сообщений: 126
11.12.2016, 19:47  [ТС] #2
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
template<class NODETYPE>
class Tree
{
public:
    Tree(); //Конструктор
            //Помещение значения в узел дерева
    void insertNode(const NODETYPE&);
    //Обход дерева заданным способом и печать значений в узлах
    void preOrderTraversal() const;
    void inOrderTraversal() const;
    void postOrderTraversal() const;
    int countALL() const { return countAll(rootPtr); }
    int countLeaf() const { return countLeaf(rootPtr); }
private:
    //Объявление указателя на корневой узел дерева
    TreeNode<NODETYPE> *rootPtr;
    static int countAll(const TreeNode<NODETYPE> *head)
    {
        return head == 0 ? 1 : countAll(head->leftPtr()) + countAll(head->rightPtr()) + 1; // вот здесь ошибка
    }
    static int countLeaf(const TreeNode<NODETYPE> *head)
    {
        if (!head) return 0;
        return !head->leftPtr() && !head->rightPtr() ? 1 : countLeaf(head->leftPtr()) + countLeaf(head->rightPtr());
    }
 
 
    //Помещение узла в дерево в качестве концевого узла
    void insertNodeHelper(TreeNode<NODETYPE> **, const NODETYPE&);
    void preOrderHelper(TreeNode<NODETYPE> *) const;
    void inOrderHelper(TreeNode<NODETYPE> *) const;
    void postOrderHelper(TreeNode<NODETYPE> *) const;
};
Ошибка C2064 результатом вычисления фрагмента не является функция, принимающая 0 аргументов lab5 d:\документи\visual studio 2015\projects\lab5\lab5\tree.h 27


Вот я так сделал но ошибка в чем дело помогите пожалуйста
0
nmcf
6267 / 5575 / 2535
Регистрация: 14.04.2014
Сообщений: 23,468
11.12.2016, 20:07 #3
rightPtr и leftPtr - не функции. Зачем скобки ставишь?
0
draka08
1 / 1 / 2
Регистрация: 24.02.2016
Сообщений: 126
12.12.2016, 22:24  [ТС] #4
C++
1
2
3
4
5
6
7
8
9
10
private:
    static int countAll(const TreeNode<NODETYPE> *head)
    {
        return head == 0 ? 1 : countAll(head->leftPtr) + countAll(head->rightPtr) + 1;
    }
    static int countLeaf(const TreeNode<NODETYPE> *head)
    {
        if (!head) return 0;
        return !head->leftPtr && !head->rightPtr ? 1 : countLeaf(head->leftPtr) + countLeaf(head->rightPtr);
    }
Вот исправил но функции неправильно рассчитывают количество узлов и листев в соответствии
0
nmcf
6267 / 5575 / 2535
Регистрация: 14.04.2014
Сообщений: 23,468
13.12.2016, 10:38 #5
Лучший ответ Сообщение было отмечено draka08 как решение

Решение

Вторая вроде бы правильная.
C++
1
2
3
4
5
6
7
8
9
10
    static int countAll(const TreeNode<NODETYPE> *head)
    {
        return head == NULL ? 0 : 1 + countAll(head->leftPtr) + countAll(head->rightPtr);
    }
 
    static int countLeaf(const TreeNode<NODETYPE> *head)
    {
        if (head == NULL) return 0;
        return head->leftPtr == NULL && head->rightPtr == NULL ? 1 : countLeaf(head->leftPtr) + countLeaf(head->rightPtr);
    }
1
13.12.2016, 10:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.12.2016, 10:38

Дополнить класс, включив метод подсчета числа узлов заданного бинарного дерева
Изучить приведенный пример реализации класса «Дерево двоичного поиска», для...

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

Бинарное дерево из НЕ бинарного
тащемта всё ясно из названия темы есть небинарное дерево -&gt; надо сделать из...


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

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

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