/**
- struct binary_tree_s - Binary tree node
- @n: Integer stored in the node
- @parent: Pointer to the parent node
- @left: Pointer to the left child node
- @right: Pointer to the right child node */ struct binary_tree_s { int n; struct binary_tree_s *parent; struct binary_tree_s *left; struct binary_tree_s *right; };
typedef struct binary_tree_s binary_tree_t;
Binary Search Tree typedef struct binary_tree_s bst_t;
AVL Tree typedef struct binary_tree_s avl_t;
Max Binary Heap typedef struct binary_tree_s heap_t;
Note: For tasks 0 to 23 (included), you have to deal with simple binary trees. They are not BSTs, thus they don’t follow any kind of rule.
Write a function that creates a binary tree node
Prototype: binary_tree_t *binary_tree_node(binary_tree_t *parent, int value); Where parent is a pointer to the parent node of the node to create And value is the value to put in the new node When created, a node does not have any child Your function must return a pointer to the new node, or NULL on failure
Write a function that inserts a node as the left-child of another node
Prototype: binary_tree_t *binary_tree_insert_left(binary_tree_t *parent, int value); Where parent is a pointer to the node to insert the left-child in And value is the value to store in the new node Your function must return a pointer to the created node, or NULL on failure or if parent is NULL If parent already has a left-child, the new node must take its place, and the old left-child must be set as the left-child of the new node.}
Write a function that inserts a node as the right-child of another node
Prototype: binary_tree_t *binary_tree_insert_right(binary_tree_t *parent, int value); Where parent is a pointer to the node to insert the right-child in And value is the value to store in the new node Your function must return a pointer to the created node, or NULL on failure or if parent is NULL If parent already has a right-child, the new node must take its place, and the old right-child must be set as the right-child of the new node.
Write a function that deletes an entire binary tree
Prototype: void binary_tree_delete(binary_tree_t *tree); Where tree is a pointer to the root node of the tree to delete If tree is NULL, do nothing
Write a function that checks if a node is a leaf
Prototype: int binary_tree_is_leaf(const binary_tree_t *node); Where node is a pointer to the node to check Your function must return 1 if node is a leaf, otherwise 0 If node is NULL, return 0
Write a function that checks if a given node is a root
Prototype: int binary_tree_is_root(const binary_tree_t *node); Where node is a pointer to the node to check Your function must return 1 if node is a root, otherwise 0 If node is NULL, return 0
Write a function that goes through a binary tree using pre-order traversal
Prototype: void binary_tree_preorder(const binary_tree_t *tree, void (*func)(int)); Where tree is a pointer to the root node of the tree to traverse And func is a pointer to a function to call for each node. The value in the node must be passed as a parameter to this function. If tree or func is NULL, do nothing
Write a function that goes through a binary tree using in-order traversal
Prototype: void binary_tree_inorder(const binary_tree_t *tree, void (*func)(int)); Where tree is a pointer to the root node of the tree to traverse And func is a pointer to a function to call for each node. The value in the node must be passed as a parameter to this function. If tree or func is NULL, do nothing
Write a function that goes through a binary tree using post-order traversal
Prototype: void binary_tree_postorder(const binary_tree_t *tree, void (*func)(int)); Where tree is a pointer to the root node of the tree to traverse And func is a pointer to a function to call for each node. The value in the node must be passed as a parameter to this function. If tree or func is NULL, do nothing
Write a function that measures the height of a binary tree
Prototype: size_t binary_tree_height(const binary_tree_t *tree); Where tree is a pointer to the root node of the tree to measure the height. If tree is NULL, your function must return 0
Write a function that measures the depth of a node in a binary tree
Prototype: size_t binary_tree_depth(const binary_tree_t *tree); Where tree is a pointer to the node to measure the depth If tree is NULL, your function must return 0
Write a function that measures the size of a binary tree
Prototype: size_t binary_tree_size(const binary_tree_t *tree); Where tree is a pointer to the root node of the tree to measure the size If tree is NULL, the function must return 0
Write a function that counts the leaves in a binary tree
Prototype: size_t binary_tree_leaves(const binary_tree_t *tree); Where tree is a pointer to the root node of the tree to count the number of leaves If tree is NULL, the function must return 0 A NULL pointer is not a leaf
Write a function that counts the nodes with at least 1 child in a binary tree
Prototype: size_t binary_tree_nodes(const binary_tree_t *tree); Where tree is a pointer to the root node of the tree to count the number of nodes If tree is NULL, the function must return 0 A NULL pointer is not a node
Write a function that measures the balance factor of a binary tree
Prototype: int binary_tree_balance(const binary_tree_t *tree); Where tree is a pointer to the root node of the tree to measure the balance factor If tree is NULL, return 0
Write a function that checks if a binary tree is full
Prototype: int binary_tree_is_full(const binary_tree_t *tree); Where tree is a pointer to the root node of the tree to check If tree is NULL, your function must return 0
Write a function that checks if a binary tree is perfect
Prototype: int binary_tree_is_perfect(const binary_tree_t *tree); Where tree is a pointer to the root node of the tree to check If tree is NULL, your function must return 0
Write a function that finds the sibling of a node
Prototype: binary_tree_t *binary_tree_sibling(binary_tree_t *node); Where node is a pointer to the node to find the sibling Your function must return a pointer to the sibling node If node is NULL or the parent is NULL, return NULL If node has no sibling, return NULL
Write a function that finds the uncle of a node
Prototype: binary_tree_t *binary_tree_uncle(binary_tree_t *node); Where node is a pointer to the node to find the uncle Your function must return a pointer to the uncle node If node is NULL, return NULL If node has no uncle, return NULL
main y salida
- Delete mandatory Write a function that deletes an entire binary tree
Prototype: void binary_tree_delete(binary_tree_t *tree); Where tree is a pointer to the root node of the tree to delete If tree is NULL, do nothing alex@/tmp/binary_trees$ cat 3-main.c #include <stdlib.h> #include <stdio.h> #include "binary_trees.h"
/**
-
main - Entry point
-
Return: Always 0 (Success) */ int main(void) { binary_tree_t *root;
root = binary_tree_node(NULL, 98); root->left = binary_tree_node(root, 12); root->right = binary_tree_node(root, 402); binary_tree_insert_right(root->left, 54); binary_tree_insert_right(root, 128); binary_tree_print(root); binary_tree_delete(root); return (0); } alex@/tmp/binary_trees$ gcc -Wall -Wextra -Werror -pedantic binary_tree_print.c 3-main.c 3-binary_tree_delete.c 0-binary_tree_node.c 2-binary_tree_insert_right.c -o 3-del alex@/tmp/binary_trees$ valgrind ./3-del ==13264== Memcheck, a memory error detector ==13264== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al. ==13264== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info ==13264== Command: ./3-del ==13264== .-------(098)--. (012)--. (128)--. (054) (402) ==13264== ==13264== HEAP SUMMARY: ==13264== in use at exit: 0 bytes in 0 blocks ==13264== total heap usage: 9 allocs, 9 frees, 949 bytes allocated ==13264== ==13264== All heap blocks were freed -- no leaks are possible ==13264== ==13264== For counts of detected and suppressed errors, rerun with: -v ==13264== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) alex@/tmp/binary_trees$
main y salida task 17
- Sibling mandatory Write a function that finds the sibling of a node
Prototype: binary_tree_t *binary_tree_sibling(binary_tree_t *node); Where node is a pointer to the node to find the sibling Your function must return a pointer to the sibling node If node is NULL or the parent is NULL, return NULL If node has no sibling, return NULL alex@/tmp/binary_trees$ cat 17-main.c #include <stdlib.h> #include <stdio.h> #include "binary_trees.h"
/**
-
main - Entry point
-
Return: Always 0 (Success) */ int main(void) { binary_tree_t *root; binary_tree_t *sibling;
root = binary_tree_node(NULL, 98); root->left = binary_tree_node(root, 12); root->right = binary_tree_node(root, 128); root->left->right = binary_tree_node(root->left, 54); root->right->right = binary_tree_node(root->right, 402); root->left->left = binary_tree_node(root->left, 10); root->right->left = binary_tree_node(root->right, 110); root->right->right->left = binary_tree_node(root->right->right, 200); root->right->right->right = binary_tree_node(root->right->right, 512);
binary_tree_print(root); sibling = binary_tree_sibling(root->left); printf("Sibling of %d: %d\n", root->left->n, sibling->n); sibling = binary_tree_sibling(root->right->left); printf("Sibling of %d: %d\n", root->right->left->n, sibling->n); sibling = binary_tree_sibling(root->left->right); printf("Sibling of %d: %d\n", root->left->right->n, sibling->n); sibling = binary_tree_sibling(root); printf("Sibling of %d: %p\n", root->n, (void *)sibling); return (0); } alex@/tmp/binary_trees$ gcc -Wall -Wextra -Werror -pedantic binary_tree_print.c 17-main.c 17-binary_tree_sibling.c 0-binary_tree_node.c -o 17-sibling alex@/tmp/binary_trees$ ./17-sibling .-------(098)-------. .--(012)--. .--(128)-------. (010) (054) (110) .--(402)--. (200) (512) Sibling of 12: 128 Sibling of 110: 402 Sibling of 54: 10 Sibling of 98: (nil) alex@/tmp/binary_trees$