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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 32, средняя оценка - 4.75
Infinity3000
1057 / 576 / 24
Регистрация: 03.12.2009
Сообщений: 1,255
#1

АТД деревья. Вывод бинарного дерева в консоль - C++

14.10.2011, 13:59. Просмотров 3964. Ответов 2
Метки нет (Все метки)

Здравствуйте, нужна помощь!

Возможно тема заезженная, но извеняйте не чего путнего не получаеться!)

Помоги вывести дерево в консоль! Можно в лежащем на левом боку но желательно стоя.

Суть задачи такова: вычислить высоту дерева с использованием представлений левых сыновей и правых братьев.

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

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
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
#pragma once
 
template <class T>
 
class Tree
{
    struct Node 
    {
        T item;
        Node *son;
        Node *brother;
 
        Node(T i, Node *s = NULL, Node *b = NULL)
        {
            item = i;
            son = s;
            brother = b;
        }
    };
    Node *root;
 
public:
    Tree()
    {
        root = NULL;
    }
 
    ~Tree()
    {
        DeleteSubtree(root);
    }
 
    int GetHeight()
    {
        return GetHeight(root);
    }
 
    int GetNodesOnLevel(int level) 
    {
        return GetNodesOnLevel(root, level);
    }
 
    void Add(const T &elem)
    {
        Add(root, elem);
    }
 
private:
    void Add(Node *&node, const T &elem);
    void DeleteSubtree(Node *node);
    int GetHeight(Node *node);
    int GetNodesOnLevel(Node *node, int level);
};
 
 
template <class T>
 
void Tree<T>::DeleteSubtree(Node *node)
{
    if (node)
    {
        DeleteSubtree(node->son);
        DeleteSubtree(node->brother);
        delete node;
    }
}
 
template <class T>
 
int Tree<T>::GetHeight(Node *node)
{
    if (node == NULL)
    {
        return 0;
    }
    int max = 0;
    for (Node *current = node->son; current; current = current->brother)
    {
        int curHeight = GetHeight(current);
        if (curHeight > max)
        {
            max = curHeight;
        }
    }
    return max + 1;
}
 
template <class T>
 
int Tree<T>::GetNodesOnLevel(Node *node, int level)
{
    if (node == NULL)
    {
        return 0;
    }
    if (level <= 0)
    {
        return 0;
    }
 
    return GetNodesOnLevel(node->son, level - 1) + (level == 1) + 
        GetNodesOnLevel(node->brother, level);
}
 
template <class T>
void Tree<T>::Add(Node *&node, const T &item)
{
    if (node == NULL)
    {
        node = new Node(item);
    }
    else if (item < node->item)
    {
        Add(node->son, item);
    }
    else 
    {
        Add(node->brother, item);
    }
}

main.cpp
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
#include "iostream"
#include "tree.h"
 
using namespace std;
 
int main() 
{
    setlocale(0,"");
 
    Tree<int> tree;
    int n, lev, item;
    
    cout << "Введите количество элементов в дереве: ";
    cin >> n;
    cout << endl;
 
    cout << "Введите элементы дерева: ";
 
    for (int i = 0; i < n; i++)
    {
        cin >> item;
        tree.Add(item);
    }
    cout << endl;
 
 
    cout << "Высота дерева: " << tree.GetHeight()<< endl;
 
    cout << "Введите номер уравня на котором хотите узнать количество узлов: ";
    cin >> lev;
    cout << endl;
 
    cout << "Количество узлов на " << lev << " уравне: " << tree.GetNodesOnLevel(3) << endl;
 
    system("pause >>NULL");
    return 0;
}

Спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.10.2011, 13:59     АТД деревья. Вывод бинарного дерева в консоль
Посмотрите здесь:

Прошивка бинарного дерева на С++ C++
C++ Запись массива в виде бинарного дерева и вывод его на экран!
C++ Вывод бинарного дерева
Деревья (алгоритм создания СБАЛАНСИРОВАННОГО бинарного дерева) C++
C++ Обход бинарного дерева
C++ Бинарные деревья, вывод дерева на экран
C++ Вывод на консоль бинарного дерева
C++ Реализация бинарного дерева С++
Вывод в консоли красивого бинарного дерева C++
Удаление из бинарного дерева C++
Вывод бинарного дерева в консоль C++
C++ Реализация и вывод бинарного дерева

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Infinity3000
1057 / 576 / 24
Регистрация: 03.12.2009
Сообщений: 1,255
14.10.2011, 14:56  [ТС]     АТД деревья. Вывод бинарного дерева в консоль #2
можно сказать что разобрался сам!))


В принцепи правильно выводит!

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Out(node *root, unsigned k)
{
 
  if (root != NULL)
   {
    Out(root->left, k + 3);
 
    for(unsigned i = 0; i < k; i++)
    {
      cout<<"  ";
    }
     cout<< root->inf << endl;
     Out(root->right, k + 3);
    }
 
}

вызов

C++
1
Out(root, num);

Подскажите как сделать чтобы выводило еще и дуги деревьев??

Спасибо!!
Миниатюры
АТД деревья. Вывод бинарного дерева в консоль  
Infinity3000
1057 / 576 / 24
Регистрация: 03.12.2009
Сообщений: 1,255
14.10.2011, 19:56  [ТС]     АТД деревья. Вывод бинарного дерева в консоль #3
Проблема не решена!!! Подскажите хотя бы что узать и в каком напралении капать, что бы вывести к каждому узлу дерева дугу ??

Спасибо!!

Где то видел пример на паскале но не могу найти!
Yandex
Объявления
14.10.2011, 19:56     АТД деревья. Вывод бинарного дерева в консоль
Ответ Создать тему
Опции темы

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