TREES in Data Structures

Trees

The linear data structures are generally not suitable for the representation of hierarchical data in hierarchal data we have an ancestor ,descendent, superior-subordinate, whole part, or similar relationship among the data elements. Definition : A tree in data structures is a finite set of one or more nodes such that : A distinguish node, called the root. The remaining nodes are partitioned into n>=0 disjoint steps called sub trees of the root Note# that the hierarchical relationship between various data items can be represented by using trees.

Example

The inheritance relationship between classes in a form a tree. In most operating systems, files are organized hierarchy calls into nested directories which are presented to the use in the form of a tree. A structured document, such as a book, ie hierarchy organized as a tree where internal nodes are chapters, sections and  sub sections, and where external nodes. 

Basic terminology

A node stands for the item of information plus the branches to other items, Trees has 13 nodes. The number of sub trees of a node is called its degree. The degree of A is 3, of c is 1 and F is nodes that have degree 0 are called leaf or terminal nodes. The other nodes are called non terminal, nodes. E,F,K,H,I,L,M id set of leaf nodes. A node is external it has no children and it is internal if it has one or more children , external nodes are also known as leafes. The roots of the sub trees of  a node are called the children of that node. In the following above figure ‘A’ is called the parent of B,C and D. The children of D are H,I and J. The parent of D is A. An ancestor of a node is either the node itself an ancestor of the parent of the node. Conversely, we say that a node v is a descendent of a node U if U is an ancestor of V.   Children of the same parent are said to be siblings. H,I and J are siblings. The degree of a tree is the maximum degree of the nodes in the tree. The tree of figure has degree 3. Another commonly used tree term is leafs. By definition the tree root is at level 1; its children (if any) are at level2; their children (if any) are at level 3 and so on. The height or depth of tree is defined to the maximum level of any node in the tree.