Page 540 - Computer science 868 Class 12
P. 540

Example 5: Answer the following from the given diagram of a Binary Tree.                        [ISC 2013]
                   (i) Preorder Transversal of the tree                                                A
                  (ii) Children of node E
                  (iii) The left sub tree of node D
                  (iv) Height of the tree when the root of the tree is at level 0                I           B

               Ans. (i) Pre Order Traversal: A, I, B, C, D, E, G, H, F                                    C     D
                  (ii) Children of node E are G, H
                   (iii) Left sub tree of node D is E, G, H                                                  E     F
                   (iv) Height of the tree taking root at level 0 is 4
                                                                                                          G     H


                             Let’s Revisit

                    ♦ Data structure  is a systematic way of  storing and organizing data in a specialized format , and its relationship with all
                   associated members.
                    ♦ In Linear data structure data elements are arranged contiguously one after another. The adjacent elements are attached with
                   one another and is traversed linearly. Example array, stack, queue etc.
                    ♦ In Non linear data structure the data elements are arranged in a hierarchical order representing parent child relationship.
                   Example tree and graph
                    ♦ In Static data structure the size and format  is  fixed during declaration.
                    ♦ In Dynamic data structure we declare the element with an  initial size, which can be changed during runtime as per requirement.
                    ♦ A stack is a linear data structure which stores data in LIFO (Last In First Out) order. A stack has only one end , top. Insertion and
                   deletion of data takes place from the top only.
                    ♦ A queue is a linear data structure which works on FIFO principle. It has two ends namely the front and the rear. Insertion in a
                   queue takes place from the rear end and deletion from the front end.
                    ♦ A Double Ended Queue or Dequeue is a modified Queue where insertion and deletion are performed from both rear and front end
                    ♦ Circular queue is a special type of queue where the front and rear ends are connected to form a circular structure. Circular
                   queue follows the queue principle of FIFO
                    ♦ The linked list is a linear data structure . that contains a sequence of elements called “Node” which  are linked to one another
                   by reference or memory address. Unlike array the nodes  are not stored at contagious memory locations.
                    ♦ 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.

                    ♦ A binary tree is a tree structure where the degree is 2. A binary tree has maximum of two children.
                    ♦ There are three types of tree traversals namely pre order. post order , in order





















                538538  Touchpad Computer Science-XII
   535   536   537   538   539   540   541   542   543   544   545