際際滷

際際滷Share a Scribd company logo

Trees

Download as PPTX, PDF
S
surya pandian

This document defines common tree data structure terminology and properties. It discusses different types of trees like binary trees and binary search trees. It covers tree traversal methods like pre-order, in-order and post-order traversal. It also describes how to construct expression trees from postfix and prefix expressions. Finally, it briefly mentions insertion and deletion operations in binary search trees.

1 of 23
Download to read offline
Trees
INTRODUCTION Tree is a non-linear data structure. It is mainly used to represent data containing a hierarchical relationship between elements. Eg: Government Subdivisions.
Trees
TREE TERMINOLOGIES ROOT: Node at the top of the tree is called as root. There is only one root in a tree. PARENT: Any node(except the root) has exactly one edge running upward to another node. The node above the given node is called parent. CHILD: Any node may have one or more lines running downward to other nodes. The nodes below a given node are called its children.
ANCESTOR: Parents, grandparents are called ancestors DESCENDANTS: Children, grandchildren are called descendants. SIBLINGS: Children of the same parent are called siblings. LEVEL: The level of a particular node refers to how many generations the node is from the root. If the root is assumed to be on level 0 then its children are at level 1. DEPTH: The Depth of a node n is the length of the unique path from root to node n. The root is at depth 0.
LEAF NODE: Node having no children. HEIGHT: Height of a node n is the length of the longest path from node n to leaf. Height of the tree= Height of the root. DEGREE OF THE NODE: Degree of the node is the number of children of the node. The node with degree 0 is a leaf or terminal node. Degree of tree= Maximum degree of any node in the tree.
BINARY TREES The Binary Tree is a tree in which no node can have more than two children. PROPERTIES: Every Binary tree with n elements, n>0 has exactly n-1 edges. A full binary tree of height h has exactly 2^(h+1) -1 nodes.
BINARY TREE TRAVERSAL METHOD: Traversal is the process of visiting every node in the tree exactly once. There are three methods of Traversal. Pre order. In order. Post order.
PRE ORDER: Step 1: Visit the root. Step 2: Traverse the left sub tree. Step 3: Traverse the right sub tree. IN ORDER: Step 1: Traverse the left sub tree. Step 2: Visit the root. Step 3: Traverse the right sub tree. POST ORDER: Step 1: Traverse the left sub tree. Step 2: Traverse the right sub tree. Step 3: Visit the root.
EXPRESSION TREE CONVERSION OF POSTFIX EXPRESSION INTO EXPRESSION TREE: Step 1: Read the postfix expression one symbol at a time from left to right. Step 2: If the symbol is an operand, we create a one node tree and push a pointer to it on to a stack. Step 3: If the symbol is an operator pop the last two sub trees and forma new tree whose root is that operator.
Eg: ab+cde+**
Trees
CONVERSION OF PREFIX EXPRESSION TO EXPRESSION TREE: Step 1:Read the prefix expression from right to left. Step 2: same as previous one. Step 3: same as previous one. Additionally, the last popped one should be on the left of the root.
Eg: ++a*bc*+*defg
Trees
Trees
Trees
BINARY SEARCH TREE Binary Search Tree is a tree in which for every node X, in the tree, the values of all the keys in its left sub tree are smaller than the key value in X, and the values of all the keys in its right sub tree are larger than the key value in X. Left Sub tree should have lesser value than its corresponding root and also the main root. Whereas Right Sub tree should have greater value than the root.
Trees
INSERTION:
DELETION:
Trees
THANK YOU!!

More Related Content

Trees

  • 2. INTRODUCTION Tree is a non-linear data structure. It is mainly used to represent data containing a hierarchical relationship between elements. Eg: Government Subdivisions.
  • 4. TREE TERMINOLOGIES ROOT: Node at the top of the tree is called as root. There is only one root in a tree. PARENT: Any node(except the root) has exactly one edge running upward to another node. The node above the given node is called parent. CHILD: Any node may have one or more lines running downward to other nodes. The nodes below a given node are called its children.
  • 5. ANCESTOR: Parents, grandparents are called ancestors DESCENDANTS: Children, grandchildren are called descendants. SIBLINGS: Children of the same parent are called siblings. LEVEL: The level of a particular node refers to how many generations the node is from the root. If the root is assumed to be on level 0 then its children are at level 1. DEPTH: The Depth of a node n is the length of the unique path from root to node n. The root is at depth 0.
  • 6. LEAF NODE: Node having no children. HEIGHT: Height of a node n is the length of the longest path from node n to leaf. Height of the tree= Height of the root. DEGREE OF THE NODE: Degree of the node is the number of children of the node. The node with degree 0 is a leaf or terminal node. Degree of tree= Maximum degree of any node in the tree.
  • 7. BINARY TREES The Binary Tree is a tree in which no node can have more than two children. PROPERTIES: Every Binary tree with n elements, n>0 has exactly n-1 edges. A full binary tree of height h has exactly 2^(h+1) -1 nodes.
  • 8. BINARY TREE TRAVERSAL METHOD: Traversal is the process of visiting every node in the tree exactly once. There are three methods of Traversal. Pre order. In order. Post order.
  • 9. PRE ORDER: Step 1: Visit the root. Step 2: Traverse the left sub tree. Step 3: Traverse the right sub tree. IN ORDER: Step 1: Traverse the left sub tree. Step 2: Visit the root. Step 3: Traverse the right sub tree. POST ORDER: Step 1: Traverse the left sub tree. Step 2: Traverse the right sub tree. Step 3: Visit the root.
  • 10. EXPRESSION TREE CONVERSION OF POSTFIX EXPRESSION INTO EXPRESSION TREE: Step 1: Read the postfix expression one symbol at a time from left to right. Step 2: If the symbol is an operand, we create a one node tree and push a pointer to it on to a stack. Step 3: If the symbol is an operator pop the last two sub trees and forma new tree whose root is that operator.
  • 13. CONVERSION OF PREFIX EXPRESSION TO EXPRESSION TREE: Step 1:Read the prefix expression from right to left. Step 2: same as previous one. Step 3: same as previous one. Additionally, the last popped one should be on the left of the root.
  • 18. BINARY SEARCH TREE Binary Search Tree is a tree in which for every node X, in the tree, the values of all the keys in its left sub tree are smaller than the key value in X, and the values of all the keys in its right sub tree are larger than the key value in X. Left Sub tree should have lesser value than its corresponding root and also the main root. Whereas Right Sub tree should have greater value than the root.