Data Strucrures
In computer science, a tree is a widely used data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.
A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.
Alternatively, a tree can be defined abstractly as a whole (globally) as an ordered tree, with a value assigned to each node. Both these perspectives are useful: while a tree can be analyzed mathematically as a whole, when actually represented as a data structure it is usually represented and worked with separately by node (rather than as a set of nodes and an adjacency list of edges between nodes, as one may represent a digraph, for instance). For example, looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general as a data structure a given node only contains the list of its children, but does not contain a reference to its parent (if any).
Followings are the terminilogies widely used in tree
1. Tree
A tree is a DS with set of one or more nodes. There is a special node called root and remaining nodes are partitioned into disjoint groups T1,T2….Tn. Where Ti- sub tree
2. Node
Each item in a tree called Node. In above figure, all the number are the nodes.
3. Degree of a Node
Number of sub trees of a node in a given tree. In above figure, node 1 have degree 3, node 2 have degree 2, node 5 have degree 1 and node 7 have degree 3.
4. Degree of a Tree
Maximum degree of node in a given tree. In above figure, node 1 and 7 are the nodes which have maximux degree i.e. 3, therefore, degree of tree is 3
5. Leaf Node
A node with degree zero. Nodes 3,4,6,8,9, and 10 are the leaf nodes
6. Interior Nodes
Any Node except root node whose degree not zero. In above figure, nodes 2,5,7 are the interior nodes
7. Children and Parents
Root of sub tree is parent & sub tree is its children. In above figure, node 1 is the root node, node 2 is the 2 and 4, also node 2 and 4 are the childrens of node 2
8. Siblings
Children's of the same parents. In above figure, nodes 2,5,7 are the siblings of node 1. Also 2,4 are the siblings of 2 and so on.
9. Tree Levels
Root is at level 0. If node is at level ‘n’, then its children’s are at level n+1. Node 1 is at Level-0, node 2,5,7 are at Level-1 and node 3,4,6,8,9,10 are at Level-2.
10. Height of a Tree
Maximum level of any node in a given tree. Level of above tree is 2, therefore, Height of tree is 2.