Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
0 / 0 / 1
Регистрация: 08.01.2015
Сообщений: 3
1

Построить идеально сбалансированное бинарное дерево поиска и обеспечить поиск указанных записей

08.01.2015, 21:03. Показов 2438. Ответов 1
Метки нет (Все метки)

Вообщем написал программу и не уверен, что правильно работает балансировка(
При нечетном количестве элементов (N=7) считает правильно, а при четном не уверен в правильности счета
Само задание:
Имеется файл записей с некоторым ключевым полем.
Построить в оперативной памяти идеально сбалансированное бинарное дерево поиска и обеспечить поиск указанных записей.
Входные данные из файла:
четное количество
12 a
5 b
3 c
7 e
15 f
10 d
20 h
6 g

нечетное
12 a
5 b
3 c
7 e
15 f
10 d
20 h


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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdio.h>
#include <conio.h>
#include <locale.h>
#include <string.h>
#include <stdlib.h>
 
typedef struct tree // структура для представления узлов дерева
{
    int key;
    char st[25];
    struct tree *left;
    struct tree *right;
} tree;
typedef struct list
{
    int key;
    char st[25];
} list;
tree* search(tree* top, int k)
{
    if (top == NULL)
    {
        return NULL;
    }
    {
        if (top->key == k)
        {
            return top;
        }
        else
        {
            if (top->key < k)
            {
                return search(top->right, k);
            }
            else
            {
                return search(top->left, k);
            }
        }
    }
}
 
 
int output(tree* top, int x)
{
    int i;
    if (top == NULL)
    {
        return 0;
    }
    
    for (i = 0; i < x; i++)
    {
        printf(" ");
    }
    printf("%d %s\n", top->key, top->st);
    output(top->left, x + 1);
    output(top->right, x + 1);
}
tree* create_tree(list* mas, int n)
{
    if (n != 0)
    {
        tree* top;
        top = (tree*)malloc(sizeof(tree));
        top->key = mas[n/2].key;
        strcpy(top->st, mas[n/2].st);
        top->left = create_tree(mas, n/2);
        top->right = create_tree(mas + n/2 + 1, n - n/2 - 1);
        return top;
    }
    else
    {
        return NULL;
    }
}
int main()
{
    tree *top;
    tree *other;
    list mas[100];
    list temp;
    int k;
    int n;
    int i;
    int j;
    int x;
    char s[25];
    FILE *infile;
    setlocale(LC_ALL, "Russian");
    printf("Введите название файла: ");
    scanf("%s", s);
    infile = fopen(s, "r");
    if (infile == NULL) 
    {
        printf("Ошибка при открытии файла...\n");
        return 0;
    }
    n = 0;
    while (feof(infile) == 0)
    {
        fscanf(infile,"%d", &mas[n].key);
        fscanf(infile,"%s", &mas[n].st);
        n++;
    }
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (mas[i].key > mas[j].key)
            {
                temp = mas[i];
                mas[i] = mas[j];
                mas[j] = temp;
            }
        }
    }
    top = NULL;
    top = create_tree(mas, n);
    output(top, 0);
    printf("Введите ключ: ");
    scanf("%d", &k);
    other = search(top, k);
    if (other == NULL)
    {
        printf("Нет такого элемента\n");
    }
    else
    {
        printf("%d  %s", other->key, other->st);
    }
    getch();
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.01.2015, 21:03
Ответы с готовыми решениями:

Сформировать идеально сбалансированное бинарное дерево
Дан текст программы. Проверти правильно или нет описание сделал? TNode*...

Сформировать идеально сбалансированное бинарное дерево и найти в нем максимальный элемент
Далее преобразовать его в дерево поиска и тоже найти максимальный элемент.

Сформировать идеально сбалансированное бинарное дерево, тип информационного поля - double
Привет, кто сможет помочь? 1. Сформировать идеально сбалансированное бинарное дерево, тип...

Построить Идеально сбалансированное дерево
Нужно срочно организовать и отладить программу для построения и печати на экран идеально...

1
Модератор
Эксперт функциональных языков программированияЭксперт Python
30645 / 16873 / 3475
Регистрация: 12.02.2012
Сообщений: 28,281
Записей в блоге: 5
08.01.2015, 22:49 2
Я вообще не заметил балансировки в этом коде...
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.01.2015, 22:49

Идеально-сбалансированное дерево
Приветствую,нужно в ИСД добавить элемент так,что бы оно впоследствии осталось таким же. Написал...

Идеально сбалансированное дерево
В файле input.txt хранится последовательность целых чисел.По входной последовательности построить...

Идеально сбалансированное дерево
Дано идеально сбалансированное дерево. Нужно найти сумму его листьев. Дерево построил, но как...

Идеально сбалансированное дерево
Интересует как работает этот кусок кода) по идеи Create(&amp;tmp-&gt;right, nr); сюда компилятор никогда...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru