class Node {
public:
char *data;
Node *left;
Node *right;
Node();
Node(char *t);
};
[C++] Бинарнoe дерево
Опять же возникла очень странная проблемка.
Класс Node:
Конструкторы(про выделение памяти знаю, но почему-то если его делать, то вообще перестает работать):
Вставка новых вершин:
Печать его:
Формирование дерева из данных, лежащих в файле:
Значит ситуация такова: если я просто возьму и создам массив строк(char *t[]={"hello","world","c++","programming","devil"...и т.д.}) и начну формировать дерево из этого массива так:
то все выводится отлично.
Если же я достаю строки из файла в функции FormTree, то выводится n раз, где n-кол-во строк в файле, последняя запись файла. Где собачка не подскажите?
Класс Node:
Код:
Конструкторы(про выделение памяти знаю, но почему-то если его делать, то вообще перестает работать):
Код:
Node::Node() {
data="\0";
}
Node::Node(char *t) {
data=t;
}
data="\0";
}
Node::Node(char *t) {
data=t;
}
Вставка новых вершин:
Код:
Node* Insert(Node* root,Node* r,char *t) {
if(!r) {
r=(Node *)malloc(sizeof(Node));
r->left=NULL;
r->right=NULL;
r->data=t;
if(!root) return r;
if(t<root->data) root->left=r;
else root->right=r;
return r;
}
if(t<root->data) Insert(r,r->left,t);
else Insert(r,r->right,t);
return root;
}
if(!r) {
r=(Node *)malloc(sizeof(Node));
r->left=NULL;
r->right=NULL;
r->data=t;
if(!root) return r;
if(t<root->data) root->left=r;
else root->right=r;
return r;
}
if(t<root->data) Insert(r,r->left,t);
else Insert(r,r->right,t);
return root;
}
Печать его:
Код:
void Print(Node *root) {
if(!root) return;
if(root->left!=NULL) {
cout << root->data << endl;
Print(root->left);
}
if(root->right!=NULL) {
cout << root->data << endl;
Print(root->right);
}
}
if(!root) return;
if(root->left!=NULL) {
cout << root->data << endl;
Print(root->left);
}
if(root->right!=NULL) {
cout << root->data << endl;
Print(root->right);
}
}
Формирование дерева из данных, лежащих в файле:
Код:
void FormTree() {
char t[50];
ifstream FILE("point.txt");
while(!FILE.eof()) {
FILE.getline(t,' ');
root=Insert(root,root,t);
}
FILE.close();
Print(root);
}
char t[50];
ifstream FILE("point.txt");
while(!FILE.eof()) {
FILE.getline(t,' ');
root=Insert(root,root,t);
}
FILE.close();
Print(root);
}
Значит ситуация такова: если я просто возьму и создам массив строк(char *t[]={"hello","world","c++","programming","devil"...и т.д.}) и начну формировать дерево из этого массива так:
Код:
for(int i=0;i<sizeof(t)/sizeof(*t);i++)
root=Insert(root,root,t);
root=Insert(root,root,t);
то все выводится отлично.
Если же я достаю строки из файла в функции FormTree, то выводится n раз, где n-кол-во строк в файле, последняя запись файла. Где собачка не подскажите?
При чтенпии из файла, все data указывают на t[50] из FormTree().
Конечно нужен был бы деструктор, который
пройдет по дереву и для каждого элемента вызовет free(data) и в Insert вместо
if(t<root->data)
нужен
if(strcmp(t, root->data)<0)
Код:
void FormTree() {
char t[50];
ifstream FILE("point.txt");
while(!FILE.eof())
{
FILE.getline(t,' ');
char *newt = strdup(t);
root=Insert(root,root,newt);
}
FILE.close();
Print(root);
}
char t[50];
ifstream FILE("point.txt");
while(!FILE.eof())
{
FILE.getline(t,' ');
char *newt = strdup(t);
root=Insert(root,root,newt);
}
FILE.close();
Print(root);
}
пройдет по дереву и для каждого элемента вызовет free(data) и в Insert вместо
if(t<root->data)
нужен
if(strcmp(t, root->data)<0)
Вы код проверяли? у меня все осталось по-прежнему. выводится последняя запись
Update:
Выводится теперь.
Update:
Выводится теперь.
Почему-то выводятся не все строки из файла. Да и присутствуют повторы. Например, файл={"hello","world","c++","programming"}. Вывод дерева:
hello
hello
c++
А надо:
hello
world
c++
programming
Кстати, функцию вставки я неверную запостил. Надо без сравниваний.
Вот:
hello
hello
c++
А надо:
hello
world
c++
programming
Кстати, функцию вставки я неверную запостил. Надо без сравниваний.
Вот:
Код:
Node* Insert(Node* root,Node* r,char *t) {
if(!r) {
r=(Node *)malloc(sizeof(Node));
r->left=NULL;
r->right=NULL;
r->data=t;
if(!root) return r;
if(root->left==NULL) root->left=r;
else root->right=r;
return r;
}
if(r->left==NULL) Insert(r,r->left,t);
else Insert(r,r->right,t);
return root;
}
if(!r) {
r=(Node *)malloc(sizeof(Node));
r->left=NULL;
r->right=NULL;
r->data=t;
if(!root) return r;
if(root->left==NULL) root->left=r;
else root->right=r;
return r;
}
if(r->left==NULL) Insert(r,r->left,t);
else Insert(r,r->right,t);
return root;
}
У тебя класс node не совсем правильно спроектирован.
Я минимально исправил, чтоб хотя бы работал, но все равно лучше бы переделать.
Я минимально исправил, чтоб хотя бы работал, но все равно лучше бы переделать.
Код:
#include <windows.h>
#include <iostream>
#include <string>
#include <iomanip.h>
#include <fstream>
using namespace std;
class Node
{
public:
char *data;
Node *left;
Node *right;
};
Node * root = NULL;
void Print(Node *root)
{
if(!root) return;
std::cout << root->data << endl;
Print(root->left);
Print(root->right);
}
Node* Insert(Node* root,Node* r,char *t)
{
if(!root)
{
root=(Node *)malloc(sizeof(Node));
root->left=NULL;
root->right=NULL;
root->data=t;
return root;
}
if(!r)
{
r=(Node *)malloc(sizeof(Node));
r->left=NULL;
r->right=NULL;
r->data=t;
}
if(strcmp(root->data, r->data)<0)
{
if(root->left)
Insert(root->left, r, t);
else
root->left = r;
}
else if(root->right)
Insert(root->right, r, t);
else
root->right = r;
return r;
}
void FormTree()
{
char t[50];
ifstream FILE("C:\\test.txt");
while(!FILE.eof())
{
FILE.getline(t,' ');
char *newt = strdup(t);
if(root)
Insert(root,NULL,newt);
else
root = Insert(root, NULL, newt);
}
FILE.close();
Print(root);
}
int main(int argc, char* argv[])
{
FormTree();
system("PAUSE");
return 0;
}
#include <iostream>
#include <string>
#include <iomanip.h>
#include <fstream>
using namespace std;
class Node
{
public:
char *data;
Node *left;
Node *right;
};
Node * root = NULL;
void Print(Node *root)
{
if(!root) return;
std::cout << root->data << endl;
Print(root->left);
Print(root->right);
}
Node* Insert(Node* root,Node* r,char *t)
{
if(!root)
{
root=(Node *)malloc(sizeof(Node));
root->left=NULL;
root->right=NULL;
root->data=t;
return root;
}
if(!r)
{
r=(Node *)malloc(sizeof(Node));
r->left=NULL;
r->right=NULL;
r->data=t;
}
if(strcmp(root->data, r->data)<0)
{
if(root->left)
Insert(root->left, r, t);
else
root->left = r;
}
else if(root->right)
Insert(root->right, r, t);
else
root->right = r;
return r;
}
void FormTree()
{
char t[50];
ifstream FILE("C:\\test.txt");
while(!FILE.eof())
{
FILE.getline(t,' ');
char *newt = strdup(t);
if(root)
Insert(root,NULL,newt);
else
root = Insert(root, NULL, newt);
}
FILE.close();
Print(root);
}
int main(int argc, char* argv[])
{
FormTree();
system("PAUSE");
return 0;
}
Доделываю программу до логического завершения. Но она ведет себя странно. Функция поиска работает в C++ Builder 6.0. В версиях ниже 6 не работает. А в универе вообще стоят MS Visual C++ 6.0. Кто-нибудь может проверить работоспособность на VC6.0?
Файл: [ATTACH]1826[/ATTACH]
Файл: [ATTACH]1826[/ATTACH]
Цитата: Ginza9
Доделываю программу до логического завершения. Но она ведет себя странно. Функция поиска работает в C++ Builder 6.0. В версиях ниже 6 не работает. А в универе вообще стоят MS Visual C++ 6.0. Кто-нибудь может проверить работоспособность на VC6.0?Файл: [ATTACH]1826[/ATTACH]
Не проверял, но все равно сперва нужно бы в ф-ии Find() переменную key объявить напр. как
char key[128]; или заменить на string
Код:
void Find(Node &obj)
{
string key;
cout << "Enter the word you want to find: ";
cin >> key;
obj.Search(root,key.c_str());
}
{
string key;
cout << "Enter the word you want to find: ";
cin >> key;
obj.Search(root,key.c_str());
}
void Search(Node *root,const char *key);
Спасибо. Очень прошу тебя проверить на VC6.0
Нет смысла проверять, потому что если твой препод хоть чуть чуть тянет, тогда за такую прогу двойку прставит. А если не тянет то и так пойдет.
Дерево - это контейнер. Узел - это элементы контейнера. Поэтому нужно определить два разных класса. Ты определил один. И поэтому в той программе, многое делается через голову. Подправил код, но проверить или в случае чего до ума довести теперь у меня времени нету.
Дерево - это контейнер. Узел - это элементы контейнера. Поэтому нужно определить два разных класса. Ты определил один. И поэтому в той программе, многое делается через голову. Подправил код, но проверить или в случае чего до ума довести теперь у меня времени нету.