We read data structure like an array, inked list, stack and queue in which all element are arranged in a sequential manner.
A tree is one of the data structures that represents hierarchical data.
defination :-
A tree is a non-linear data structure because it does not store in a sequential manner .It is a hierarchical structure as elements in tree are arranged in multiple levels. defined of simulate hierom collection of objects or entities known as noves that are linked together to represent or A tree is a non-linear data structure .
In tree data structure topmost node is called as root node. Each node contains some data& data can be of any type.
Each node contains some data or reference of other nodes that can be called chidren.
Some Basic terms of tree :-
link :- each node is labeled with some number. each array shown in fig is known as links between
two nodes.
Root :-
The root node is top most node in tree hierarchy. root node is one that doesnt have any parent. If node is directly linked to some other node,when it would be called a parent-child relationship.
Child node:-
If the node is a descendant of any node, then the node is known as a child node.
Parent:-
If the node contains any sub-node, then that node is said to be the parent of that sub-node.
Sibling:-
The nodes that have the same parent are known as siblings.
Leaf Node:-
The node of the tree, which doesn't have any child node, is called a leaf node. A leaf node is the bottom-most node of the tree. There can be any number of leaf nodes present in a general tree. Leaf nodes can also be called external nodes.
Internal nodes:-
A node has atleast one child node known as an internal
Ancestor node:-
An ancestor of a node is any predecessor node on a path from the root to that node. The root node doesn't have any ancestors. In the tree shown in the above image, nodes 1, 2, and 5 are the ancestors of node 10.
Descendant:-
The immediate successor of the given node is known as a descendant of a node. In the above figure, 10 is the descendant of node 5.
Properties of Tree data structure
Recursive data structure:-
The tree is also known as a recursive data structure. A tree can be defined as recursively because the distinguished node in a tree data structure is known as a root node. The root node of the tree contains a link to all the roots of its subtrees. The left subtree is shown in the yellow color in the below figure, and the right subtree is shown in the red color. The left subtree can be further split into subtrees shown in three different colors. Recursion means reducing something in a self-similar manner. So, this recursive property of the tree data structure is implemented in various applications.
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.
