From bf384468a7e6b4ed7a2070287bbb58863d22bd90 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Luk=C3=A1=C5=A1=20Ji=C5=99i=C5=A1t=C4=9B?= Date: Thu, 7 Aug 2025 15:53:48 +0200 Subject: [PATCH] Implement tree traversal --- Makefile | 1 + ft_struct/ft_rbtree_traversal.c | 133 ++++++++++++++++++++++++++++++++ inc/ft_struct.h | 20 ++++- 3 files changed, 153 insertions(+), 1 deletion(-) create mode 100644 ft_struct/ft_rbtree_traversal.c diff --git a/Makefile b/Makefile index 4f27214..0b80c08 100644 --- a/Makefile +++ b/Makefile @@ -41,6 +41,7 @@ SRCstruct:= ft_stack_free.c \ ft_rbtree_insert.c \ ft_rbtree_search.c \ ft_rbtree_search_node.c \ + ft_rbtree_traversal.c \ ft_dict_access.c \ ft_dict_free.c \ ft_dict_init.c \ diff --git a/ft_struct/ft_rbtree_traversal.c b/ft_struct/ft_rbtree_traversal.c new file mode 100644 index 0000000..5d28c86 --- /dev/null +++ b/ft_struct/ft_rbtree_traversal.c @@ -0,0 +1,133 @@ +#include "ft_struct.h" + +t_ft_stat fill_stack_inorder(t_stack *stack, t_rbtree_node *node) +{ + t_ft_stat res; + + if (!node) + return (success); + res = fill_stack_inorder(stack, node->right); + if (res != success) + return (res); + ft_stack_push(stack, &node); + return (fill_stack_inorder(stack, node->left)); +} + +t_ft_stat fill_stack_inorder_reverse(t_stack *stack, t_rbtree_node *node) +{ + t_ft_stat res; + + if (!node) + return (success); + res = fill_stack_inorder_reverse(stack, node->left); + if (res != success) + return (res); + res = ft_stack_push(stack, &node); + if (res != success) + return (res); + return (fill_stack_inorder_reverse(stack, node->right)); +} + +t_ft_stat fill_stack_preorder(t_stack *stack, t_rbtree_node *node) +{ + t_ft_stat res; + + if (!node) + return (success); + res = fill_stack_preorder(stack, node->right); + if (res != success) + return (res); + res = fill_stack_preorder(stack, node->left); + if (res != success) + return (res); + return (ft_stack_push(stack, &node)); +} + +t_ft_stat fill_stack_preorder_reverse(t_stack *stack, t_rbtree_node *node) +{ + t_ft_stat res; + + if (!node) + return (success); + res = fill_stack_preorder_reverse(stack, node->left); + if (res != success) + return (res); + res = fill_stack_preorder_reverse(stack, node->right); + if (res != success) + return (res); + return (ft_stack_push(stack, &node)); +} + +t_ft_stat fill_stack_postorder(t_stack *stack, t_rbtree_node *node) +{ + t_ft_stat res; + + if (!node) + return (success); + res = ft_stack_push(stack, &node); + if (res != success) + return (res); + res = fill_stack_postorder(stack, node->right); + if (res != success) + return (res); + return (fill_stack_postorder(stack, node->left)); +} + +t_ft_stat fill_stack_postorder_reverse(t_stack *stack, t_rbtree_node *node) +{ + t_ft_stat res; + + if (!node) + return (success); + res = ft_stack_push(stack, &node); + if (res != success) + return (res); + res = fill_stack_postorder_reverse(stack, node->left); + if (res != success) + return (res); + return (fill_stack_postorder_reverse(stack, node->right)); +} + +t_ft_stat fill_stack(t_stack *stack, t_rbtree_node *node, t_traversal_order order) +{ + t_ft_stat res; + + if (order == inorder) + res = fill_stack_inorder(stack, node); + else if (order == reverse_inorder) + res = fill_stack_inorder_reverse(stack, node); + else if (order == preorder) + res = fill_stack_preorder(stack, node); + else if (order == reverse_preorder) + res = fill_stack_preorder_reverse(stack, node); + else if (order == postorder) + res = fill_stack_postorder(stack, node); + else if (order == reverse_postorder) + res = fill_stack_postorder_reverse(stack, node); + return (res); +} + +t_ft_stat ft_rbtree_traversal_init(t_rbtree_traversal *traversal, t_rbtree *tree, t_traversal_order order) +{ + t_ft_stat res; + + res = ft_stack_init(&traversal->stack, sizeof(t_rbtree_node *)); + if (res == success) + { + res = fill_stack(&traversal->stack, tree->root, order); + if (res != success) + ft_stack_free(&traversal->stack, NULL); + } + return (res); +} + +void *ft_rbtree_traverse(t_rbtree_traversal *traversal) +{ + t_rbtree_node **node; + + node = ft_stack_pop_forget(&traversal->stack); + if (node && *node) + return (&(*node)->data); + ft_stack_free(&traversal->stack, NULL); + return (NULL); +} diff --git a/inc/ft_struct.h b/inc/ft_struct.h index 0d7a5ad..39305cb 100644 --- a/inc/ft_struct.h +++ b/inc/ft_struct.h @@ -6,7 +6,7 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2024/06/20 16:59:43 by ljiriste #+# #+# */ -/* Updated: 2025/08/02 16:58:18 by ljiriste ### ########.fr */ +/* Updated: 2025/08/03 08:49:37 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -99,6 +99,24 @@ void ft_rbtree_rotate(t_rbtree_node *node); int ft_rbtree_draw(t_rbtree *tree, size_t min_height); +typedef enum e_traversal_order +{ + inorder, + preorder, + postorder, + reverse_inorder, + reverse_preorder, + reverse_postorder, +} t_traversal_order; + +typedef struct s_rbtree_traversal +{ + t_stack stack; +} t_rbtree_traversal; + +t_ft_stat ft_rbtree_traversal_init(t_rbtree_traversal *traversal, t_rbtree *tree, t_traversal_order order); +void *ft_rbtree_traverse(t_rbtree_traversal *traversal); + typedef struct s_dict { size_t key_size; -- 2.30.2