Unformatted text preview:

TreesGeneral TreesRooted TreesGeneral TermsTree example: DirectoryTrace the SIZE functionSlide 7Representation Of a General Tree -- first child/next siblingBinary tree (BT)Representation of Binary TreesSmall binary treesBinary Tree ApplicationsTraversalRecursive Traversal ImplementationSlide 15Designing a Nonrecursive TraversalA Nonrecursive Preorder TraversalA non-recursive preorder traversalA non-recursive inorder traversalLevel-Order Traversal -- Breadth First Search (BFS)1Trees53 71 2 82General TreesNonrecursive definition: a tree consists of a set of nodes and a set of directed edges that connect pairs of nodes.Recursive definition: Either a tree is empty or it consists of a root and zero or more nonempty subtrees T1, T2, … Tk, each of whose roots are connected by an edge from the root.ABDFGHECRootT2T1Tk•••subtreessubtrees3Rooted TreesIn this class, we consider only rooted trees. A rooted tree has the following properties:One node is distinguished as the root.Every node c, except the root, is connected by an edge from exactly one other node p. Node p is c’s parent, and c is one of p’s children. – acyclic propertyA unique path traverses from the root to each node.4General TermsPath length: the number of edges on the path from a node to another.Depth of a node: the length of the path from the root to the node.Height of a node: the length of the path form the node to the deepest leaf.Siblings: Nodes with the same parent.Size of a Node: the number of descendants the node has (including the node itself). The size of root is the size of a tree. The size of a leaf is 1.ABDFGHECNode Height Depth Size A 3 0 8 B 1 1 3 C 0 1 1 D 2 1 3 E 0 2 1 F 0 2 1 G 1 2 2 H 0 3 15Tree example: Directory6Trace the SIZE function7Trace the SIZE function8Representation Of a General Tree-- first child/next sibling Example for this tree:ABDFGHECAnullFirst childNext siblingBEnullHnull nullCnullDnullFnull nullGnullCannot directly access D from A. ParentPtrKey valuesibling1st child9Binary tree (BT)A binary tree is either empty, or it consists of a node called the root together with TWO binary trees called the left subtree and the right subtree of the root.A binary tree is either empty, or it consists of a node called the root together with TWO binary trees called the left subtree and the right subtree of the root.A binary tree is a tree in which no node can have more than two children.A binary tree is a tree in which no node can have more than two children.10Representation of Binary TreesleavesleavesrootrootLeaves are nodes that have no children.Leaves are nodes that have no children.Parent Node: is the one between the node and the root of the tree.parentparentright childright childleft childleft childChild Node: is the one between the node and the leaves of the tree.ParentPtrKey valueRight CLeft C11Small binary treesEmpty treeEmpty treeTree of size 1Tree of size 1Tree of size 2Tree of size 2Tree of size 3Tree of size 312Binary Tree Applications Expression treeA central data structure in compiler design. The leaves of an expression tree are operands; the other nodes contain operators. Huffman coding treeImplement a simple but relatively effective data compression algorithm. Binary Search Tree (BST)Will discuss in chapter 19.*- dbca+13TraversalThree standard traversal orderpreorder - V L Rinorder - L V Rpostorder - L R VPreorder: traverse the node itself first, then all nodes in the LEFT subtree , then all nodes in the RIGHT subtree.Preorder: traverse the node itself first, then all nodes in the LEFT subtree , then all nodes in the RIGHT subtree.Inorder: traverse all nodes in the LEFT subtree first, then the node itself, then all nodes in the RIGHT subtree.Inorder: traverse all nodes in the LEFT subtree first, then the node itself, then all nodes in the RIGHT subtree.Postorder: traverse all nodes in the LEFT subtree first, then all nodes in the RIGHT subtree, then the node itself, Postorder: traverse all nodes in the LEFT subtree first, then all nodes in the RIGHT subtree, then the node itself, VRL14Recursive Traversal ImplementationVoid PrintInorder (root) if root != null PrintInorder(root->left); print(root->data); PrintInorder(root->right); endif;Void PrintInorder (root) if root != null PrintInorder(root->left); print(root->data); PrintInorder(root->right); endif;The difference is the order of the three statements in the ‘IF’.The difference is the order of the three statements in the ‘IF’.12 34 5 6preorder : 1 2 4 5 3 6inorder : 4 2 5 1 3 6postorder : 4 5 2 6 3 1preorder : 1 2 4 5 3 6inorder : 4 2 5 1 3 6postorder : 4 5 2 6 3 1Void PrintPreorder (root) if root != null print(root->data); PrintPreorder(root->left); PrintPreorder(root->right); endif;Void PrintPreorder (root) if root != null print(root->data); PrintPreorder(root->left); PrintPreorder(root->right); endif;Void PrintPostorder (root) if root != null PrintPostorder(root->left); PrintPostorder(root->right); print(root->data); endif;Void PrintPostorder (root) if root != null PrintPostorder(root->left); PrintPostorder(root->right); print(root->data); endif;15Traversal12 34 5 6preorder : 1 2 4 5 3 6inorder : 4 2 5 1 3 6postorder : 4 5 2 6 3 1preorder : 1 2 4 5 3 6inorder : 4 2 5 1 3 6postorder : 4 5 2 6 3 171012 34 5698preorder : 1 … ...inorder : … 1 ...postorder : … … 1preorder : 1 … ...inorder : … 1 ...postorder : … … 116Designing a Nonrecursive TraversalConsider the algorithm for an inorder traversalIf the current node is not null traverse the left subtree process the current node traverse the right subtreeEnd ifWhen traversing the left subtree, the stack of activation records remembers the postponed obligations of processing the current node and traversing the right subtreeA nonrecursive version of the algorithm would have to use an explicit stack to remember these obligations17A Nonrecursive Preorder Traversal•Recursion is a convenient way to postpone tasks that will be completed at a later time•For example, in a preorder traversal, the task of traversing the right subtree is postponed while the left subtree is being traversed•To eliminate recursion, you must use a stack to remember postponed obligations18A non-recursive preorder traversalStack S push root onto S repeat until S is


View Full Document

GSU CSC 2320 - CSCI2320 Chapter 18

Download CSCI2320 Chapter 18
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CSCI2320 Chapter 18 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CSCI2320 Chapter 18 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?