The tree is an important data structure in software development. There are numerous applications of trees. In this post, we take you through the basics of this Data Structure. This post takes you through all that you need to know about trees.
What is the Tree Data Structure
A Tree represents data in hierarchical order. Each data point in the tree is called a node. The topmost node is called the root node from where the tree begins.
Important Terms:
Nodes: Each data point in the tree
Root Node: First or topmost node in the tree
Child Node: A subsequent node. Every node apart from the root node is a child node.
Leaf Node: A node which does not have subsequent child nodes. The tree ends here.
Parent Node: A node which has subsequent child nodes. All nodes except leaf nodes are parent nodes.
Height of Tree: The maximum number of nodes from root node to leaf node.
Application of Trees
The primary application of tree data structure is in applications with hierarchical data.
- File Systems: As you must have observed, files are stored in Operating Systems hierarchies where files come under directories or folders. So, the tree data structure can naturally store or access file structure.
- Database Index: Database Indexes are created on database tables to fetch information from the table quickly. Tree Data structure is used here to create an index on tables.
- Markup Languages like XML and HTML: XML & HTML are markup languages in which data is stored between tags. These tags are also present in a hierarchy of Parent-child relationships. Thus, the tree is a natural choice to represent markup languages.
- Compilers: Compilers use tree data structures to represent and parse program syntax.
Types of Trees
Based on the number of child nodes:
- Binary Tree – up to 2 child nodes
- Ternary Tree – up to 3 child nodes
- N-ary Tree – up to N child nodes (more than 3)
Add Comment