November 30, 2019
Amitraj
Tree (data Structure)
-> In linear data structure data is organized in sequential order and in non-linear data structure data is organized in Random order.
-> A tree is a very popular non-linear data structure used in a wide range of applications.
-> A tree data structure can be defined as follows:-
Tree is non-linear data structure which organizes data in hierarchical structure and this is a recursive definition.
-> A tree is a connected graph without any circuits.
Tree Terminology
1. Root:- This is the unique node in the tree in which further sub-trees were attached.
In the Above tree 8 is root node.
2. Degree of a node:- The total number of children of a node is known as Degree of a node.
In the Above tree Degree of 8 is two.
3=2
14=2
6=2
10=1
4=0
Because leaf node degree is always zero.
3. Leaf node:- leaf nodes are also known as terminal nodes. The nodes which have degree 0, are called the leaf node of the tree.
also known as external- node.
-> In the above tree leaf nodes are: 1,4,7,13
4. Edge:- The connecting link between two nodes is called an edge.
-> In a tree with a number of nodes, there are exactly (n-1) number of edges.
5. Parent:- The node which has one or more children is called as a parent node.
In a tree, a parent node can have any number of child nodes.
-> In the above tree, 8 is parent of 3 and 10.
6. Child:- The node which is a descendant of some node is called as a child node.
-> All the nodes except root node are child nodes.
-> In the above tree, 3 is children of 8.
7. Siblings:- The nodes which belong to the same parent are called as Siblings.
-> In the above tree, 4,7 is siblings.
8. Internal nodes:- The nodes in the tree which are other than leaf nodes and the root node, are called as internal nodes.
-> The node which has at least one child is called as an internal node.
->Internal nodes are also called as non-terminal nodes.
-> Every non-leaf node is an internal node.
9. Level:- In a tree, each step from top to bottom is called as level of a tree.
-> Root node is at level 0. The children of root node are at level 1 and so on.
-> In the above tree, 8 = level 0
3,10 = level 1
1,6,14 = level 2
4,7,13 = level 3
10. Height:- Total number of edges that lies on the longest path from any leaf node to a particular node is called as height of that node.
-> Height of a tree is the height of root node.
-> Height of all leaf nodes = 0
-> Above tree, height of root node 8 = 2
node 3 = 1
leaf node 4 = 0
11. Forest:- It is a set of disjoint Trees.
Properties-
The important properties of tree data structure are-
1. There is one and only one path between every pair of vertices in a tree.
2. A tree with n vertices has exactly (n-1) edges.
3. A graph is a tree if and only if it is minimally connected.
4. Any connected graph with n vertices and (n-1) edges is a tree.
-> In linear data structure data is organized in sequential order and in non-linear data structure data is organized in Random order.
-> A tree is a very popular non-linear data structure used in a wide range of applications.
-> A tree data structure can be defined as follows:-
Tree is non-linear data structure which organizes data in hierarchical structure and this is a recursive definition.
-> A tree is a connected graph without any circuits.
Tree Terminology
1. Root:- This is the unique node in the tree in which further sub-trees were attached.
In the Above tree 8 is root node.
2. Degree of a node:- The total number of children of a node is known as Degree of a node.
In the Above tree Degree of 8 is two.
3=2
14=2
6=2
10=1
4=0
Because leaf node degree is always zero.
3. Leaf node:- leaf nodes are also known as terminal nodes. The nodes which have degree 0, are called the leaf node of the tree.
also known as external- node.
-> In the above tree leaf nodes are: 1,4,7,13
4. Edge:- The connecting link between two nodes is called an edge.
-> In a tree with a number of nodes, there are exactly (n-1) number of edges.
5. Parent:- The node which has one or more children is called as a parent node.
In a tree, a parent node can have any number of child nodes.
-> In the above tree, 8 is parent of 3 and 10.
6. Child:- The node which is a descendant of some node is called as a child node.
-> All the nodes except root node are child nodes.
-> In the above tree, 3 is children of 8.
7. Siblings:- The nodes which belong to the same parent are called as Siblings.
-> In the above tree, 4,7 is siblings.
8. Internal nodes:- The nodes in the tree which are other than leaf nodes and the root node, are called as internal nodes.
-> The node which has at least one child is called as an internal node.
->Internal nodes are also called as non-terminal nodes.
-> Every non-leaf node is an internal node.
9. Level:- In a tree, each step from top to bottom is called as level of a tree.
-> Root node is at level 0. The children of root node are at level 1 and so on.
-> In the above tree, 8 = level 0
3,10 = level 1
1,6,14 = level 2
4,7,13 = level 3
10. Height:- Total number of edges that lies on the longest path from any leaf node to a particular node is called as height of that node.
-> Height of a tree is the height of root node.
-> Height of all leaf nodes = 0
-> Above tree, height of root node 8 = 2
node 3 = 1
leaf node 4 = 0
11. Forest:- It is a set of disjoint Trees.
Properties-
The important properties of tree data structure are-
1. There is one and only one path between every pair of vertices in a tree.
2. A tree with n vertices has exactly (n-1) edges.
3. A graph is a tree if and only if it is minimally connected.
4. Any connected graph with n vertices and (n-1) edges is a tree.
