data_structures
rbt_keys.c
Go to the documentation of this file.
1 /* ************************************************************************** */
3 /* */
4 /* ::: :::::::: */
5 /* rbt_keys.c :+: :+: :+: */
6 /* +:+ +:+ +:+ */
7 /* By: unite <marvin@42.fr> +#+ +:+ +#+ */
8 /* +#+#+#+#+#+ +#+ */
9 /* Created: 2020/07/18 21:08:44 by unite #+# #+# */
10 /* Updated: 2020/09/07 22:10:03 by unite ### ########.fr */
11 /* */
12 /* ************************************************************************** */
13 
14 #include "rbt.h"
15 
16 static void rbt_inorder_recur(const t_rbt *rbt, const t_rbt_node *node,
17  t_queue *queue)
18 {
19  if (node == NULL)
20  return ;
21  rbt_inorder_recur(rbt, node->left, queue);
22  queue_enqueue(queue, node->key);
23  rbt_inorder_recur(rbt, node->right, queue);
24 }
25 
26 t_queue *rbt_keys(const t_rbt *rbt)
27 {
28  t_queue *queue;
29 
30  queue = queue_new(rbt->key_type);
31  rbt_inorder_recur(rbt, rbt->root, queue);
32  return (queue);
33 }
s_rbt
A left-leaning red-black binary search tree.
Definition: rbt.h:72
rbt_keys
t_queue * rbt_keys(const t_rbt *rbt)
Returns a queue with all the keys in the tree, sorted in the ascending order.
Definition: rbt_keys.c:26
s_rbt_node::right
struct s_rbt_node * right
The right child.
Definition: rbt.h:56
s_list
Doubly-linked list of generic items.
Definition: list.h:54
queue_new
t_queue * queue_new(const t_type *type)
Allocates memory and initializes an empty queue.
Definition: queue_new.c:16
s_rbt_node::left
struct s_rbt_node * left
The left child.
Definition: rbt.h:55
s_rbt_node::key
void * key
The key.
Definition: rbt.h:53
s_rbt::key_type
const t_type * key_type
The type of keys in the tree.
Definition: rbt.h:75
queue_enqueue
void queue_enqueue(t_queue *queue, const void *data)
Copies the item and adds the copy to the queue.
Definition: queue_enqueue.c:16
rbt.h
s_rbt_node
A node in a red-black tree.
Definition: rbt.h:51
s_rbt::root
t_rbt_node * root
The root of the tree.
Definition: rbt.h:74