diff options
Diffstat (limited to 'src/bt')
| -rw-r--r-- | src/bt/ft_btdestroy.c | 13 | ||||
| -rw-r--r-- | src/bt/ft_btnew.c | 16 | ||||
| -rw-r--r-- | src/bt/ft_btsorted_insert.c | 38 | ||||
| -rw-r--r-- | src/bt/ft_btsorted_search.c | 35 |
4 files changed, 94 insertions, 8 deletions
diff --git a/src/bt/ft_btdestroy.c b/src/bt/ft_btdestroy.c index c802db0..d8746ef 100644 --- a/src/bt/ft_btdestroy.c +++ b/src/bt/ft_btdestroy.c @@ -6,18 +6,25 @@ /* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/02/07 21:30:53 by cacharle #+# #+# */ -/* Updated: 2020/02/07 21:35:19 by cacharle ### ########.fr */ +/* Updated: 2020/04/26 19:47:45 by charles ### ########.fr */ /* */ /* ************************************************************************** */ #include "libft_bt.h" -void ft_btdestroy(t_ftbtree *tree, void (*del)(void *data)) +/* +** \brief Destroy a binary tree +** \param tree Binary tree to destroy +** \param del Delete function applied to each node data +*/ + +void ft_btdestroy(t_ftbt *tree, void (*del)(void *data)) { if (tree == NULL) return ; ft_btdestroy(tree->left, del); ft_btdestroy(tree->right, del); - (*del)(tree->data); + if (del != NULL) + del(tree->data); free(tree); } diff --git a/src/bt/ft_btnew.c b/src/bt/ft_btnew.c index 973e1a4..09cfa12 100644 --- a/src/bt/ft_btnew.c +++ b/src/bt/ft_btnew.c @@ -6,20 +6,26 @@ /* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/02/07 21:33:16 by cacharle #+# #+# */ -/* Updated: 2020/02/07 21:34:35 by cacharle ### ########.fr */ +/* Updated: 2020/04/26 19:46:57 by charles ### ########.fr */ /* */ /* ************************************************************************** */ #include "libft_bt.h" -t_ftbtree *ft_btnew(void *data) +/* +** \brief Create a new binary tree +** \param data Node's data +** \return Allocated node with left and right set to NULL, NULL on error +*/ + +t_ftbt *ft_btnew(void *data) { - t_ftbtree *tree; + t_ftbt *tree; - if ((tree = (t_ftbtree*)malloc(sizeof(t_ftbtree))) == NULL) + if ((tree = (t_ftbt*)malloc(sizeof(t_ftbt))) == NULL) return (NULL); - tree->data = data; tree->left = NULL; tree->right = NULL; + tree->data = data; return (tree); } diff --git a/src/bt/ft_btsorted_insert.c b/src/bt/ft_btsorted_insert.c new file mode 100644 index 0000000..12c0cde --- /dev/null +++ b/src/bt/ft_btsorted_insert.c @@ -0,0 +1,38 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_btsorted_insert.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/04/26 19:10:36 by charles #+# #+# */ +/* Updated: 2020/04/26 19:19:24 by charles ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_bt.h" + +/* +** \brief Insert a data in a binary search tree so that it stays sorted +** \param tree Tree where data is inserted +** \param data Data to insert +** \param cmp Comparison function +** \return The new root or NULL if a new node couldn't be allocated +*/ + +t_ftbt *ft_btsorted_insert(t_ftbt *tree, void *data, int (*cmp)(void*, void*)) +{ + if (tree == NULL) + return (ft_btnew(data)); + if (cmp(data, tree->data) < 0) + { + if (ft_btsorted_insert(tree->left, data, cmp) == NULL) + return (NULL); + } + else + { + if (ft_btsorted_insert(tree->right, data, cmp) == NULL) + return (NULL); + } + return (tree); +} diff --git a/src/bt/ft_btsorted_search.c b/src/bt/ft_btsorted_search.c new file mode 100644 index 0000000..00629d0 --- /dev/null +++ b/src/bt/ft_btsorted_search.c @@ -0,0 +1,35 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_btsorted_search.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/04/26 19:31:42 by charles #+# #+# */ +/* Updated: 2020/04/26 19:35:53 by charles ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_bt.h" + +/* +** \brief Search a element in a sorted binary tree +** \param tree Searched tree +** \param ref First argument of comparison function +** \param cmp Comparison function +** \return Node data if found, NULL otherwise +*/ + +void *ft_btsorted_search(t_ftbt *tree, void *ref, int (*cmp)(void*, void*)) +{ + int res; + + if (tree == NULL) + return (NULL); + if ((res = cmp(ref, tree->data)) == 0) + return (tree->data); + if (res < 0) + return (ft_btsorted_search(tree->left, ref, cmp)); + else + return (ft_btsorted_search(tree->right, ref, cmp)); +} |