ralexrivero / binary_trees Goto Github PK

View Code? Open in Web Editor NEW

Binary trees are data structures in which each node has at most two children. The algorithms concerning to the different traversal methods to go through a binary tree and how to generate a perfect balanced one.

License: GNU General Public License v3.0

C 98.12% Makefile 1.88%

binary_trees's Introduction

0x1D. C - Binary trees

          000 00  0 00
      00 0\/0\|0 ()|/ @, 00
      0\/(/0/0||/0 /_/)_0/_0
   0() 0\/0|()|/0\/ '%" 0 ()
  0_\_00_\ |0 |00/0__%_/_0 00
00   00 0 0| 0| /0 0 % ()0 /00
 ()0_---()0\0\|00-00--%---()~
     00     \|||
             |||
             |||
             |||
       , -=-~  .-^- _
              `

Learning Objectives

General

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

Environment

Language: C
OS: Ubuntu 20.04 LTS
Editor: VIM 8.1.2269
Compiler: gcc 9.3.0
- compilation flags: -Wall -Werror -Wextra -pedantic -std=gnu89
Style guidelines: Betty style

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;