• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

orium

[C] Binary Search Tree

1 mensagem neste tópico

Aqui esta' codigo que implementa uma simples arvore binaria de pesquisa. Não têm auto-balanciamento (nem tão pouco uma funçao para o fazer).

bstree.h:

/*
*  GPL
*
*  Written by Diogo Sousa aka orium
*  Copyright © 2008 Diogo Sousa
*
*  This program is free software: you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef BSTREE_H_
#define BSTREE_H_

struct bstree_node
{
void *data;

struct bstree_node *left;
struct bstree_node *right;
};

extern int bstree_add(struct bstree_node **,
	     void *,
	     int (*)(const void *, const void *));
extern void bstree_walk(struct bstree_node *,
	       void (*)(void *));
extern void bstree_free(struct bstree_node *,
	       void (*)(void *));
extern void *bstree_search(struct bstree_node *,
		  void *,
		  int (*)(const void *, const void *));

#endif

bstree.c

/*
*  GPL
*
*  Written by Diogo Sousa aka orium
*  Copyright © 2008 Diogo Sousa
*
*  This program is free software: you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

/* TODO:
*       * Deletion
*       * Rebalancing
*/

#include <stdlib.h>

#include "bstree.h"

static struct bstree_node *alloc_bstree_node(void);
static int bstree_insert(struct bstree_node *,
		 struct bstree_node *,
		 int (*)(const void *, const void *));
static void *bstree_search_recursive(struct bstree_node *,
			     void *,
			     int (*)(const void *, const void *));

static struct bstree_node *alloc_bstree_node(void)
{
struct bstree_node *r;

r=malloc(sizeof(*r));

if (r == NULL)
	abort();

return r;
}

static int bstree_insert(struct bstree_node *tree_node,
		 struct bstree_node *node,
		 int (*cmp)(const void *, const void *))
{
struct bstree_node **dn;
int d;

d=cmp(node->data,tree_node->data);

if (!d)
	return -1;

if (d > 0)
	dn=&tree_node->right;
else
	dn=&tree_node->left;

if (*dn == NULL)
{
	*dn=node;
	node->left=NULL;
	node->right=NULL;
}
else
	return bstree_insert(*dn,node,cmp);

return 0;
}

int bstree_add(struct bstree_node **root,
       void *data,
       int (*cmp)(const void *, const void *))
{
struct bstree_node *node;

if (data == NULL) /* This may be used as a special value */
	return -1;

node=alloc_bstree_node();
node->data=data;

if (*root == NULL)
{
	*root=node;
	node->left=NULL;
	node->right=NULL;
	return 0;
}

return bstree_insert(*root,node,cmp);
}

void bstree_walk(struct bstree_node *node,
	 void (*action)(void *))
{
if (node == NULL)
	return;

action(node->data);

bstree_walk(node->left,action);
bstree_walk(node->right,action);
}

void bstree_free(struct bstree_node *node,
	 void (*action)(void *))
{
if (node == NULL)
	return;

if (action != NULL)
	action(node->data);

bstree_free(node->left,action);
bstree_free(node->right,action);

free(node);
}

static void *bstree_search_recursive(struct bstree_node *tree_node,
			     void *needle,
			     int (*cmp)(const void *, const void *))
{
struct bstree_node **dn;
int d;

d=cmp(needle,tree_node->data);

if (!d)
	return tree_node->data;

if (d > 0)
	dn=&tree_node->right;
else
	dn=&tree_node->left;

if (*dn != NULL)
	return bstree_search_recursive(*dn,needle,cmp);

return NULL;
}

void *bstree_search(struct bstree_node *root,
	    void *needle,
	    int (*cmp)(const void *, const void *))
{
if (root == NULL)
	return NULL;

return bstree_search_recursive(root,needle,cmp);
}

E um pequeno exemplo:

/*
*  GPL
*
*  Written by Diogo Sousa aka orium
*  Copyright © 2008 Diogo Sousa
*
*  This program is free software: you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <stdio.h>
#include <assert.h>

#include "bstree.h"

struct integer
{
int n;
char *english;
};

int my_cmp(const void *p1, const void *p2)
{
return ((struct integer *)p1)->n-((struct integer *)p2)->n;
}

void my_twalk_action(void *data)
{
printf("%d %s\n",((struct integer *)data)->n,
       ((struct integer *)data)->english);
}

int main(void)
{
struct bstree_node *bstree_root=NULL;
struct integer i1={1,"one"};
struct integer i2={2,"two"};
struct integer i3={3,"three"};	
struct integer i4={4,"four"};
struct integer i5={5,"five"};
struct integer lost={2,NULL};
struct integer *needle;

bstree_add(&bstree_root,&i3,my_cmp);
bstree_add(&bstree_root,&i1,my_cmp);
bstree_add(&bstree_root,&i5,my_cmp);
bstree_add(&bstree_root,&i4,my_cmp);
bstree_add(&bstree_root,&i2,my_cmp);

bstree_walk(bstree_root,my_twalk_action);

needle=bstree_search(bstree_root,&lost,my_cmp);

assert(needle != NULL);

printf("%s\n",needle->english);

bstree_free(bstree_root,NULL);

return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora