Class Note for CS 357 at UA-Data Structures (14)
Class Note for CS 357 at UA-Data Structures (14)
Popular in Course
Popular in Department
This 6 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Alabama - Tuscaloosa taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Class Note for CS 357 at UA-Data Structures (14)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CS 357 Data Structures Class 16 February 18 2002 Announcements Chapter 6 section 3 for next time Project 2 is scheduled to be out on Wednesday February 20 mzmzc 357C135 mm Recurring Recursion 1 Give a recursive algorithm for calculating m for any n 2 0 Aigunmm Puwm n if ri El return i return in Pummm mzmzc 357C135 mm Trees A set of nodes storing elements much like lists Instead of next and previous references nodes have children Instead of a head reference trees have a root Which is perceptually the top element A in this diagram L2 Terminology rooted no pun intended in family trees Hj ll ij 339 mzmzc 357C135 mm p a Tree Terms Root The top element A Parent The node which contains this node s child pointer A is the parent of B Child The node which this node points to D is he child of B Siblings Nodes that are children ofthe same parent BampC External Node Has no children Also called a Leaf All green nodes mzmzc 357C135 mm p s Tree Terms cont Internal Node Has children All nongreen nodes Ancestor The node or an ancestor of its parent A is the ancestor of amp every other node Descendent The node or a descendent ofits children I is a descendent of H and C and A Subtree All descendents ofa par icular node BD E is a subtree rooted at B mzmzc 357C135 mm p 5 Trees in the wild Inheritance diagrams in Java javalang0bject is the ancestor of all other classes javautilLinkedList is the parent of your Queue class File systems Root directory Books Document map in Microso Word mzmzc amuss Ms p Binary Trees Ordered trees are trees for which a linear ordering of the children of each node is defined A binary tree is an ordered tree in which every node has at most two children Children are labeled as either the left or right If every node has either 0 or 2 children it is said to be proper mzmzc amuss Ms p z Tree ADT Fundamental Functions ruut e Purpuse Retumtnerum prtnetree 7 input NuriE 7 output Pusi uri urNude parent v e Purpuse Return tne parent npue ufv an Ermruccurs irv is mint 7 input PEISitiEIri 7 output Pusi uri niiuren v e Purpuse Return an iteratur prtne niiuren pr npuev 7 input PEISitiEIri 7 output iteratprprppsmpns mzmzc amuss Ms p 9 Tree ADT Supporting Functions 151111211151v 7 Purpuse T251 wn21n2111222v 15111211151 7 111221 P25111211 7 021221 22212511 15Ex1211151 v 7 Purpuse T251 wn21n21 11222v 15 2lt1211151 7 111221 P25111211 7 021221 22212511 15R221v 7 Purpuse T251 wn21n21 11222v151n2 1221211221122 7 111221 P25111211 7 021221 22212511 mzmzc 357022112122 2 212 Tree ADT Other Supporting Functions 5122 0 22112252 112m122M12221n22251n1221122 121221 NW2 Output 11112221 2121221115 0 22112252 112m 5211215111 21211 2121121115 52121 2 nudes 211221122 121221 NW2 Output 11221212122122 12251112115 0 22112252 112m an11212221211122n2222211221122 121221 NW2 Output 11221212122511m5 wapEiememSW W 22112252 52512122 21212115 51112221122 nadesvsnd W 121221 Yvaasmms Output Nme vepiaceEiementW E 22112252 112121222 W12 212112111 2 21121212121112 212112111 52121 2 nude v 121221 Apastmn 2112 an 22122 Output 021221 mzmzc 357022112122 2 2n Depth The depth of a node is the number of ancestors it has excluding the node itself By definition what is the depth of the root of any tree Any other node What is the depth of G Recursiver speaking Root has depth 0 Otherwise depth is 1 plus the depth of the parent mzmzc 357022112122 2 212 Height The height of a tree is the maximum depth of an external node of the tree By de nition what is the height of a tree with only a root node extrapolate into an external node An internal node What is the height of this tree Recursiver speaking External node has height 0 Otherwise height is 1 plus the max height of its children mzmzc 357C135 mes Algorithms mzmzc 357C135 mes Order Algorithm depth v Assumptiuns ifT lsRuutv then return a return 1 uepth r parentv Order Algorithm helghtl T Assumptiuns h u for each v e T pusltluns do ifT lsEXternalv then h maxhuepthm return l1 Order Algorithm haightzmv Assumptiuns ifT lsExterrlalv then return a h u for each W e T chlldrenv do h magtlth helght2T vv return 1 h p a mzmzc 357C135 mes Traversing a Tree PreOrder Asit the node Asit its children in order if ordered tree PostOrcler Asit its children in order if ordered tree Asit the node Visit means do something such as print or perform a calculation or p e15 Quick Quiz Assuming visit means print the element stored in that node and that the tree is ordered Ie toright Give the height of the tree Give the depth of he node holding element 11 Give the preorder traversal Give the postorder traversal 2m2c 357C135 Ms p as
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'