Introduction to trees

Introduction to trees

A tree is an acyclic graph, a tree of which each vertex has at most 2 children is called a binary tree.
Since each vertex of a binary tree can only have 2 children, we generally name them left child (under left tree) and right child (under right tree).

Unlike tables, linked lists, stacks, and queues, which are linear data structures, trees are hierarchical data structures.

The highest node is called the root of the tree (root). Items that are directly under an item are called its children. The element directly above something is called its parent. For example, "D" is a child of "B" and "B" is the parent of "D".
Finally, the elements without children are called leaves (D, E, F, G).

Why trees?

  •   One reason for using trees may be because you want to store information that naturally forms a hierarchy. For example, the file system on a computer
  •   Trees (with a certain order, for example Binary search tree) offer (access / search) faster than the linked list and slower than tables.
  •   Trees provide faster insertion / deletion than tables and slower than unordered linked lists.
  •   Like linked lists and unlike arrays, trees have no upper limit in terms of the number of nodes, since the nodes are linked using pointers.

Main applications of trees

  •   Manipulate hierarchical data.
  •   Make information searching easier
  •   Manipulate lists of sorted data.
  •   As a workflow for composing digital images for visual effects.
  •   Form of decision-making in several stages
  •   Algorithms for routers

Binary Tree Representation

A tree is represented by a pointer to the highest node in the tree. If the tree is empty, the value of the root is zero.

A node contains the following elements:

  •   Data (information stored in the tree)
  •   Left child pointer
  •   Right child pointer
                class Node: 
                    def __init__(self,val): 
                        self.left = None
                        self.right = None
               = data
                    public class Node 
                        int data; 
                        Node left, right; 
                        public Node(int val) 
                            data = val; 
                            left = right = null; 
                    struct Node  
                      int data; 
                      struct Node *left; 
                      struct Node *right; 

Share this course with your friends :

This course is written by M. ESSADDOUKI Mostafa

Many people realize their hearts desires late in life. Continue learning, never stop striving and keep your curiosity sharp, and you will never become too old to appreciate life.

0 Comment(s)

To leave a comment you must have an account Sign up, or Sign in