Поиск в двоичном дереве

@Вероника99 · Регистрация: 16.12.2013

Студворк — интернет-сервис помощи студентам

Добрый день. Нужно построить англо-русский словарь как двоичное дерево. Каждая компонента содержит английское слово, соответствующее ему русское слово и счетчик количества обращений к данной компоненте. Дальше нужно сформировать новое представление словаря в виде двоичного дерева по следующему алгоритму:
а) в старом словаре ищется компонента с наибольшим значением
счетчика обращений;
б) найденная компонента заносится в новый
словарь и удаляется из старого;
в) переход к п. а) до исчерпания исходного словаря;
Пока что есть добавление узлов в дерево, возникли проблемы с поиском максимального счетчика и вывода дерева.

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
#include <iostream>
#include <string>
using namespace std;
 
string temp_eng;
string temp_rus;
int temp_count;
int lev=0;
struct tree
{
    string eng; //слово
    string rus; //слово
    int count; //количество обращений
    tree *left;
    tree *right;
};
// Функция создания первого элемента
// Функция фoрмирования первого элемента дерева:
tree *first (string temp_eng,string temp_rus,int temp_count)
{
    tree *pv=new tree;
    pv->eng=temp_eng;
    pv->rus=temp_rus;
    pv->count=temp_count;
    pv->left=0;
    pv->right=0;
    return pv;
}
 
// Функция поиска и добавления элемента в дерево:
tree *search_insert (tree *root, string temp_eng, string temp_rus,int temp_count)
{
    tree *pv=root, *prev;
    bool found=false;
    //поиск по дереву
    while (pv&&!found) 
    {
    prev=pv;
    if ((temp_eng==pv->eng)&&(temp_rus==pv->rus))
        found = true;
    else if (temp_count < pv->count)
        pv=pv->left;
    else pv=pv->right;
    }
    if (found) return pv;
    //создание нового узла
    tree *pnew=new tree;
    pnew->eng=temp_eng;
    pnew->eng=temp_rus;
    pnew->count=temp_count;
    pnew->left=0;
    pnew->right=0;
    if (temp_count < prev->count)
    prev->left=pnew; //присоединение к левому поддереву предка
    else prev->right=pnew; //присоединение к правому поддереву предка
    return pnew;
}
//функция поиска наибольшего счетчика
void seek_count (tree *root) //ПРОБЛЕМА ЗДЕСЬ
{
    tree *p=root;
    int max_l=0;
    while(p!=NULL)
    {
        if(max_l<p->count)
        {
            max_l=p->count;
        }
        else
            p=p->left; //еще нужен обход по правому узлу
 
    }
    cout<<"\n"<<max_l<<endl;
}
// Функция показа дерева
void print_tree (tree *p, int level) //И здесь проблема
{
    if (p)
    {
        print_tree(p->left, level+1);
        for (int i=0; i<level; i++)
        cout<<" ";
        cout<<p->eng<<endl;
            cout<<p->rus<<endl;
        for (int i=0; i<level; i++)
        cout<<" ";
        cout<<p->count<<endl;
        print_tree (p->right, level+1);
    }
    lev=level;
}
int main()
{
    tree *root=NULL;
    for(int i=0;i<2;i++)
    {
    cout<<"Vvedite angliskoe slovo: "<<endl;
    cin>>temp_eng;
        cout<<"Vvedite russkoe slovo: "<<endl;
    cin>>temp_rus;
    cout<<"Vvedite znachenie schetchika: "<<endl;
    cin>>temp_count;
    if(!root)
    {
        root=first(temp_eng,temp_rus,temp_count);
    }
    else 
        root=search_insert (root, temp_eng, temp_rus,temp_count);
    }
    print_tree (root, 0);
    seek_count(root);
    return 0;
}

Подскажите пожалуйста,как правильно перебираться все узлы дерева,чтобы найти в нем максимальный счетчик?Я запуталась немного

@stzer · 22.06.2016, 18:31

Можно воспользоваться обходом в ширину.

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
size_t seek_count (tree *root)
{
    assert(root != nullptr);
    
    size_t max = root->count;
    std::queue<tree *> nodes;
    nodes.push(root);
    while (nodes.size() != 0)
    {
        auto temp = nodes.front();
        
        if (temp->count > max)
            max = temp->count;
        
        if (temp->left)
            nodes.push(temp->left);
        
        if (temp->right)
            nodes.push(temp->right);
        
        nodes.pop();
    }
    return max;
}

Вроде так =)

@Вероника99 · 22.06.2016, 19:53 **[ТС]**

Тут разобралась, сделала таким образом:

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
int max_l=0;
tree *seek_count (tree *p, int level)
{
    if(p)
    {
        if(max_l<p->count)
        {
            max_l=p->count;
            
        }
        seek_count(p->left,level+1);
            seek_count(p->right,level+1);
 
    }
    return p;
}
 
void print_tree (tree *p, int level)
{
    if (p)
    {
        print_tree(p->left, level+1);
        for (int i=0; i<level; i++)
        cout<<" ";
        cout<<p->eng<<endl;
            cout<<p->rus<<endl;
        for (int i=0; i<level; i++)
        cout<<" ";
        cout<<p->count<<endl;
        print_tree (p->right, level+1);
    }
    lev=level;
}

Теперь думаю,как организовать пункт б: найденная компонента заносится в новый словарь и удаляется из старого;
Пока есть такое:

C++
1
2
3
4
5
6
7
8
...
tree *p=seek_count(root,0); //р-найденный узел с максимальным счетчиком
    DeleteNode(p); // передаю в функцию удаления узла найденное значение
    cout<<"\nMax= "<<max_l<<endl;
    tree *new_root=NULL;
    if(new_root==NULL)
        new_root=copy_root(p); //заношу в новый словарь найденное значение
    print_tree (new_root, 0);

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
tree* copy_root(tree*p)
{
 
    tree *pv=new tree;
    pv->eng=p->eng;
    pv->rus=p->rus;
    pv->count=p->count;
    pv->left=0;
    pv->right=0;
    return pv;
}
tree* DeleteNode(tree*p) //как правильно удалить найденный узел
{
    if(p==NULL)
        return;
 
}

Как правильно удалить найденный узел,подскажите пожалуйста?

Добавлено через 54 минуты
Вообщем написала такую функцию удаления,почему оно не удаляет узел?вроде все по правилам делала

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
void DeleteNode(tree*root,tree*p)
{
    tree *p_new,*pp;
    if(p->left==NULL&&p->right==NULL)
    {
        p=NULL;
        return;
    }
    else if(p->right==NULL)
    {
        p=p->left;
        return;
    }
    else if(p->left==NULL)
    {   p=p->right;
    return;
    }
    else
    {
        p_new=p->left;
        pp=p;
        while(p_new->right!=NULL)
        {
            pp=p_new;
            p_new=p_new->right;
        }
        p_new->right=p->right;
        if(pp!=p)
        {
            pp->right=p_new->left;
            p_new->left=p->left;
        }
    }
    p=p_new;
    
    free(p);
    return;
}

C++
1
2
3
4
tree *p=seek_count(root,0);
    cout<<"Delete"<<endl;
    DeleteNode(root,p);
        print_tree (root, 0);

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .