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

бинарными деревьями как динамическая структура данных - C++

Восстановить пароль Регистрация
 
3a4em
11 / 11 / 1
Регистрация: 05.12.2010
Сообщений: 26
10.12.2010, 19:32     бинарными деревьями как динамическая структура данных #1
Суть задачи в следующем.
Необходимо реализовать бинарное дерево как динамическую структуру данных.
Помимо стандартных функций созджания 1 элемента и распечатки дерева необходимо написать функцию добавления новогно элемента в дерево. В узле дерева находится строка.
Ещё про функцию добавления. Узел дерева должен содержать либо данные либо * , как указатель на то что у дерева сущетвуют ещё 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
75
76
77
78
79
80
81
#include <iostream>
#include <string>  // для строк
using namespace std;
struct Node  // стрктура дерево
{
    string d;  // узел
    Node *left ;  // ссссылка на левое 
    Node *right ;  // и правое поддеревья
};
Node * first (string d);  // функция формирования корня 
void insert(Node *root, string d); // функция добавления нового элемента
void print_tree (Node *root, int l);  // вывод на экран
void sear (Node *root, string d);   // функция поиска места для вставки
 
 
void main()  // главная функция
{
    string b[] = {"anton","ryc9","petr","olog","anton","tania","gala","badik"};  // массив данных
    Node *root = first(b[0]);  // формирования е 1 жлемента
    for (int i=1; i<8 ; i++) // цикл добавления элементов
        {
            sear(root , b[i]); // функуция поиска места для вставки (внутри вызов функции вставки) 
        }
    print_tree (root, 0); // распечатка дерева
}
 
Node * first (string d) // формирование 1 жлемента дерева
{
    Node *pv = new Node; // создание узла pv типа структура
    pv->d = d;  // данные в узле
    pv->left = 0;  // ссылка на левое
    pv->right = 0; // и правое поддеревья
    return pv;  // возвращаем корень
}
void print_tree (Node *p , int level)  // распечатка дерева  рекурсивная функция обхода дерева с лева на право
{
    if (p)  // пока p
    {
        print_tree (p->left, level +1);  // вызов вывода для левого поддерева
            for (int i=0; i<level; i++ ) 
                    cout << "   "; // уровень
        cout << p->d << endl;  // вывод данных из узла
        print_tree (p->right, level + 1); // ввод правого пооддерева
    }
}
void insert(Node *root, string d)  // функция вставки
{    
    Node *pv = root;  // pv корень
    Node *pnewr = new Node;  // новая структура новое лево
    Node *pnewl = new Node;  // новое право
    string buf = pv->d;  // данные из узла в буфер
    pv->d = "*";  // данные в узле заменяем на знак указателя
    pv->left = pnewl;  // для левог новая структура
    pv->right = pnewr;  // для правого новая структура
    pnewr->d = buf;  // в правое поддерево в узел дынные из буфера
    pnewr->left = 0;  // лево 0
    pnewr->right = 0; // право 0
    pnewl->d = d;  // в правое поддерево в узел новые данные
    pnewl->left = 0;  // лево 0
    pnewl->right = 0;  // право 0
}
void sear (Node *p, string d)  // поиск
{   
    if (p)  //пока p
    {
        sear (p->left, d );  //рекурсия на лево 
        int t = p->d.compare(d);
            if (t == 0) 
            {
                return;
            }
        int pr = 0, se = 0, se1 = 0; // переменные
        int co1 = p->d.find('*'); // смотрим чтобы * не попадалось
        if (  co1 != 0 && t == -1)
            {
                insert(p , d); // вызов вставки
                return;
            }
        sear (p->right, d ); // рекурсия в право
    }
}
Протокол работы программы прилагется. Дак вот у меня проблема. Не понимаю почему некоторая строка вставляеться много раз, а не 1 ??? никак не могу разобраться....
заранее спасибо за подсказку
Миниатюры
бинарными деревьями как динамическая структура данных  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.12.2010, 19:32     бинарными деревьями как динамическая структура данных
Посмотрите здесь:

C++ Динамическая структура данных С++
Динамическая структура данных C++
C++ Динамическая структура данных
Динамическая структура данных в С++ C++
C++ Динамическая структура данных
C++ Динамическая структура данных Очередь
Динамическая структура данных (Стек) C++
C++ Динамическая структура данных в форме односвязного списка на основе указателей

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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