The tree data structure can be formed by using pointers to create the nodes dynamically. As shown below, the memory tree can be expressed as follows:
- The memory representation of the tree data structure is shown in the diagram above.
- The node in the above structure has three fields.
- The data is stored in the second field, while the left child's address is stored in the first field and the right child's address is stored in the third field.
A node's structure can be defined as follows in programming:
struct node
{
int data;
struct node *left;
struct node *right;
}
- Because binary trees can only have two children, and generic trees can have more than two, the above structure can only be defined for binary trees.
- In comparison to the binary tree, the structure of the node in generic trees would be different.
Applications of trees
- Trees are used to store data in a hierarchical form that is naturally hierarchical. Consider the file system. The file system, files, and folders are saved on the disc drive in the form of naturally hierarchical data in the form of trees.
- Organize Data: It is used to arrange data in order to make insertion, deletion, and searching more efficient. A binary tree, for example, has a logN time for searching an element.
- Trie: The dictionary is stored in a specific type of tree called a trie. It's a quick and easy approach to do dynamic spell checking.
- Heap: Heap is a tree data structure that is also built using arrays. Priority queues are implemented using it.
- B-Tree and B+Tree: B-Tree and B+Tree are tree data structures that are used in databases to implement indexing.
- Routing table: In routers, the tree data structure is also used to store data in routing tables.
Types of Tree data structure
Generic tree:
- The generic tree is one of the different forms of tree data structures. A node in the general tree can have either 0 or maximum n nodes.
- The degree of the node is not limited in any way (the number of nodes that a node can contain).
- A root node is the node at the very top of a generic tree. Subtrees are the offspring of the parent node.
- A generic tree can have an infinite number of subtrees. The subtrees in the general tree are unordered because the nodes in the subtrees cannot be ordered.
- A downward edge runs through every non-empty tree, and these edges are connected to the nodes known as child nodes.
- Level 0 is assigned to the root node. Sibling nodes are those that have the same parent.
Binary tree:
- The name binary implies two numbers, namely 0 and 1. Each node in a binary tree can have a maximum of two child nodes.
- The term "utmost" refers to whether a node has zero, one, or two nodes.
Binary Search Tree:
- A binary search tree is a non-linear data structure in which one node is connected to a n number of other nodes.
- It's a data structure with nodes. In a binary search tree, a node can be represented by three fields: data portion, left-child, and right-child.
- In a binary search tree, a node can be connected to the utmost two child nodes, resulting in the node having two pointers (left child and right child pointer).
- Every node in the left subtree must have a value less than the root node's value, and every node in the right subtree must have a value greater than the root node's value.
