Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
my_life
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 30
1

Бинарные деревья

26.10.2013, 15:01. Просмотров 799. Ответов 6
Метки нет (Все метки)

Возникла проблема с бинарными деревьями . Нужно определить K - количество узлов, ключ которых больше заданного числа N.
Я дошёл только до создания дерева и вывода его на экран:
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
// tree.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
 
struct tree
{
    int info;
    tree* left;
    tree* right;
};
void NewTree(tree* &r, int info)
{
    if(NULL==r)
    {
        r=new tree;
        r->left=r->right=NULL;
        r->info=info;       //запись элемента
    }
        
        if(info<r->info)     //запись в левое поддерево
        {
            if(r->left!=NULL) NewTree(r->left,info);
            else
            {
                r->left=new tree;
                r->left->left=r->left->right=NULL;
                r->left->info=info;
            }
        }
        if(info>r->info)        //запись в левое поддерево
        {
            if(r->right!=NULL) NewTree(r->right,info);
            else
            {
                r->right=new tree;
                r->right->right=r->right->left=NULL;
                r->right->info=info;
            }
        }
}
void Preorder(tree* &p)
{
    if(!p) return;
    cout<<p->info<<" ";
    Preorder(p->left);
    Preorder(p->right);
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL,"Rus");
    tree* r=NULL;
    int info;
    for(int i=1;i<20;i++)
    {
        info=i +3;
        NewTree(r,info);
    }
    cout<<"Элементы дерева: "<<endl;
    Preorder(r);
    cout<<endl;
       int N;
       cout<<"Введите N:";
       cin>>N;
    getch();
    return 0;
}
Не могу понять , как определить это количество узлов ? Помогите , пожалуйста , запутался я что-то с этими поддеревьями совсем . Хотя бы идею подайте , пожалуйста. Заранее огромнейшее спасибо!
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.10.2013, 15:01
Ответы с готовыми решениями:

Бинарные деревья
Компилятор выдаёт ошибки в 9, 10 и 12, 13 строках: invalid conversion from...

