Ferramentas de Utilizador

Ferramentas de Site


dev_geral:c:snippet:binary_search_tree

Implementação de Binary Search Tree (BST) em C

Aqui está código que implementa uma simples árvore binária de pesquisa. Não têm auto-balanceamento (nem tão pouco uma função para o fazer).

Ficheiro: bstree.h

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 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
 

Ficheiro: bstree.c

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 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);
}

Exemplo de uso

FIXME Comentar o código.

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 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 %sn",((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("%sn",needle->english);
 
	bstree_free(bstree_root,NULL);
 
	return 0;
}
dev_geral/c/snippet/binary_search_tree.txt · Esta página foi modificada pela última vez em: 2014/09/02 12:39 (Edição externa)