Sati
09 de Mayo del 2004

Tengo que hacer una practica en la que tengo que utilizar arboles binarios ( de expresion) para introducir una expresion y luego evaluarla. Y la verdad no se por donde cogerlo. Tengo que usar pilas para ver las prioridades? NO se, no tengo ni idea, me podeis ehcar una mano??
Gracias por adelantado!!

Alejandro_
09 de Mayo del 2004

Un buen lugar para empesar es el google. Pon "arboles binarios" y encontrarás varios sitios y archivos pdf con explicaciones y ejemplos.

Alejandro

Sati
09 de Mayo del 2004

Si, si la verdad es q se como se manejan los arboles binarios el problema es mas bien de C++ que no lo conozco, lo q me gustaria es codigo para poder ver como va, como implementarlos y todo eso

noel solw
09 de Mayo 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
// -------------------------------------------------------------------------