Форум программистов, компьютерный форум CyberForum.ru

Построение сбалансированного дерева из файла - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
[FENIX]
 Аватар для [FENIX]
1 / 1 / 0
Регистрация: 09.10.2009
Сообщений: 162
31.03.2011, 15:34     Построение сбалансированного дерева из файла #1
Народ, помогите пожалуйста, нужно написать функции:

Node * CreateBalansedTree(char * fname); – функция создает сбалансированное бинарное дерево. Функция вначале открывает файл, читает первую строку (имя узла) и создает корневой узел. Далее для всех оставшихся строк из файла вызывает функцию:
void AddNode(Node * node, char * name);

AddNode добавляет слева/справа дочерний узел, если у текущего узла нет дочерних узлов слева/справа, в противном случае выбирает дочерний узел у которого высота меньше (а если высоты равны то выбирает левый) и вызывает функцию AddNode() для выбранного узла.

Необходимо использовать функции Win32 API

Исходник:

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
136
137
138
139
140
141
142
143
144
145
146
// Laba5_OS.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <Windows.h>
#include <string>
using namespace std;
//#include <iostream.h>
 
 
//Узел бинарного дерева
 
int count;
char S[50];
struct Node
{
    char value; //значение узла
    Node * left;        //левая ветвь
    Node * right;       //правая ветвь
    
    //Конструктор структуры
    Node() {
        left = right = NULL;
    }
 
    Node(char x)
    {
        value=x;
        left = right = NULL;
    }
 
};
 
int ascii_cod(char x)
{
    int a;
    a = x;
    return a;
}
 
//левосторонний алгоритм обхода дерева, и вывывод узлов на экран
void LKP(Node* pointer)
{
    if(pointer!=NULL)
    {
        LKP(pointer->left);
        printf("%c ",pointer->value);
        
        LKP(pointer->right);
    }
}
 
 
void AddNode(Node * pointer, char  name)
{
    
 
    if (pointer->left == NULL) {
            pointer->left = new Node(name);
        } else
        if (pointer->right == NULL) {
 
            pointer->right = new Node(name);
        } else {
            AddNode(pointer->left, name);
            
            
        }
    
}
 
 
//Создание сбалансированного дерева
//Я добавил параметр Node* pointer, т.к. не знаю, как без него обойтись
Node* createBalanced(char * fname, Node* pointer) {
 
    FILE *fp;
 
 
    //действия, если файл не открылся
    if ((fp = fopen(fname, "r")) == NULL)
    {
        puts("File not found\n");
        fclose(fp);
        return NULL;
        
    }
    else
    {
        //действия, если файл существует
        //char S[50];
        fgets(S, 50, fp);//В S считываем содержимое файла
        int count1=0;
 
        while(  ascii_cod(S[count1]) > 0 )
        {
            printf("%d\n", ascii_cod(S[count1]) );
            count1++;
        }
 
 
        if(pointer==NULL)
            pointer=new Node(S[0]);
        else
        {
            AddNode(pointer->left,S[1]);
        }
        
 
 
        //count=count1;
        
 
        fclose(fp);
        return pointer;
    }
 
    
}
 
 
void _tmain(int argc, _TCHAR* argv[])
{
 
    //Открытие файла. Если файла нет, он создаётся
    //HANDLE fp = CreateFile ("Tree.txt", GENERIC_WRITE && GENERIC_READ, 0, NULL, /*CREATE_ALWAYS*/CREATE_NEW, 0, NULL);
 
    Node * root = NULL;
    //root=openFile("Tree.txt");
 
    
    root=createBalanced("Tree.txt", root);
 
 
 
    //printf("\n\n\n %d\n",count);
    
 
    LKP(root);
    
    int b;
    scanf("%d",&b);
 
    //CloseHandle(fp);
    
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.03.2011, 15:34     Построение сбалансированного дерева из файла
Посмотрите здесь:

Построение дерева каталогов C++
из сбалансированного дерева в дерево поиска C++
Деревья (алгоритм создания СБАЛАНСИРОВАННОГО бинарного дерева) C++
C++ Поиск минимального элемента идеально сбалансированного дерева
C++ Создание и обработка сбалансированного дерева
C++ Алгоритм построения сбалансированного дерева
Разработать программу построения идеально сбалансированного дерева, элементами которого являются целые числа, C++
Построение В*-дерева C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 08:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru