Download to read offline
Data structure lecture of tree in daa -07.ppt
- 1.
- 2. Tree In thislecture, we can extend the concept of linked data structure (linked list, stack, queue) to a structure that may have multiple relations among its nodes. One reason to use trees might be because you want to store information that naturally forms a hierarchy. For example 2
- 3. A treeis non linear data structure. Each object of a tree starts with a root and extends into several branches. Each branch may extend into other branches . Tree is mainly used to represent the data containing a hierarchal relationship between elements e.g family tree, table contents, organization chart of a company 3
- 4. General tree: Ageneral tree is a tree where each node may have zero or more children. or A general tree ,a node can have any number of children. Note: A binary tree is a specialized case of a general tree. 4
- 5. A typical treeis shown below 5
- 6. Tree Terminology In atree data structure, we use the following terminology. 1)Node : An entry in a tree. 2)Root Node: In a tree data structure, the first node is called as Root Node. Every tree must have root node. We can say that root node is the origin of tree data structure. In any tree, there must be only one root node. We never have multiple root nodes in a tree. 6
- 7.
- 8. Tree Terminology 3) Edge:In a tree data structure, the connecting link between any two nodes is called as EDGE. In a tree with 'N' number of nodes there will be a maximum of 'N-1' number of edges. 8
- 9. Tree Terminology 4) Parent:In a tree data structure, the node which is predecessor of any node is called as PARENT NODE. In simple words, the node which has branch from it to any other node is called as parent node. Parent node can also be defined as "The node which has child / children". 9
- 10. Tree Terminology 5) Child: In a tree data structure, the node which is descendant of any node is called as CHILD Node. In simple words, the node which has a link from its parent node is called as child node. In a tree, any parent node can have any number of child nodes. In a tree, all the nodes except root are child nodes. 10
- 11. Tree Terminology 6) Siblings:In a tree data structure, nodes which belong to same Parent are called as SIBLINGS. In simple words, the nodes with same parent are called as Sibling nodes. 11
- 12. Tree Terminology 7) Leaf:In a tree data structure, the node which does not have a child is called as LEAF Node. In simple words, a leaf is a node with no child. In a tree data structure, the leaf nodes are also called as External Nodes. External node is also a node with no child. In a tree, leaf node is also called as 'Terminal' node. 12
- 13.
- 14. Tree Terminology 8) InternalNodes: In a tree data structure, the node which has at least one child is called as INTERNAL Node. In simple words, an internal node is a node with at least one child. In a tree data structure, nodes other than leaf nodes are called as Internal Nodes. The root node is also said to be Internal Node if the tree has more than one node. Internal nodes are also called as 'Non-Terminal' nodes. 14
- 15.
- 16. Tree Terminology 9) Degree: In a tree data structure, the total number of children of a node is called as DEGREE of that Node. In simple words, the Degree of a node is total number of children it has. 16
- 17. Tree Terminology 10) Level:In a tree data structure, the root node is said to be at Level 0 and the children of root node are at Level 1 and the children of the nodes which are at Level 1 will be at Level 2 and so on... In simple words, in a tree each step from top to bottom is called as a Level and the Level count starts with '0' and incremented by one at each level (Step). 17
- 18.
- 19.
- 20.
- 21. Tree Terminology 14) SubTree: In a tree data structure, each child from a node forms a subtree recursively. Every child node will form a subtree on its parent node. 21
- 22.
- 23. Copies oftree Contents of each node are also same. 23
- 24.
- 25. Binary Tree Ina normal tree, every node can have any number of children. Binary tree is a special type of tree data structure in which every node can have a maximum of 2 children. One is known as left child and the other is known as right child. A tree in which every node can have a maximum of two children is called as Binary Tree. Note: In a binary tree, every node can have either 0 children or 1 child or 2 children but not more than 2 children. 25
- 26.
- 27. Types of binarytree A binary tree has following types 1) Strictly Binary Tree In a binary tree, every node can have a maximum of two children. But in strictly binary tree, every node should have exactly two children or none. That means every internal node must have exactly two children or none . Note: A binary tree in which every node has either two or zero number of children is called Strictly Binary Tree 27
- 28. Strictly Binary Tree……. Strictlybinary tree is also called as Full Binary Tree or Proper Binary Tree or 2-Tree 28
- 29. 2) Complete BinaryTree In a binary tree, every node can have a maximum of two children. But in strictly binary tree, every node should have exactly two children or none an And complete binary tree all the nodes must have exactly two children and at every level of complete binary tree there must be 2level number of nodes. For example at level 2 there must be 22 = 4 nodes and at level 3 there must be 23 = 8 nodes. 29
- 30. Note: Binarytree in which every internal node has exactly two children and all leaf nodes are at same level is called Complete Binary Tree. Complete binary tree is also called as Perfect Binary Tree 30
- 31. 3) Extended BinaryTree Extended binary tree consists of replacing every null subtree of the original tree with special nodes. Empty circle represents internal node and square represents external node. The nodes from the original tree are internal nodes and the special nodes are external nodes. All external nodes are leaf nodes and the internal nodes are non-leaf nodes. Every internal node in the extended binary tree has exactly two children and every external node is a leaf. It displays the result which is a complete binary tree. 31
- 32.
- 33. Note: In extendedbinary tree, each node has either 0 or 2 child node. The node with 2 child node are called internal nodes, and the nodes with 0 child node are called external nodes, Extended binary tree also known as 2-tree. 33
- 34.
- 35. Method of Binarytree traversing Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree. 35
- 36. There are threeways which we use to traverse a tree − 1. In-order Traversal 2. Pre-order Traversal 3. Post-order Traversal 36
- 37. 1) In-order Traversal In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself. If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order. 37
- 38. 38 We start fromD, and following in-order traversal, we move to its left subtree B. B is also traversed in-order. The process goes on until all the nodes are visited. The output of in order traversal of this tree will be − D B E A F C G → → → → → →
- 39. Algorithm for In-orderTraversal 39 Until all nodes are traversed − Step 1 − Recursively traverse left subtree. Step 2 − Visit root node. Step 3 − Recursively traverse right subtree.
- 40. 2) Pre-order Traversal In this traversal method, the root node is visited first, then the left subtree and finally the right subtree. 40
- 41. We startfrom A, and following pre-order traversal, we first visit A itself and then move to its left subtree B. B is also traversed pre-order. The process goes on until all the nodes are visited. The output of pre-order traversal of this tree will be − A → B → D → E → C → F → G 41
- 42. Algorithm for Pre-orderTraversal 42 Until all nodes are traversed − Step 1 − Visit root node. Step 2 −Recursively traverse left subtree. Step 3 − Recursively traverse right subtree.
- 43. 3) Post-order Traversal In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node. 43
- 44. We startfrom D, and following post-order traversal, we move to its left subtree B. B is also traversed post- order. The process goes on until all the nodes are visited. The output of post-order traversal of this tree will be − D → E → B → F → G → C → A 44
- 45. Algorithm for Post-orderTraversal 45 Until all nodes are traversed − Step 1 − Recursively traverse left subtree. Step 2 − Recursively traverse right subtree. Step 3 − Visit root node.
- 46.
- 47. Example 47 BST IS USEDMAINLY FOR SEARCHING PURPOSE
- 48.
- 49. Polish Notation Polishnotation (PN), also known as normal Polish notation (NPN),Łukasiewicz notation, is a mathematical notation in which operators precede their operands, in contrast to infix notation (in which operators are placed between operands), as well as to reverse Polish notation (RPN, in which operators follow their operands). 49
- 50. Three Polish Notation 1.Polish infix notations 2. Polish Prefix notations 3. Polish Postfix notations 50
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.