VPF::Функция поиска в дереве - Форум программистов

Voldemar2004

Дата 10.6.2007, 18:39 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1650
Регистрация: 25.12.2004

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

Что-то странное происходит: в методе Search - поиске элемента в дереве. smile

Сразу скажу IDE Borland C++ Builder 6.0:

работает правильно:

Код

#include <iostream.h>
#include <string.h>

class Tree{

public:

        class Node {

        public:

        string Text;            // Предложение.
        int Counter;            // Количество цифр в предложении.
        int Symbols_Counter;    // Количество символов в предложении.

        Node* Left;
        Node* Right;
        };

        Node* First(string Text);
        Node* Search_Insert(Node* root, string Text);
        void Print_Back(Node* root, int Level);

        // Поиск элемента в дереве:
        int Search(Node* root, int Key);

        private:

        // Метод возвращает количество цифр в предложении:
        int Counter(string Text);

        // Метод возвращает количество всех символов в предложении:
        int Symbols_Counter(string Text);


};

//---------------------------------------------------------------------------
int main()
{

Tree My;

Tree::Node* root = My.First("abcd 123");

// Добавляем элементы:

My.Search_Insert(root, "abcdefg 12");

My.Search_Insert(root, "abcdefg 1");

My.Search_Insert(root, "abcdefgefgh ");

int Search = 1;
My.Search(root, Search);

cin.get();

return 0;
}
//---------------------------------------------------------------------------

// Формирование первого элемента дерева:
Tree::Node* Tree::First(string Text) {

Node* pv = new Node;

// Добавление информационной части узла в первый элемент дерева:

pv->Symbols_Counter = Symbols_Counter(Text.c_str());

pv->Text = Text.c_str();

pv->Counter = Counter(Text.c_str());

pv->Left = 0;
pv->Right = 0;

return pv;

}

//---------------------------------------------------------------------------
// Поиск элемента с включением его в дерево:
Tree::Node* Tree::Search_Insert(Node* root, string Text) {

Node* pv = root, *prev;

bool found = false;

        while(pv && !found){

        prev = pv;

               if (Symbols_Counter(Text) == pv->Symbols_Counter) found = true;
               else if (Symbols_Counter(Text) < pv->Symbols_Counter) pv = pv->Left;
               else pv = pv->Right;
        }

        if(found) return pv;

        // Создание нового узла:

        Node* pnew = new Node;

        // Добавление информационной части узла в новый элемент дерева:
        pnew->Symbols_Counter = Symbols_Counter(Text.c_str());
        pnew->Text = Text.c_str();
        pnew->Counter = Counter(Text.c_str());

        pnew->Left = 0;
        pnew->Right = 0;

                if(Symbols_Counter(Text) < prev->Symbols_Counter)
                // Присоединение к левому поддереву предка:
                        prev->Left = pnew;
                else
                        prev->Right = pnew;
                // Присоединение к правому поддереву предка:
                return pnew;
}
//---------------------------------------------------------------------------

// Метод возвращает количество цифр в предложении:

int Tree::Counter(string Text) {

int Counter = 0;

        for(int i=0; i<strlen( (char*)Text.c_str() ); ++i)
        isdigit(Text[i]) ? ++Counter : Counter;

return Counter;

}

//---------------------------------------------------------------------------
// Метод возвращает количество всех символов в предложении:

int Tree::Symbols_Counter(string Text) {

return strlen( (char*)Text.c_str() );

}

//---------------------------------------------------------------------------

// Поиск элемента в дереве:
int Tree::Search(Node* root, int Key) {

        if(root == NULL) return NULL;

        if(Key == root->Counter) {
        cout << root->Symbols_Counter;
        //return root->Symbols_Counter;
        }

Search(root->Left, Key);
Search(root->Right, Key);

}
//---------------------------------------------------------------------------

Выводит 9 через cout .

Немного преобразуем:

Код

