Ayudame por favor (Arboles de orden N)

lorenluz
09 de Noviembre del 2005
Necesito saber como se crea un arbol de orden n, como cargar datos, etc. Lo que tenga me biene bien. Es para un trabajo de la Universidad (me pidieron que implemente la Busqueda 1º en Prof., en el juego del TATETI.) Lo tengo que entregar el 15/11/05.

Ayudenme por favor. Desde ya eternamente muy agradecida.

alkdaras
09 de Noviembre del 2005
// tree.c

/*
* Laboratorio de Programacion 3
* INCO-FI-UDELAR
*
* Arbol General de Enteros
* Implementado utilizando una estructura primer hijo-siguiente hermano
*/

// Definicion de Tipo

#include <stdlib.h>
#include <assert.h>
#include "tree.h"


struct Node {
int data;
struct Node *phijo;
struct Node *shermano;
};

// typedef struct Node * Tree;
// Tipo opaco, el struct Nodo se debe definir en tree.cpp


// Constructoras

Tree makeNullTree (){
// Construye el Arbol vacio.
return NULL;
}

Tree createTree (int val){
// Construye el Arbol con valor val en la raiz y sin hijos.
Tree t;
t = (Tree)malloc(sizeof(Node));
t -> data = val;
t -> phijo = NULL;
t -> shermano = NULL;
return t;
}

void addChildTree (Tree & parent, Tree child){
// Precondicion: el Arbol no es vacio.
// Agrega el Arbol child como primero en la lista de hijos de parent.
// Esta operacion se debe realizar en O(1) peor caso.
assert(parent != NULL);
child -> shermano = parent -> phijo;
parent -> phijo = child;
}

// Predicados

bool isEmptyTree (Tree t){
// Retorna true si el Arbol esta vacio y false si no.
// Esta operacion se debe realizar en O(1) peor caso.
return t == NULL;
}

// Selectoras

int getValueTree (Tree t){
// Precondicion: el Arbol no es vacio.
// Retorna el valor de la raíz del Arbol.
// Esta operacion se debe realizar en O(1) peor caso.
assert(t != NULL);
return t -> data;
}

Tree getFirstChildTree (Tree t){
// Precondicion: el Arbol no es vacio.
// Retorna el Primer Hijo del Arbol.
// Esta operacion se debe realizar en O(1) peor caso.
// En caso de no tener hijos retorna un Arbol vacio.
assert(t != NULL);
return t -> phijo;
}

Tree getNextSiblingTree (Tree t){
// Precondicion: el Arbol no es vacio.
// Retorna el Primer Hermano del Arbol.
// Esta operacion se debe realizar en O(1) peor caso.
// En caso de no tener hermanos retorna un Arbol vacio.
assert(t != NULL);
return t -> shermano;
}

// Destructoras

void removeChildTree (int val, Tree & parent){
// Precondicion: el Arbol no es vacio.
// Elimina el Primer Hijo de parent con valor val.
// Esta operacion se debe realizar en O(n) peor caso,
// siendo n la cantidad de hijos de parent.
assert(parent != NULL);
Tree t = parent -> phijo;
Tree temp;
if (t -> data == val){
parent -> phijo = t -> shermano;
destroyTree(t);
return;
}

while(t -> shermano != NULL){
if (t -> shermano -> data == val){
temp = t -> shermano;
t -> shermano = t -> shermano -> shermano;
destroyTree(temp);
} else {
t = t -> shermano;
}
}
}

void destroyTree (Tree & t){
// Libera la memoria asociada al Arbol.
if (t != NULL) {
destroyTree(t -> phijo);
destroyTree(t -> shermano);
free(t);
t = NULL;
}
}