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).
- 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
self.left = None
self.right = None
self.data = data
public class Node
Node left, right;
public Node(int val)
data = val;
left = right = null;
struct Node *left;
struct Node *right;