Git Product home page Git Product logo

binary_trees's Introduction

0x1D. C - BINARY TREES

C Group project Algorithm Data structure

Resources

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


※※※※※※※※※※※※


Learning Objectives

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


※※※※※※※※※※※※


Requirements

General

  • 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 own main.c files at compilation. Our main.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

GitHub

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.

More Info

Data structures

Please use the following data structures and types for binary trees. Don’t forget to include them in your header file.

Basic Binary Tree

/**
 * 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.

Print function

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

Tasks

0. New node

mandatory

File: 0-binary_tree_node.c

1. Insert left

mandatory

File: 1-binary_tree_insert_left.c

2. Insert right

mandatory

File: 2-binary_tree_insert_right.c

3. Delete

mandatory

File: 3-binary_tree_delete.c

4. Is leaf

mandatory

File: 4-binary_tree_is_leaf.c

5. Is root

mandatory

File: 5-binary_tree_is_root.c

6. Pre-order traversal

mandatory

File: 6-binary_tree_preorder.c

7. In-order traversal

mandatory

File: 7-binary_tree_inorder.c

8. Post-order traversal

mandatory

File: 8-binary_tree_postorder.c

9. Height

mandatory

File: 9-binary_tree_height.c

10. Depth

mandatory

File: 10-binary_tree_depth.c

11. Size

mandatory

File: 11-binary_tree_size.c

12. Leaves

mandatory

File: 12-binary_tree_leaves.c

13. Nodes

mandatory

File: 13-binary_tree_nodes.c

14. Balance factor

mandatory

File: 14-binary_tree_balance.c

15. Is full

mandatory

File: 15-binary_tree_is_full.c

16. Is perfect

mandatory

File: 16-binary_tree_is_perfect.c

17. Sibling

mandatory

File: 17-binary_tree_sibling.c

18. Uncle

mandatory

File: 18-binary_tree_uncle.c

19. Lowest common ancestor

#advanced

File: 100-binary_trees_ancestor.c

20. Level-order traversal

#advanced

File: 101-binary_tree_levelorder.c

21. Is complete

#advanced

File: 102-binary_tree_is_complete.c

22. Rotate left

#advanced

File: 103-binary_tree_rotate_left.c

23. Rotate right

#advanced

File: 104-binary_tree_rotate_right.c

24. Is BST

#advanced

File: 110-binary_tree_is_bst.c

25. BST - Insert

#advanced

File: 111-bst_insert.c, 0-binary_tree_node.c

26. BST - Array to BST

#advanced

File: 112-array_to_bst.c, 111-bst_insert.c, 0-binary_tree_node.c

27. BST - Search

#advanced

File: 113-bst_search.c

28. BST - Remove

#advanced

File: 114-bst_remove.c

29. Big O #BST

#advanced

File: 115-O

30. Is AVL

#advanced

File: 120-binary_tree_is_avl.c

31. AVL - Insert

#advanced

File: 121-avl_insert.c, 14-binary_tree_balance.c, 103-binary_tree_rotate_left.c, 104-binary_tree_rotate_right.c, 0-binary_tree_node.c

32. AVL - Array to AVL

#advanced

File: 122-array_to_avl.c, 121-avl_insert.c, 0-binary_tree_node.c, 103-binary_tree_rotate_left.c, 104-binary_tree_rotate_right.c, 14-binary_tree_balance.c

33. AVL - Remove

#advanced

File: 123-avl_remove.c, 14-binary_tree_balance.c, 103-binary_tree_rotate_left.c, 104-binary_tree_rotate_right.c

34. AVL - From sorted array

#advanced

File: 124-sorted_array_to_avl.c, 0-binary_tree_node.c

35. Big O #AVL Tree

#advanced

File: 125-O

36. Is Binary heap

#advanced

File: 130-binary_tree_is_heap.c

37. Heap - Insert

#advanced

File: 131-heap_insert.c, 0-binary_tree_node.c

38. Heap - Array to Binary Heap

#advanced

File: 132-array_to_heap.c, 131-heap_insert.c, 0-binary_tree_node.c

39. Heap - Extract

#advanced

File: 133-heap_extract.c

40. Heap - Sort

#advanced

File: 134-heap_to_sorted_array.c, 133-heap_extract.c

41. Big O #Binary Heap

#advanced

File: 135-O

binary_trees's People

Contributors

codenvibes avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.