Read or watch :
-
Binary tree
(
note the first line:
Not to be confused with B-tree.
) - Data Structure and Algorithms - Tree
- Tree Traversal
- Binary Search Tree
- Data structures: Binary Tree
At the end of this project, you are expected to be able to explain to anyone , without the help of Google :
- What is a binary tree
- What is the difference between a binary tree and a Binary Search Tree
- What is the possible gain in terms of time complexity compared to linked lists
- What are the depth, the height, the size of a binary tree
- What are the different traversal methods to go through a binary tree
- What is a complete, a full, a perfect, a balanced binary tree
-
Allowed editors:
vi
,vim
,emacs
- All your files will be compiled on Ubuntu 20.04 LTS using gcc, using the options -Wall -Werror -Wextra -pedantic -std=gnu89
- All your files should end with a new line
-
A
README.md
file, at the root of the folder of the project, is mandatory -
Your code should use the
Betty
style. It will be checked using betty-style.pl and betty-doc.pl - You are not allowed to use global variables
- No more than 5 functions per file
- You are allowed to use the standard library
-
In the following examples, the
main.c
files are shown as examples. You can use them to test your functions, but you donβt have to push them to your repo (if you do we wonβt take them into account). We will use our ownmain.c
files at compilation. Ourmain.c
files might be different from the one shown in the examples -
The prototypes of all your functions should be included in your header file called
binary_trees.h
- Donβt forget to push your header file
- All your header files should be include guarded
There should be one project repository per group. If you clone/fork/whatever a project repository with the same name before the second deadline, you risk a 0% score.
Please use the following data structures and types for binary trees. Donβt forget to include them in your header file.
/** * 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;
typedef struct binary_tree_s bst_t;
typedef struct binary_tree_s avl_t;
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.
To match the examples in the tasks, you are given this function
This function is used only for visualization purposes. You donβt have to push it to your repo. It may not be used during the correction
### Project BreakDownWrite 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 - 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 - 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
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
ifnode
is a leaf, and0
otherwise - If
node
isNULL
, return0
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
ifnode
is a root, and0
otherwise - If
node
isNULL
, return0
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.
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.
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.
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 of - If
tree
isNULL
, your function must return0
Write a function that measures the depth of a node in a binary tree
- Prototype:
size_t binary_tree_depth(const binary_tree_t *node);
- Where
tree
is a pointer to the node to measure the depth of - If
node
isNULL
, your function must return0
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 of
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 leaves in - 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 nodes in - 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 of - If
tree
isNULL
, return0
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
isNULL
, your function must return0
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
isNULL
, your function must return0
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 of - Your function must return a pointer to the sibling node
- If
node
has no sibling, returnNULL
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 of - Your function must return a pointer to the uncle node
- If
node
has no uncle, returnNULL
Write a function that finds the lowest common ancestor of two nodes
- Prototype:
binary_tree_t *binary_trees_ancestor(const binary_tree_t *first, const binary_tree_t *second);
- Where
first
is a pointer to the first node - And
second
is a pointer to the second node - Your function must return a pointer to the lowest common ancestor node of the two given nodes
- If no common ancestor was found, your function must return
NULL
Write a function that goes through a binary tree using level-order traversal
- Prototype:
void binary_tree_levelorder(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.
Write a function that checks if a binary tree is complete
- Prototype:
int binary_tree_is_complete(const binary_tree_t *tree);
- Where
tree
is a pointer to the root node of the tree to check - If
tree
isNULL
, your function must return0
Write a function that performs a left-rotation on a binary tree
- Prototype:
binary_tree_t *binary_tree_rotate_left(binary_tree_t *tree);
- Where
tree
is a pointer to the root node of the tree to rotate - Your function must return a pointer to the new root node of the tree once rotated
Write a function that performs a right-rotation on a binary tree
- Prototype:
binary_tree_t *binary_tree_rotate_right(binary_tree_t *tree);
- Where
tree
is a pointer to the root node of the tree to rotate - Your function must return a pointer to the new root node of the tree once rotated