VPF::[C++] Деревья/Структуры данных - Форум программистов

utwo

Дата 15.1.2010, 11:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 11.12.2009

Репутация: нет
Всего: нет

Всем привет,
нужно внести небольшие изменения в код (также убрать лишнее):

Элeмeнт дeрeвa coдeржит либo дaнныe (cтрoкa oгрaничeннoй
длины), либo укaзaтeли нa прaвoe и лeвoe пoддeрeвья. Стрoки в
дeрeвe получаются упoрядoчeны. Нaпиcaть функцию включeния нoвoй cтрoки.
Обрaтить внимaниe нa тo, чтo элeмeнт c укaзaтeлями нe coдeржит
дaнных, и при включeнии нoвoй вeршины вeршину c дaнными
cлeдуeт зaмeнить нa вeршину c укaзaтeлями.

На сколько я правильно понял, дерево мое теперь должны выглядеть таким образом?

Код


#include<iostream>
using namespace std;
 
struct node
{
             int x; //ключ
             char info;//информация
             node* LL; //left link
             node* RL; //right link
             node(){x=0;LL=0;RL=0;};
             ~node()
             {
                  if (LL) LL->~node();
                  if (RL) RL->~node();
                  if (LL) {delete LL; LL=0;}
                  if (RL) {delete RL; RL=0;}
             }
             void putx(int new_x,char new_info){this -> x=new_x;this -> info=new_info;}
             void null_leftlink(){this -> LL=0;}
             void null_rightlink(){this -> RL=0;}
             void add(int new_x, char new_info)
             {
                  if (LL&&(new_x < x)) LL->add(new_x,new_info);
                  if (RL&&(new_x > x)) RL->add(new_x,new_info);
                  
                  if (!LL&&(new_x < x))
                  {
                          node* N=new node;
                          N->x=new_x;
                          N->info=new_info;
                          N->LL=0;
                          N->RL=0;
                          LL=N;
                  }
                  if (!RL&&(new_x > x))
                  {
                          node* N=new node;
                          N->x=new_x;
                          N->info=new_info;
                          N->LL=0;
                          N->RL=0;
                          RL=N;
                  }
             }
             void print(int tab)
             {
                  if (RL) RL-> print(tab + 1);
                     for(int i=1;i!=tab;i++)cout << "  "; cout <<this->x << "-"<< this->info << endl;
                  if(LL) LL->print(tab + 1);      
             }
 
 
};
 
struct tree
{
             node* link;
             tree(){link=0;};
             void add(int new_x,char new_info)
             {
                  if (link) link->add(new_x,new_info);
                  else
                  {
                      node* N=new node();
                      N->putx(new_x,new_info);
                      N->null_leftlink();
                      N->null_rightlink();
                      link=N;
                  }
             };
             void print(){if(link)link->print(1);else cout << "No tree existing\n";}
};
 
int main()
{
 
    tree *T=new tree; // создание дерева
    //menu
    int choos=0;
    const int exit=3;
    while (choos!=exit)
    {
          cout << "  1-add;\n"
                  "  2-print;\n"
                  "  3-exit;\n"
                  "enter-> "; cin >> choos; system("cls");
          switch (choos){
                 case 1: {
                         int key; //ключ.
                         char val; //значение
                         cout << "enter key: "; cin >> key;
                         cout << "enter int value: "; cin >> val; 
                         T->add(key,val); 
                         break;
                 }
                 case 2: T->print(); break;
                  }
    }
    delete T; //удаление дерева, используется деструктор.
}

world

Дата 17.1.2010, 13:45 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 133
Регистрация: 2.10.2009
Где: Харьков

Репутация: 6
Всего: 12

Когда-то писал класс для работы с двоичными деревьями(компилятор MSVS 2008). Посмотри может найдёшь, что-то полезное

Код


#include "stdafx.h"
#include <iostream>
using namespace std;