Бинарные деревья
Имею три файла: Скажите пожалуйста почему я не могу создать э-т m?(Класс...

Бинарные деревья
Вот задачка: Для заданного бинарного дерева поиска проверить условие: • для...

Бинарные деревья
Очень нужна помощь, вообще деревья не понимаю!!!:( Вершина дерева содержит...

бинарные деревья
Вершина двоичного дерева содержит указатель на строку и указатели на правое и...

6
Hunter13ua
46 / 46 / 18
Регистрация: 25.10.2011
Сообщений: 183
26.10.2013, 16:07 2
В самом лёгком не разобрались? о_О У Вас же есть функция обхода дерева. Создайте некоторую переменную, которая будет счетчиком. И каждый раз возле вывода на экран проверяйте ключ, и если он соответствует условию - счетчик++.
0
my_life
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 30
26.10.2013, 16:16  [ТС] 3
Цитата Сообщение от Hunter13ua Посмотреть сообщение
В самом лёгком не разобрались? о_О У Вас же есть функция обхода дерева. Создайте некоторую переменную, которая будет счетчиком. И каждый раз возле вывода на экран проверяйте ключ, и если он соответствует условию - счетчик++.
Всё , количество узлов нашёл . Получилось )
Мне ещё нужно потом добавить узел с ключом K. Вот это не пойму .
Вот как я искал это K:
C++
1
2
3
4
5
6
7
8
int Preorder1(tree* &p,int &sum,int key)
{
if(!p) return 0;
if((p->info)>key) sum++;
Preorder1(p->left,sum,key);
Preorder1(p->right,sum,key);
return sum;
}
Не пойму , что делать дальше? Как добавить узел с этим ключом? Куда добавить ?Даже суть вопроса не пойму -_-
0
Hunter13ua
46 / 46 / 18
Регистрация: 25.10.2011
Сообщений: 183
26.10.2013, 16:23 4
Как вариант, просто добавить элемент с этим ключом в дерево, уже готовой, у вас, функцией newtree.
0
my_life
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 30
26.10.2013, 16:49  [ТС] 5
Цитата Сообщение от Hunter13ua Посмотреть сообщение
Как вариант, просто добавить элемент с этим ключом в дерево, уже готовой, у вас, функцией newtree.
То есть , просто написать
C++
1
NewTree(r,kol);
Я вот немного не пойму с выводом дерева:
если я например заполняю дерево в цикле
C++
1
2
3
4
5
for(int i=1;i<20;i++)
    {
        info=i+3;
        NewTree(r,info);
    }
Потом на экран выводятся элементы дерева: 4 5 6 7 8 9 ...22

Вот я не могу понять , какая суть этого дерева? В выводе всё-равно не понятно , где левая или правая его часть , просто выводится как обычный массив чисел .

Если ввожу в качестве ключа 20 , количество узлов получается 2 и выводится уже такое дерево:
4 2 5 6 7 ... 22

Добавлено через 1 минуту
не пойму , почему 2-ка пишется после 4-ки ?
0
Hunter13ua
46 / 46 / 18
Регистрация: 25.10.2011
Сообщений: 183
26.10.2013, 16:55 6
Суть дерева в том, что это динамическая структура данных. Выводит как массив по причине. Вы заносите элементы в дерево сравнивая, и у вас обход дерева префиксный, что и даёт вывод по-возрастанию.
На счет двойки - не пойму откуда она вообще взялась.
0
my_life
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 30
26.10.2013, 18:00  [ТС] 7
Цитата Сообщение от Hunter13ua Посмотреть сообщение
Суть дерева в том, что это динамическая структура данных. Выводит как массив по причине. Вы заносите элементы в дерево сравнивая, и у вас обход дерева префиксный, что и даёт вывод по-возрастанию.
На счет двойки - не пойму откуда она вообще взялась.
На счёт 2-ки : например у меня такое дерево:4 5 6 7 8 .....20 21 22
Мне нужно найти количество узлов K , ключ которых больше N
я ввожу N=20
количество найденных узлов получается =2
а потом вывожу новое дерево , уже с добавленным узлом:
4 2 5 6 7 8 9 10 ....20 21 22
Вот не могу понять , почему 2-ка после 4-ки идёт ?

Добавлено через 20 минут
Здесь наверное нужна новая функция , которая будет добавлять элемент в уже созданное дерево? Или всё-таки нет ?

Добавлено через 32 минуты
Вот весь мой код:
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
// tree.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
 
struct tree           //структура дерева
{
    int info;         //информационное поле
    tree* left;       //левая часть
    tree* right;     //правая часть
};
void NewTree(tree* &r, int info)   //функция создания нового дерева
{
    if(NULL==r)
    {
        r=new tree;
        r->left=r->right=NULL;
        r->info=info;       //запись элемента
    }
        
        if(info<r->info)     //запись в левое поддерево
        {
            if(r->left!=NULL) NewTree(r->left,info);
            else
            {
                r->left=new tree;
                r->left->left=r->left->right=NULL;
                r->left->info=info;
            }
        }
        if(info>r->info)        //запись в правое поддерево
        {
            if(r->right!=NULL) NewTree(r->right,info);
            else
            {
                r->right=new tree;
                r->right->right=r->right->left=NULL;
                r->right->info=info;
            }
        }
}
 
 
void Show_Tree(tree* &p)      //функция вывода дерева на экран в порядке возвростания 
{
    if(!p) return;
    cout<<p->info<<" ";
    Show_Tree(p->left);
    Show_Tree(p->right);
}
 
//Функция поиска количества узлов
int K(tree* &p,int &sum,int key)
{
if(!p) return 0;
if((p->info)>key) sum++;
K(p->left,sum,key);
K(p->right,sum,key);
return sum;
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL,"Rus");
    tree* r=NULL;
    int info;
    int sum=0;
    int key;
    for(int i=1;i<10;i++)
    {
        info=i*5;
        NewTree(r,info);
    }
    cout<<"Tree: "<<endl;
    Show_Tree(r);
    cout<<endl;
    cout<<"Enter key:";
    cin>>key;
    int kol=K(r,sum,key);
    cout<<"K="<<kol<<endl;
    NewTree(r,kol);
    cout<<"Tree:"<<endl;
    Show_Tree(r);
    getch();
    return 0;
}
Возникли сложности с добавлением нового узла(
0
26.10.2013, 18:00
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.10.2013, 18:00

Бинарные деревья
Здравствуйте! Подскажите, правильно ли написано правое удаление вершины дерева?...

Бинарные деревья
Доброго времени суток, нужна помощь, дали задание...Вершина бинарного дерева...

Бинарные деревья
Разработать набор классов упорядоченных бинарных деревьев поиска типов:...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru