Деревья
Модераторы: Hawk, Romeo, Absurd, DeeJayC, WinMain
-
- Сообщения: 75
- Зарегистрирован: 24 мар 2005, 11:00
Парни,погмогите написать дерево с помощью структур......
Вобщем идея такая:
struct NODE
{
-----
---
NODE *left
NODE *right
NODE *parent
};
строить дерево должна функция,прототип у неё имеет след. вид
NODE *add(NODE *root, int val) -----прототип
{
if(root == 0)
{
NODE *p = (NODE*)malloc(sizeof(NODE));
p->NODE.left = 0;
............................
............................
return p;
Дальше в цикле пише примерно......Если число больше root,то строим в правую сторону и наоборот
root->left = add(root->left,val)
Наверное она рекурсивно вызываться должна
Забыл сказать на вход поступают числа,и нужно и разложить по этим узлам,а потом отсортировать,но это уже другое
Примерно представляю как это делается,но трудность в не знании синтаксиса,как правильно реализовать это всё....
Помогите ПЛЗ!!!
Заранее спасибо!!!
Вобщем идея такая:
struct NODE
{
-----
---
NODE *left
NODE *right
NODE *parent
};
строить дерево должна функция,прототип у неё имеет след. вид
NODE *add(NODE *root, int val) -----прототип
{
if(root == 0)
{
NODE *p = (NODE*)malloc(sizeof(NODE));
p->NODE.left = 0;
............................
............................
return p;
Дальше в цикле пише примерно......Если число больше root,то строим в правую сторону и наоборот
root->left = add(root->left,val)
Наверное она рекурсивно вызываться должна
Забыл сказать на вход поступают числа,и нужно и разложить по этим узлам,а потом отсортировать,но это уже другое
Примерно представляю как это делается,но трудность в не знании синтаксиса,как правильно реализовать это всё....
Помогите ПЛЗ!!!
Заранее спасибо!!!
По-моему, лучше использовать такую структуру
Создаешь корень - элемент Node* с left = NULL, right = NULL, number=<первое число со входа>
А теперь строишь отсортированное дерево.Алгоритм может быть таким
1. Идти в корень
2. Если число больше числа в текущем узле, то идти в корень правого поддерева текущего элемента (если оно не существует, то создать его)
3. Иначе идти в корень левого поддерева текущего элемента (если оно не существует, то создать его)
4. Если поддерево не было создано на шаге 2 или 3, то вернуться к шагу 2
5. Записать число в корень текущего поддерева
Вот, вроде бы, и все, если я тебя правильно понял и нигде не напортачил...
Код: Выделить всё
struct Node
{
int number;
Node* left;
Node* right;
};
А теперь строишь отсортированное дерево.Алгоритм может быть таким
1. Идти в корень
2. Если число больше числа в текущем узле, то идти в корень правого поддерева текущего элемента (если оно не существует, то создать его)
3. Иначе идти в корень левого поддерева текущего элемента (если оно не существует, то создать его)
4. Если поддерево не было создано на шаге 2 или 3, то вернуться к шагу 2
5. Записать число в корень текущего поддерева
Вот, вроде бы, и все, если я тебя правильно понял и нигде не напортачил...
Не ошибается тот, кто ниченго не делает...
-
- Сообщения: 75
- Зарегистрирован: 24 мар 2005, 11:00
Спасибо .......Алгоритм то я примерно представляю...
Но хотелось бы увидеть как это всё будет выглядеть на бумаге....
Но хотелось бы увидеть как это всё будет выглядеть на бумаге....
Т.е.?.. Код что ли?.. Я бы сделал примерно так:qwertyuiop писал(а): Но хотелось бы увидеть как это всё будет выглядеть на бумаге....
Код: Выделить всё
//Для простоты
#define input_count 10
int input[]
Не ошибается тот, кто ниченго не делает...
-
- Сообщения: 75
- Зарегистрирован: 24 мар 2005, 11:00
Bikutoru, Спасибо большое....
Завтара с утреца буду разбираться.....
Очень благодарен!!!
Завтара с утреца буду разбираться.....
Очень благодарен!!!
А скажите, как можно осуществить ввод-вывод элементов в-из дерево, если оно не бинарное и у каждого элемента может быть произвольное количество потомков??
Юный Падаван
- Romeo
- Сообщения: 3091
- Зарегистрирован: 02 мар 2004, 17:25
- Откуда: Крым, Севастополь
- Контактная информация:
Тогда у каждой вершины можно сделать список дуг. Например так.
В первом случае data - некое поле, содержащее информацию о вершине, например её порядковый номер. Во втором случае data - это некое число, содержащее инофрмацию о дуге, например её длина.
Код: Выделить всё
struct Edge;
struct Vertex
{
int data;
Edge* edges;
};
struct Edge
{
int data;
Node* dest;
Edge* next;
};
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
А можно это все в класс поместить?? Значение в вершине, указатель на массив потомков, количество потомков?? Например как-нибудь так.. :
И как осуществить именно ввод значений в дерево, допустим, целочисленное?? Как пользователю предоставить ввести любую вершину самому?? Он ведь см выбрать должен, чего и куда вводить. Но прежде он должен увидеть то, что уже имеется.
Код: Выделить всё
typedef int TreeltemType;
class Vertex
{
private:
TreeltemType item; //Значение в вершине
int count; // Число потомков
Vertex *ch; // Указатель на потомков
public:
Vertex():item(0),count(0),ch(NULL){};
Vertex(const TreeltemType& nodeltem,int n,Vertex *T):
item(nodeltem),count(n),ch(T){};
// ..Методы..
};
Юный Падаван
road.h:
print.cpp:
print.h:
cway.h:
cway.cpp:
gamg.h:
gamg.cpp:
Makefile:
Столкнулся с проблемой мультиопределения глобальных указателей на стадии сборки объектных файлов. #pragma once дает тот же эффект. В принципе оно и понятно. Но как устранить неполадку я так и не додумалсо.
Код: Выделить всё
#ifndef _ROAD_H_
#define _ROAD_H_
#include "string.h"
#include "iostream"
using namespace std;
int **troad;
string *tname;
int tempcount;
#endif // _ROAD_H_
Код: Выделить всё
#include "road.h"
void Print(int& count)
{
printf(" ");
for(int p=0;p<count;p++)
cout<<tname[p]<<" ";
printf("\n");
for(int y=0;y<count;y++)
{
cout<<tname[y]<<" ";
for(int z=0;z<count;z++)
cout<<troad[y][z]<<" ";
cout<<endl;
}
}
Код: Выделить всё
#ifndef _PRINT_H_
#define _PRINT_H_
void Print(int& count);
#endif // _PRINT_H_
Код: Выделить всё
#ifndef _CWAY_H_
#define _CWAY_H_
bool CheckWay(string& city1,string& city2,int& count);
#endif // _CWAY_H_
Код: Выделить всё
#include "road.h"
bool CheckWay(string& city1,string& city2,int& count)
{
int f1=-1,f2=-1;
for(int a=0;a<count;a++)
{
if(tname[a]==city1)
f1=a;
if(tname[a]==city2)
f2=a;
if((f1>0)&&(f2>0))
break;
}
if(((f1)>=0)&&((f2)>=0))
{
troad[f1][f2]=1;
troad[f2][f1]=1;
return true;
}
else return false;
}
Код: Выделить всё
#ifndef _GAMG_H_
#define _GAMG_H_
#include "road.h"
bool CheckGamGraf(int& iX,int& count, int* label);
#endif // _GAMG_H_
Код: Выделить всё
#include "road.h"
bool CheckGamGraf(int& iX,int& count, int* label)
{
label[iX]=2;
bool L=false;
tempcount++;
for(int i=0;i<count;i++)
{
if(troad[iX][i]==1)
{
if(i==0)
if(tempcount==count)
return true;
if(label[i]==0)
{
L=CheckGamGraf(i,count,label);
if(L==true)return true;
}
}
}
tempcount--;
label[iX]=0;
return L;
}
Код: Выделить всё
#Makefile for GamGraf project
GamGraf: print.o cway.o gamg.o main.o
g++ -o GamGraf print.o cway.o gamg.o main.o
main.o: main.cpp
g++ -c main.cpp
gamg.o: gamg.cpp
g++ -c gamg.cpp
cway.o: cway.cpp
g++ -c cway.cpp
print.o: print.cpp
g++ -c print.cpp
clean:
rm -f *.o GamGraf
Юный Падаван
main.cpp:
Код: Выделить всё
#include "road.h"
#include "print.h"
#include "gamg.h"
#include "cway.h"
int main()
{
int count=0;
int out=0;
char c;
while(out!=1)
{
printf("a - Vertex++\n");
printf("p - Print\n");
printf("r - Make roads\n");
printf("g - Gamilton's graph\n");
printf("c - EXIT\n");
printf("\n>>\n");
cin>>c;
printf("\n");
switch (c)
{
case 'a':
{
int **ct;
string *cn;
if(count!=0)
{
ct=new int*[count];
for(int h=0;h<count;h++)
ct[h]=new int[count];
cn=new string[count];
for(int i=0;i<count;i++)
{
ct[i]=troad[i];
for(int q=0;q<count;q++)
ct[i][q]=troad[i][q];
cn[i]=tname[i];
}
}
count++;
tname=new string[count];
troad=new int*[count];
for(int j=0;j<count;j++)
troad[j]=new int[count];
if(count!=1)
{
for(int k=0;k<count-1;k++)
{
for(int kk=0;kk<count-1;kk++)
troad[k][kk]=ct[k][kk];
troad[k][count-1]=0;
tname[k]=cn[k];
}
for(int j=0;j<count-1;j++)
delete ct[j];
delete[]ct;
delete[]cn;
}
troad[count-1]=new int[count];
for(int x=0;x<count;x++)
troad[count-1][x]=0;
printf("Enter the name of the point> ");
cin>>tname[count-1];
break;
}
case 'p':
{
Print(count);
break;
}
case 'g':
{
int *label=new int[count];
for(int j=0;j<count;j++)
label[j]=0;
tempcount=0;
bool Gam=false;
int iX=0;
Gam=CheckGamGraf(iX,count,label);
if(Gam==true)
printf("This is Gamilton's graph\n");
else printf("This is NOT Gamilton's graph\n");
delete []label;
break;
}
case 'r':
{
bool way=false;
printf("Don't remember that every road have ONE way!\n\n");
printf("1 means the way i-town <--> j-town\n");
Print(count);
string city1,city2;
printf("\nEnter START-town>");
cin>>city1;
printf("Enter END-town>");
cin>>city2;
way=CheckWay(city1,city2,count);
if(way==false) printf("ERROR!!\n");
break;
}
case 'c':
{
out++;
break;
}
default:continue;
}
}
return 0;
}
Юный Падаван