template <typename T> class Tree
{
public:
    struct Node
    {
        T Key;
        Node* Parent;
        Node* Left;
        Node* Right;
    }* root;
private:
//Поиск перехода в левое или правое поддерево
    Node* SearchNext(Node* start, T Key)
    {
        Node* res = NULL;
        if(start != NULL){
            if(start->Key < Key)
            {
                res = start->Right;
            }
            if(start->Key >= Key)
            {
                res = start->Left;
            }
        }
        return res;
    }
//Вывод дерева на печать(обход корень-левый потомок-правый потомок
    void Vis(Node* nd)
    {
       cout << nd->Key << " ";
       if(nd->Left != NULL)
       {
           Vis(nd->Left);
       }
       if(nd->Right != NULL)
       {
           Vis(nd->Right);
       }
    }
public:
    Tree(T Key)
    {
        root = new Node();
        root->Key = Key;
        root->Parent = NULL;
        root->Left = NULL;
        root->Right = NULL;
    }
//Добавление элемента
    void Add(T Key)
    {
        Node* now = root;
        Node* tmp = SearchNext(now, Key);
        while(tmp != NULL)
        {
            now = tmp;
            tmp = SearchNext(now, Key);
        }
        tmp = new Node();
        tmp->Key = Key;
        tmp->Parent = now;
        if(now->Key < tmp->Key)
        {
            now->Right = tmp;
        }
        else
        {
            now->Left = tmp;
        }
    }
//Нахождение минимального элемента
    Node* Min()
    {
        Node* now = root;
        Node* tmp = now->Left;
        while(tmp != NULL)
        {
            now = tmp;
            tmp = now->Left;
        }
        return now;
    }
//Находение максимального элемента
    Node* Max()
    {
        Node* now = root;
        Node* tmp = now->Right;
        while(tmp != NULL)
        {
            now = tmp;
            tmp = now->Right;
        }
        return now;
    }
//Поиск элемента по значению(находит первый встречающийся элемент)
    Node* Search(T Key)
    {
        Node* now = root;
        Node* tmp = SearchNext(now, Key);
        while(tmp != NULL && now->Key != Key)
        {
            now = tmp;
            tmp = SearchNext(now, Key);
        }
        if(now->Key == Key)
        {
            return now;
        }
        return NULL;
    }
//Удаление элемента
    void Remove(T Key)
    {
        Node* now = root;
        Node* tmp = SearchNext(now, Key);
        while(tmp != NULL && now->Key != Key)
        {
            now = tmp;
            tmp = SearchNext(now, Key);
        }
        if(now->Key != Key)
        {
            printf("Key is not found!\n");
            return;
        }
        Node* parent = now->Parent;
        if(now->Left == NULL && now->Right == NULL)
        {
            if(parent != NULL && parent->Left == now)
            {
                parent->Left = NULL;
            }
            if(parent != NULL && parent->Right == now)
            {
                parent->Right = NULL;
            }
            delete now;
            printf("Key is deleted!\n");
            return;
        }
        if(now->Left == NULL)
        {
            if(parent != NULL && parent->Left == now)
            {
                parent->Left = now->Right;
            }
            if(parent != NULL && parent->Right == now)
            {
                parent->Right = now->Right;
            }
            Node* next = now->Right;
            next->Parent = parent;
            delete now;
            printf("Key is deleted!\n");
            return;
        }
        if(now->Right == NULL)
        {
            if(parent != NULL && parent->Left == now)
            {
                parent->Left = now->Left;
            }
            if(parent != NULL && parent->Right == now)
            {
                parent->Right = now->Left;
            }
            Node* next = now->Left;
            next->Parent = parent;
            delete now;
            printf("Key is deleted!\n");
            return;
        }
        tmp = now->Right;
        while(tmp->Left != NULL)
        {
            tmp = tmp->Left;
        }
        Node* t = tmp->Parent;
        if(t->Right != tmp)
        {
            t->Left = tmp->Right;
        }
        if(parent != NULL && parent->Left == now)
        {
            parent->Left = tmp;
        }
        if(parent != NULL && parent->Right == now)
        {
            parent->Right = tmp;
        }
        tmp->Left = now->Left;
        t = tmp->Left;
        t->Parent = tmp;
        if(now->Right == tmp)
        {
            tmp->Right = NULL;
        }
        else
        {
            tmp->Right = now->Right;
        }
        if(root == now)
        {
            root = tmp;
            tmp->Parent = NULL;
        }
        delete now;
        printf("Key is deleted!\n");
    }
//Поиск предка элемента (-1 если корень)
    Node* Earlier(int key)
    {
        Node* n = Search(key);
        if(n == NULL)
        {
            return (Tree<T>::Node*)-1;
        }
        else
        {
            return n->Parent;
        }
    }
//Визуализация дерева
    void Visual()
    {
        Vis(root);
    }
};

Это сообщение отредактировал(а) world - 17.1.2010, 13:52

--------------------

Say what you mean, and mean what you say. Robert Wilson Cody

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »