Class Note for CS 357 at UA-Data Structures (9)
Class Note for CS 357 at UA-Data Structures (9)
Popular in Course
Popular in Department
This 3 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 14 views.
Reviews for Class Note for CS 357 at UA-Data Structures (9)
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
Announcements CS 357 Data Structures Class 16 February 18 2002 Chapter 6 section 3 for next time Project 2 is scheduled to be out on Wednesday February 20 mzmzc 357C135 mm p 2 Recurring Recursion Trees 1 Give a recursive algorithm for calculating m for any n 2 0 Algunthm Puwmn if ri El return I return in Pummnh 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 Terminology rooted no pun intended in family trees mzmzc 357C135 mm p 3 mzmzc 357C135 mm p a Tree Terms Tree Terms cont 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 Internal Node Has children All nongreen nodes Ancestor The node or an ancestor of its parent A is the ancestor of I 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 particular node BD E is a subtree rooted at B mzmzc 357C135 mm p s mzmzc 357C135 mm p 5 Trees in the wild Binary Trees 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 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 357C135 Ms e mzmzc 357C135 Ms e z Tree ADT Fundamental Functions Tree ADT Supporting Functions ruut e Purpuse Retumtherum prtnetree 7 input ane 7 output Pusmuri urNudE parent v e Purpuse Return tne parent nude ufv ari Ermruccurs irv is mint 7 input PEISitiEIri 7 output Pusmuri eniiuren v e Purpuse Return an iteratur ertne eniiuren pr npuev 7 input PEISitiEIri 7 output iteratprerppsinpns islriterrial v e Purpuse Test wnetnernpuev isinIErrial 7 input PEISitiEIri 7 output Euuleari isEXtErrial v e Purpuse Test Whether nudev is aternai 7 input PEISitiEIri 7 output Euuleari istpt v e Purpuse Test Whether nudev is tne ruut ertnetree 7 input PEISitiEIri 7 output Euuleari mzmzc 357C135 Ms e 9 mzmzc 3570153 th e em Tree ADT Other Supporting Functions Depth size 0 Pumase Returnthenuriiberatnadesinthetree input Narie output lmeger eiements 0 Pumase Return an tteteu mall elements saved a nudes atthetree input Narie output itestututupieus pustpns 0 Pumase Return sriiterawatallthenadesmthetree input Narie output itestututpusttms wapElementSW W Pumase Smptheelaiimtsstwedattheriadesvsrid W input vapasnims output Nme ieplaceElemenKv E Pumase nepisee win element e and tetuntne element saved a nude v input Apastianandanabla output opieet 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 3570153 th e e mzmzc 3570153 th e e12 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 Algorithm depth v Order ifT lsRuutv then return a Assumptiuns return 1 uepth r parentv Algorithm haightlm Order h u Assumptiuns for each v e T pusltluns do ifT lsEXternalv then h maxhuepthrv return l1 Algorithm heighti v Order ifT lsExterrlalv then return a Assumptiuns h u for each W e T chlldrenv do h magtlth helght2T vv return 1 h mzmzc 357C135 mes p m 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 Quick Quiz Assuming visit means print the element stored in that node and that the tree is ordered le to right Give he height ofthe tree Give he depth ofthe node holding element 11 Give he preorder traversal Give he postorder traversal p 15 p e15 mzmzc 357C135 mes mzmzc 357C135 mes
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'