// Поиск элемента в дереве:
int Tree::Search(Node* root, int Key) {

        if(root == NULL) return NULL;

        if(Key == root->Counter) {
        //cout << root->Symbols_Counter;
        return root->Symbols_Counter;
        }

Search(root->Left, Key);
Search(root->Right, Key);

и в функции main():

Код

int main()
{

Tree My;

Tree::Node* root = My.First("abcd 123");

My.Search_Insert(root, "abcdefg 12");

My.Search_Insert(root, "abcdefg 1");

My.Search_Insert(root, "abcdefgefgh ");

int Search = 1;
cout << My.Search(root, Search);

cin.get();

return 0;
}

Выводит 0 ! Что это такое ? smile

Код

#include <iostream.h>
#include <string.h>

class Tree{

public:

        class Node {

        public:

        string Text;            // Предложение.
        int Counter;            // Количество цифр в предложении.
        int Symbols_Counter;    // Количество символов в предложении.

        Node* Left;
        Node* Right;
        };

        Node* First(string Text);
        Node* Search_Insert(Node* root, string Text);
        void Print_Back(Node* root, int Level);

        // Поиск элемента в дереве:
        int Search(Node* root, int Key);

        private:

        // Метод возвращает количество цифр в предложении:
        int Counter(string Text);

        // Метод возвращает количество всех символов в предложении:
        int Symbols_Counter(string Text);


};

//---------------------------------------------------------------------------
int main()
{

Tree My;

Tree::Node* root = My.First("abcd 123");

// Добавляем элементы:

My.Search_Insert(root, "abcdefg 12");

My.Search_Insert(root, "abcdefg 1");

My.Search_Insert(root, "abcdefgefgh ");

int Search = 1;
cout << My.Search(root, Search);

cin.get();

return 0;
}
//---------------------------------------------------------------------------

// Формирование первого элемента дерева:
Tree::Node* Tree::First(string Text) {

Node* pv = new Node;

// Добавление информационной части узла в первый элемент дерева:

pv->Symbols_Counter = Symbols_Counter(Text.c_str());

pv->Text = Text.c_str();

pv->Counter = Counter(Text.c_str());

pv->Left = 0;
pv->Right = 0;

return pv;

}

//---------------------------------------------------------------------------
// Поиск элемента с включением его в дерево:
Tree::Node* Tree::Search_Insert(Node* root, string Text) {

Node* pv = root, *prev;

bool found = false;

        while(pv && !found){

        prev = pv;

               if (Symbols_Counter(Text) == pv->Symbols_Counter) found = true;
               else if (Symbols_Counter(Text) < pv->Symbols_Counter) pv = pv->Left;
               else pv = pv->Right;
        }

        if(found) return pv;

        // Создание нового узла:

        Node* pnew = new Node;

        // Добавление информационной части узла в новый элемент дерева:
        pnew->Symbols_Counter = Symbols_Counter(Text.c_str());
        pnew->Text = Text.c_str();
        pnew->Counter = Counter(Text.c_str());

        pnew->Left = 0;
        pnew->Right = 0;

                if(Symbols_Counter(Text) < prev->Symbols_Counter)
                // Присоединение к левому поддереву предка:
                        prev->Left = pnew;
                else
                        prev->Right = pnew;
                // Присоединение к правому поддереву предка:
                return pnew;
}
//---------------------------------------------------------------------------

// Метод возвращает количество цифр в предложении:

int Tree::Counter(string Text) {

int Counter = 0;

        for(int i=0; i<strlen( (char*)Text.c_str() ); ++i)
        isdigit(Text[i]) ? ++Counter : Counter;

return Counter;

}

//---------------------------------------------------------------------------
// Метод возвращает количество всех символов в предложении:

int Tree::Symbols_Counter(string Text) {

return strlen( (char*)Text.c_str() );

}

//---------------------------------------------------------------------------

// Поиск элемента в дереве:
int Tree::Search(Node* root, int Key) {

        if(root == NULL) return NULL;

        if(Key == root->Counter) {
        //cout << root->Symbols_Counter;
        return root->Symbols_Counter;
        }

Search(root->Left, Key);
Search(root->Right, Key);

}
//---------------------------------------------------------------------------

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

i_i
(';')
(V)

user posted image

Kuvaldis

Дата 11.6.2007, 09:39 (ссылка)

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

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

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

Voldemar2004,

Код


// Поиск элемента в дереве:
int Tree::Search(Node* root, int Key) {

        int  res;

        if(root == NULL) return NULL;
        if(Key == root->Counter) {
        //cout << root->Symbols_Counter;
        return root->Symbols_Counter;
        }
        else if ( res = Search(root->Left, Key) )
            return res;
        else
        {
            res = Search(root->Right, Key);
            return res;
        }
}

Обоснование:
когда ты искал ключ, то не возвращал результат рекурсивного поиска. Т.е. был return только от узла, в котором ты нашел.

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

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

Voldemar2004

Дата 11.6.2007, 11:50 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1650
Регистрация: 25.12.2004

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

Kuvaldis, работает ! smile

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

i_i
(';')
(V)

user posted image

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