Non Linear Data Structures

explanation of Non Linear Data Structures wit examples.
eg. tree , graph , general tree, binary tree

1. Nonlinear data structure Subject :- Data structure (2130702) :: Presented by :: Patel Adarsh ( 00 ) :: Guided faculty :: Prof. X yz Abc Sarvajanik College of Engineering & Technology

2. Tree The boxes on the tree are called nodes • The nodes immediately below (to the left and right of) a given node are called its children • The node immediately above a given node is called its parent • The (unique) node without a parent is called the root • A node with no children is called a leaf • Two children of the same parent are said to be siblings

3. Depth and height • depth or level: length of the path from root to the current node (depth of root = 0) • height: length of the longest path from root to any leaf – empty (null) tree's height: -1 – single-element tree's height: 0 – tree with a root with children: 1

4. In a binary tree , each node can have no more than two child nodes Trees are typically are represented using references as dynamic links For binary trees, this requires storing only two links per node to the left and right child Binary Tree

5. Tree traversal schemes include Preorder traversal ( root , left, right ) Inorder traversal ( left, root , right ) Postorder traversal ( left, right, root ) Preorder generates prefix expression ( polish notation ) from an expression trees Inorder generates a sorted ordering Postorder generates a post fix expression, also useful for node deletion Tree Traversal

6. Pre-order traversal sequence :: F, B, A, D, C, E, G, I, H (root, left, right) In-order traversal sequence :: A, B, C, D, E, F, G, H, I (left, root, right) Post-order traversal sequence :: A, C, E, D, B, H, I, G, F (left, right, root)

7. Binary Search Tree Binary search trees allow for fast insertion and removal of elements They are specially designed for fast searching All nodes in a binary search tree fulfill the property that: Descendants to the left have smaller data values than the node data value Descendants to the right have larger data values than the node data value

8. Threaded Tree Binary trees have a lot of wasted space: the leaf nodes each have 2 null pointers We can use these pointers to help us in inorder traversals We have the pointers reference the next node in an inorder traversal called threads We need to know if a pointer is an actual link or a thread, so we keep a boolean for each pointer

9. Threaded Tree Binary trees have a lot of wasted space: the leaf nodes each have 2 null pointers We can use these pointers to help us in inorder traversals We have the pointers reference the next node in an inorder traversal called threads We need to know if a pointer is an actual link or a thread, so we keep a boolean for each pointer

10. Threaded Tree 8 7 5 3 11 13 1 6 9

11. Threaded Tree 8 7 5 3 11 13 1 6 9 Output 1 3

12. Trees in which the number of subtrees of any node need not be required to be 0, 1, or 2. The number of subtrees for any node may be variable. Some nodes may have 1 or no subtrees, others may have 3, some 4, or any other combination. General Tree

13. Conversion process Use the root of the general tree as the root of the binary tree. Determine the first child of the root. This is the leftmost node in the general tree at the next level. Insert this node. The child reference of the parent node refers to this node. Continue finding the first child of each parent node and insert it below the parent node with the child reference of the parent to this node.

14. Conversion process (continued) When no more first children exist in the path just used, move back to the parent of the last node entered and repeat the above process. Complete the tree for all nodes. In order to locate where the node fits you must search for the first child at that level and then follow the sibling references to a nil where the next sibling can be inserted. The children of any sibling node can be inserted by locating the parent and then inserting the first child. Then the above process is repeated.

15. Creating binary tree from a general tree General Tree Binary Tree

16. .. Thank you ..