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

Класс для бинарного дерева - C++

Восстановить пароль Регистрация
 
vozup
5 / 5 / 0
Регистрация: 25.12.2011
Сообщений: 99
01.02.2014, 14:15     Класс для бинарного дерева #1
Добрый день, рзбераю бинарное дерево но что-то не особо понимаю. Может есть у кого-то простой пример с минимумом методов и желательно с коментами. Вот мой пример, но почему-то при вводе по возрастанию node->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
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
//Класс бинарного дерева
//
#include <iostream>
#include <conio.h>
#include <string>
 
using namespace std;
 
struct Node                                 //Звено дерева
{
    int data;                                   //То, что записываем в дерево
    string str;                                 //То, что записываем в дерево
    Node *left, *right, *parrent;                       //Это указатели на новые звенья
};
 
class Tree
{
private:
    Node *root;
public:
    Tree() { root = NULL; }
    void show_tree(Node *node);
    void add_node(Node *node);
    Node *getRoot();
};
 
Node* Tree::getRoot()
{
    return root;
}
 
void Tree::show_tree(Node *node)                    //Функция обхода
{
    if(node != NULL)                                //Пока не встретится пустое звено
    {
        show_tree(node->left);                      //Рекурсивная функция для вывода левого поддерева
        cout<<node->data<<" "<<node->str<<endl;     //Отображаем корень дерева
        show_tree(node->right);                     //Рекурсивная функци для вывода правого поддерева
    }
}
 
void Tree::add_node(Node *node)//Функция добавления звена в дерево
{
    // потомков нет
    node->left = NULL;
    node->right = NULL;
 
    Node * new_node = NULL;
    Node *node_root = root;
    // поиск места
    while(node_root != NULL)
    {
        // будущий родитель
        new_node = node_root;
        if(node->str.length() < node_root->str.length())
            node_root = node_root->left;
        else node_root = node_root->right;
    }
    // заполняем родителя
    node->parrent = new_node;
 
    if(new_node == 0)// элемент первый (единственный)
        root = node;
    // чей ключ больше?
    else if(node->data < new_node->data)
        new_node->left = node;
    else new_node->right = node;
}
 
void main(int argc, char* argv[])
{
    Tree tree;
    
    for(int i=0;i<5;i++)
    {
        Node *node = new Node;
        cout<<"Enter ID: ";
        cin>>node->data;
        cout<<"\nEnter string: ";
        cin>>node->str;
        cout<<endl;
 
        tree.add_node(node);
    }
 
    tree.show_tree(tree.getRoot());
    getch();
    return;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.02.2014, 14:15     Класс для бинарного дерева
Посмотрите здесь:

C++ Построение бинарного дерева на основе не бинарного
C++ Итератор для бинарного дерева поиска.
Итератор для бинарного дерева C++
Шаблонный класс бинарного дерева C++
C++ Вывод бинарного дерева на экран в виде "дерева"
Создать класс [B]TreeChar[/B], для работы с элементами двоичного дерева C++
Класс для бинарного дерева C++
Написать шаблон бинарного дерева с функцией распечатки дерева C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vovacreme
-16 / 61 / 13
Регистрация: 14.01.2014
Сообщений: 145
01.02.2014, 14:53     Класс для бинарного дерева #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
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
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
//--------------------------
struct  ElemT
{
   int Sod;
   ElemT* pLeft;
   ElemT* pRight;
}*pHead = NULL;
void AddUzel(ElemT* pCur,int value) {     // добавление конкретного узла дерева
    if(value < pCur->Sod)
        { if(pCur->pLeft != NULL)         // если значение меньше, двигаемся по "левой ветке"
              AddUzel(pCur->pLeft, value);
          else
          {  pCur->pLeft = new ElemT;
             pCur->pLeft->Sod = value;
             pCur->pLeft->pLeft=NULL;
             pCur->pLeft->pRight=NULL;
          }
        }
    if(value > pCur->Sod)                 // иначе двигаемся по правой 
        { if(pCur->pRight != NULL)
             AddUzel(pCur->pRight, value);
          else
           {
             pCur->pRight = new ElemT;
             pCur->pRight->Sod = value;
             pCur->pRight->pLeft=NULL;
             pCur->pRight->pRight=NULL;
           }
        }
    if(value == pCur->Sod)                
        { cout<<value<<" is already in tree"<<endl;
          return;
        }
}
void Add2Tree(int value)                  // проверка, не пустое ли дерево
{
    if(pHead == NULL)                     // если дерево пустое - создадим первый узел
     {
        pHead = new ElemT;
        pHead->Sod = value;
        pHead->pLeft=NULL;
        pHead->pRight=NULL;
        return;
     }
    AddUzel(pHead, value);                // если в макушке уже что-то есть - добавляем слева или справа 
}
//---------------------------
// в итоге получае упорядоченное дерево, то есть меньшие элементы расположены 
// "слева", а большие - "справа". Рекурсивно распечатываем это дерево от меньшего 
// элемента к большему
void PrintTree(ElemT* pCur)
{
    if (pCur!=NULL)
    {
        PrintTree(pCur->pLeft);
        cout<<pCur->Sod<<' ';
        PrintTree(pCur->pRight);
    }
}
//---------------------------
int main()
{
    Add2Tree(10);
    Add2Tree(20);
    Add2Tree(5);
    Add2Tree(100);
    Add2Tree(-11);
    PrintTree(pHead);
    return 0;
}
Yandex
Объявления
01.02.2014, 14:53     Класс для бинарного дерева
Ответ Создать тему
Опции темы

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