Page 535 - Computer science 868 Class 12
P. 535

13.4 TREE
                 We have learnt about linear data structures like array, stack,                  A
                 queue, linked list where data is stored in a sequential manner.
                 Now we will know about a data structure where data is stored
                 in different levels similar to a family tree.                      B                        C
                 Tree  is a non-linear  data structure  containing  a collection
                 of interconnected nodes joined in a definite sequence. The
                 nodes are arranged in different levels depicting a hierarchical
                 relationship among itself.                                 D               E         F              G

                 13.4.1 Basic terminologies of a Tree
                 •  Node: Each element of a tree is called a node. A node contains a value and a link to its next node.
                 •  Root: The topmost node of a tree is called a root. The other nodes called sub nodes emerge from the root. There
                   can be only one root node of a tree.
                 •  Parent or Predecessor node: The node from where sub nodes emerge is called a parent node. Thus a node with one
                   or more child nodes is a parent node.
                 •  Child node: A node directly connected to another node as its immediate successor is called a child node. All nodes
                   except root node are child nodes.
                 •  Leaf node: A node which does not have any child node is called a leaf or external node.
                 •  Internal node or Branch node: All nodes excluding the root node and leaf nodes are called internal nodes.
                 •  Edge: The connecting link of a node to its successor node is called an edge. A tree with ‘N’ nodes will have ‘N-1’
                   edges.
                 •  Path: The sequence of edges joining one node with another node is called a path.
                 •  Size: Total number of nodes in a tree is called its size.
                 •  Sibling: Nodes belonging to same the parent node are called sibling.
                 •  Sub tree: The set of nodes present on either side of a parent node is called sub tree. The left side nodes from left
                   sub tree while the right side nodes form right sub tree.
                 •  Descendant: Any successor node on the path from the parent node to the child node is called descendant.
                 •  Ancestor: Any predecessor node on the path from the child node to the parent node is called ancestor.

                 Let us understand the terms with the following tree given as an example.
                 •  Each element of a tree is called a node. In this example, 8, 3, 10, 1, 6, 15,
                   13, 4, 7 are nodes.                                                                 8
                 •  The root node is 8.
                 •  The parent node of 6 is 3, 15 is 10 and so on.                            3                10
                 •  The child nodes of 6 are 4 and 7. Similarly, the child node of 15 is 13.
                 •  The leaf nodes of this tree are 1, 4, 7, and 13.
                 •  The internal nodes of the tree are 3, 10, 6, 15.                    1           6                15
                 •  The line joining 8 and 10  or 10 and 15 or 3 and 6 etc. is called an edge.

                 •  The path from 8 to 7 are the edges connecting 8 with 3, 3 with 6 and 6
                   with 7.                                                                     4         7     13
                 •  The size of the tree is 9.






                                                                                                                       533
                                                                                                       Data Structures  533
   530   531   532   533   534   535   536   537   538   539   540