- A tree is a widely used data structure that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as nodes. It is composed of nodes connected by edges.
- Each node contains a value and a list of references to its children nodes.
Some key terms associated with trees are:
- Node: Each element of a tree that contains a value and references to its children nodes.
- Root: The topmost node of the tree, serving as the starting point for accessing other nodes.
- Edge: The link between a parent node and its child node.
- Parent Node: A node that has one or more child nodes connected to it.
- Child Node: A node directly connected to another node when moving away from the root.
- Leaf Node: A node with no children in the tree.
- Subtree: A tree structure consisting of a node and its descendants.
- Height of a Tree: The length of the longest path from the root to a leaf.
- Depth of a Node: The length of the path from the root to that node.
- Binary Tree: A type of tree in which each node has at most two children, known as the left child and the right child.
Properties of Tree Data Structure
- Number of edges: If there are n nodes, then there would n-1 edges. Each arrow in the structure represents the link or path. Each node, except the root node, will have atleast one incoming link known as an edge. There would be one link for the parent-child relationship.
- Depth of node x: The depth of node x can be defined as the length of the path from the root to the node x. One edge contributes one-unit length in the path. So, the depth of node x can also be defined as the number of edges between the root node and the node x. The root node has 0 depth.
- Height of node x: The height of node x can be defined as the longest path from the node x to the leaf node.
Applications Of Trees
- File Systems: Trees are used to represent the hierarchical structure of file systems, with directories and subdirectories organized in a tree-like structure.
- Database Systems: Trees are employed in indexing structures like B-trees and B+ trees for efficient storage and retrieval of data in database systems.
- Compiler Design: Abstract Syntax Trees (ASTs) are used in compiler design to represent the structure of source code, enabling efficient parsing and analysis.
- Network Routing Algorithms: Trees are utilized in network routing algorithms to determine the optimal path for data transmission in computer networks.
- Artificial Intelligence and Decision Trees: Decision trees are used in machine learning and artificial intelligence for classification and predictive modeling.
Types Of Tree Data Structure
The following are the types of a tree data structure:
General tree:A general tree, also known as an unordered tree or a non-linear tree, is a tree data structure in which each node can have any number of child nodes. Unlike a binary tree, where each node has at most two children, a general tree allows for a variable and arbitrary number of children per node.
The defining characteristic of a general tree is that it has a hierarchical structure, with a root node and a collection of nodes connected by edges, where each node can have multiple child nodes.
Binary tree:A binary tree is a fundamental tree data structure in which each node has at most two children, referred to as the left child and the right child. The binary tree has the following properties:
- Each node can have at most two children, which are referred to as the left child and the right child.
- The left child node is typically less than the parent node, while the right child node is greater than the parent node, depending on the specific implementation of the binary tree.
The left child node is typically less than the parent node, while the right child node is greater than the parent node, depending on the specific implementation of the binary tree.
- The left subtree of a node contains only nodes with keys/values less than the node’s key/value.
- The right subtree of a node contains only nodes with keys/values greater than the node’s key/value.
- The left and right subtrees must also be binary search trees.
struct node
{
int data;
struct node *left;
struct node *right;
}
