AYUDA CON ARBOLES BINARIOS
Yaiza
19 de Noviembre del 2004
HOla
TEngo que hacer un programa para gestionar arboles genealogicos. El profesor nos pide que lo hagamos con listas enlazadas y arboles pero como siempre nos lo da todo por sabido y no explica nada. he buscado en libros y tengo apuntes muy buenos sobre listas enlazadas pero de arboles no tengo nada y no se como empezar
TEngo que hacer un programa para gestionar arboles genealogicos. El profesor nos pide que lo hagamos con listas enlazadas y arboles pero como siempre nos lo da todo por sabido y no explica nada. he buscado en libros y tengo apuntes muy buenos sobre listas enlazadas pero de arboles no tengo nada y no se como empezar
kamegeist
19 de Noviembre del 2004
es imposible que no encuentre ese tema de arboles en algun libro de estructuras de datos!
Yaiza
19 de Noviembre del 2004
Si, he encontrado unos libros en la biblioteca que hablaban de arboles pero no aclaraban nada,
noel solw
19 de Noviembre del 2004
Te envio un programa que trabaja con arboles binarios y el header file generico.
Espero que sea util.
*************************************************************************
// program k20a5.cpp - page 411
// binary search tree : print inorder, preorder and postorder forms.
// (not recursive solution).
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1
#include "Tree.h"
enum type {IN,PRE,POST};
char *msg[3] = {"InOrder","PreOrder","PostOrder"};
void Print(Node<int> *p)
{
if(first)
{
cout << "{" << p->info;
first = 0;
}
else
cout << "," << p->info;
} // PRINT
void Traversal(Node<int> *p,int sw)
{
if(!p)
return;
switch(sw)
{
case PRE : Print(p); // PreOrder : Node-Left-Rigth
Traversal(p->left,sw); // NLR
Traversal(p->right,sw);
break;
case IN : Traversal(p->left,sw); // InOrder : Left-Node-Rigth
Print(p); // LNR
Traversal(p->right,sw);
break;
case POST : Traversal(p->left,sw); // PostOrder : Left-Rigth-Node
Traversal(p->right,sw); // LRN
Print(p);
break;
}
} // TRAVERSAL
void Show(Node<int> *p,int sw)
{
cout << setw(9) << msg[sw] << ": ";
if(!p)
cout << "{empty tree}" << endl;
else
{
first = 1;
Traversal(p,sw);
cout << "}" << endl;
}
} // SHOW
void Process()
{
int data[] = {40,20,10,5,15,13,17,16,30,35,33,60,
50,45,43,47,42,44,70,65,67,68};
Tree<int> a(sizeof(data)/sizeof(int),data);
Node<int> *p = a.GetRoot();
Show(p,IN);
Show(p,PRE);
Show(p,POST);
} // PROCESS
void main()
{
clrscr();
cout << "binary search tree : print inorder, preorder and postorder "
<< "forms.n";
cout << "-----------------------------------------------------"
"-------------------------n";
Process();
cout << "-----------------------------------------------------"
"-------------------------n";
cout << "end of program - good bye ! ! !n";
getch();
} // MAIN
**************************************************************************
// program Tree.h - page 410 . . . . .
// Header File for Tree class.
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1
#include <conio.h>
#include <iostream.h>
#include <iomanip.h>
// -------------------------------------------------------------------------
template <class T>
struct Node
{
T info;
Node<T> *left,
*right;
Node(T = 0);
}; // STRUCT NODE
template <class T>
Node<T>::Node(T INFO = 0)
{
info = INFO;
left = NULL;
right = NULL;
} // NODE CONSTRUCTOR
// -------------------------------------------------------------------------
template <class T>
class Tree
{
private:
Node<T> *root;
int len;
public:
Tree(int = 0,T* = NULL);
~Tree();
void Insert(Node<T>*,T);
Node<T> *GetRoot() {return root;};
void SetRoot(Node<T> *p) {root = p;};
int GetLen() {return len;};
void SetLen(int x) {len += x;};
void Show() const;
void operator=(Tree<T> &);
}; // CLASS TREE
// -------------------------------------------------------------------------
template <class T>
void Tree<T>::Insert(Node<T> *p,T data)
{
if(p->info < data)
{
if(!p->right)
p->right = new Node<T>(data);
else
Insert(p->right,data);
}
else
{
if(!p->left)
p->left = new Node<T>(data);
else
Insert(p->left,data);
}
} // INSERT
template <class T>
Tree<T>::Tree(int num = 0,T *data = NULL)
{
len = 0;
if(!num)
root = NULL;
else
{
root = new Node<T>(data[0]);
len++;
for(int i = 1;i < num;i++)
{
Insert(root,data[i]);
len++;
}
}
} // TREE CONSTRUCTOR
template <class T>
void TreeDel(Node<T> *p)
{
if(!p)
return;
TreeDel(p->left);
TreeDel(p->right);
if(p)
delete(p);
} // TREE DEL
template <class T>
Tree<T>::~Tree()
{
if(len) // avoid unnecesary delete in program k20a24.cpp
TreeDel(root);
} // TREE DESTRUCTOR
int first;
template <class T>
void Traversal(Node<T> *p)
{
if(!p)
return;
Traversal(p->left);
if(first)
{
cout << "{" << p->info;
first = 0;
}
else
cout << "," << p->info;
Traversal(p->right);
} // TRAVERSAL
template <class T>
void Tree<T>::Show() const
{
Node<T> *p = root;
if(!p)
cout << "{empty tree}" << endl;
else
{
first = 1;
Traversal(p);
cout << "}" << endl;
}
} // TREE SHOW
template <class T>
Node<T> *CopyTree(Node<T> *p)
{
if(!p)
return NULL;
Node<T> *q = new Node<int> (p->info);
q->left = CopyTree(p->left);
q->right = CopyTree(p->right);
return q;
} // COPY TREE
template <class T>
void Tree<T>::operator=(Tree<T> &right)
{
root = CopyTree(right.GetRoot());
} // OPERATOR EQUAL
// -------------------------------------------------------------------------
Espero que sea util.
*************************************************************************
// program k20a5.cpp - page 411
// binary search tree : print inorder, preorder and postorder forms.
// (not recursive solution).
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1
#include "Tree.h"
enum type {IN,PRE,POST};
char *msg[3] = {"InOrder","PreOrder","PostOrder"};
void Print(Node<int> *p)
{
if(first)
{
cout << "{" << p->info;
first = 0;
}
else
cout << "," << p->info;
void Traversal(Node<int> *p,int sw)
{
if(!p)
return;
switch(sw)
{
case PRE : Print(p); // PreOrder : Node-Left-Rigth
Traversal(p->left,sw); // NLR
Traversal(p->right,sw);
break;
case IN : Traversal(p->left,sw); // InOrder : Left-Node-Rigth
Print(p); // LNR
Traversal(p->right,sw);
break;
case POST : Traversal(p->left,sw); // PostOrder : Left-Rigth-Node
Traversal(p->right,sw); // LRN
Print(p);
break;
}
} // TRAVERSAL
void Show(Node<int> *p,int sw)
{
cout << setw(9) << msg[sw] << ": ";
if(!p)
cout << "{empty tree}" << endl;
else
{
first = 1;
Traversal(p,sw);
cout << "}" << endl;
}
} // SHOW
void Process()
{
int data[] = {40,20,10,5,15,13,17,16,30,35,33,60,
50,45,43,47,42,44,70,65,67,68};
Tree<int> a(sizeof(data)/sizeof(int),data);
Node<int> *p = a.GetRoot();
Show(p,IN);
Show(p,PRE);
Show(p,POST);
} // PROCESS
void main()
{
clrscr();
cout << "binary search tree : print inorder, preorder and postorder "
<< "forms.n";
cout << "-----------------------------------------------------"
"-------------------------n";
Process();
cout << "-----------------------------------------------------"
"-------------------------n";
cout << "end of program - good bye ! ! !n";
getch();
} // MAIN
**************************************************************************
// program Tree.h - page 410 . . . . .
// Header File for Tree class.
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1
#include <conio.h>
#include <iostream.h>
#include <iomanip.h>
// -------------------------------------------------------------------------
template <class T>
struct Node
{
T info;
Node<T> *left,
*right;
Node(T = 0);
}; // STRUCT NODE
template <class T>
Node<T>::Node(T INFO = 0)
{
info = INFO;
left = NULL;
right = NULL;
} // NODE CONSTRUCTOR
// -------------------------------------------------------------------------
template <class T>
class Tree
{
private:
Node<T> *root;
int len;
public:
Tree(int = 0,T* = NULL);
~Tree();
void Insert(Node<T>*,T);
Node<T> *GetRoot() {return root;};
void SetRoot(Node<T> *p) {root = p;};
int GetLen() {return len;};
void SetLen(int x) {len += x;};
void Show() const;
void operator=(Tree<T> &);
}; // CLASS TREE
// -------------------------------------------------------------------------
template <class T>
void Tree<T>::Insert(Node<T> *p,T data)
{
if(p->info < data)
{
if(!p->right)
p->right = new Node<T>(data);
else
Insert(p->right,data);
}
else
{
if(!p->left)
p->left = new Node<T>(data);
else
Insert(p->left,data);
}
} // INSERT
template <class T>
Tree<T>::Tree(int num = 0,T *data = NULL)
{
len = 0;
if(!num)
root = NULL;
else
{
root = new Node<T>(data[0]);
len++;
for(int i = 1;i < num;i++)
{
Insert(root,data[i]);
len++;
}
}
} // TREE CONSTRUCTOR
template <class T>
void TreeDel(Node<T> *p)
{
if(!p)
return;
TreeDel(p->left);
TreeDel(p->right);
if(p)
delete(p);
} // TREE DEL
template <class T>
Tree<T>::~Tree()
{
if(len) // avoid unnecesary delete in program k20a24.cpp
TreeDel(root);
} // TREE DESTRUCTOR
int first;
template <class T>
void Traversal(Node<T> *p)
{
if(!p)
return;
Traversal(p->left);
if(first)
{
cout << "{" << p->info;
first = 0;
}
else
cout << "," << p->info;
Traversal(p->right);
} // TRAVERSAL
template <class T>
void Tree<T>::Show() const
{
Node<T> *p = root;
if(!p)
cout << "{empty tree}" << endl;
else
{
first = 1;
Traversal(p);
cout << "}" << endl;
}
} // TREE SHOW
template <class T>
Node<T> *CopyTree(Node<T> *p)
{
if(!p)
return NULL;
Node<T> *q = new Node<int> (p->info);
q->left = CopyTree(p->left);
q->right = CopyTree(p->right);
return q;
} // COPY TREE
template <class T>
void Tree<T>::operator=(Tree<T> &right)
{
root = CopyTree(right.GetRoot());
} // OPERATOR EQUAL
// -------------------------------------------------------------------------
Yaiza
19 de Noviembre del 2004
muchas gracias
rodrigo
19 de Noviembre del 2004
en monografias .com,a biene muy bien
noel solw
19 de Noviembre del 2004
No creo que puedas solucionar un arbol genealogico con arboles binarios, necesitas arboles de un tipo completamente distinto.
Yaiza
19 de Noviembre del 2004
Nos mandan con árboles binarios.Tenemos un mes para "aprender" a programar así que los profesores dicen que nos hacen un favor pidiendonos arboles binarios.
noel solw
19 de Noviembre del 2004
Mira, puedo mandarte un programa que implementa arboles binarios.
No se cual es nivel en programacion, pero tienes que saber por lo menos pointers y alocacion dinamica de memoria.
Tengo implementacion sin pointers, con arrays.
Dime que prefieres.
No se cual es nivel en programacion, pero tienes que saber por lo menos pointers y alocacion dinamica de memoria.
Tengo implementacion sin pointers, con arrays.
Dime que prefieres.
nightwalker
19 de Noviembre del 2004
Me harias el favor mas grande del mundo GRACIAS
Yaiza
19 de Noviembre del 2004
Tnego que hacer el programa con listas enlazadas y arboles. No me vale hacerlo con memoria estática.
Muchas gracias
Muchas gracias