Question? Leave a message!




Tree traversals

Tree traversals
ECE 250 Algorithms and Data Structures Tree traversals Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Tree traversals 2 Outline This topic will cover tree traversals: – A means of visiting all the objects in a tree data structure – We will look at • Breadthfirst traversals • Depthfirst traversals – Preorder and Postorder depthfirst traversals – Applications – General guidelinesTree traversals 3 4.3 Background All the objects stored in an array or linked list can be accessed sequentially When discussing deques, we introduced iterators in C++: – These allow the user to step through all the objects in a container Question: how can we iterate through all the objects in a tree in a predictable and efficient manner – Requirements: Q(n) run time and o(n) memory Tree traversals 4 4.3.1 Types of Traversals We have already seen one traversal: – The breadthfirst traversal visits all nodes at depth k before proceeding onto depth k + 1 – Easy to implement using a queue Another approach is to visit always go as deep as possible before visiting other siblings: depthfirst traversalsTree traversals 5 4.3.1 BreadthFirst Traversal Breadthfirst traversals visit all nodes at a given depth – Can be implemented using a queue – Run time is Q(n) – Memory is potentially expensive: maximum nodes at a given depth – Order: A B H C D G I E F J KTree traversals 6 4.3.1 BreadthFirst Traversal The implementation was already discussed: – Create a queue and push the root node onto the queue – While the queue is not empty: • Push all of its children of the front node onto the queue • Pop the front nodeTree traversals 7 4.3.2 Backtracking To discuss depthfirst traversals, we will define a backtracking algorithm for stepping through a tree: – At any node, we proceed to the first child that has not yet been visited – Or, if we have visited all the children (of which a leaf node is a special case), we backtrack to the parent and repeat this decision making process We end once all the children of the root are visitedTree traversals 8 4.3.2 Depthfirst Traversal We define such a path as a depthfirst traversal We note that each node could be visited twice in such a scheme – The first time the node is approached (before any children) – The last time it is approached (after all children)Tree traversals 9 4.3.2.1 Preorder Depthfirst Traversal Visiting each node first results in the sequence A, B, C, D, E, F, G, H, I, J, K, L, MTree traversals 10 4.3.2.1 Postorder Depthfirst Traversal Visiting the nodes with their last visit: D, C, F, G, E, B, J, K, L, I, M, H, ATree traversals 11 4.3.3 Implementing DepthFirst Traversals Depthfirst traversals can be implemented with recursion: template typename Type void SimpletreeType::depthfirsttraversal() const // Perform previsit operations on the element std::cout element ' '; // Perform a depthfirst traversal on each of the children for ( ece250::SinglenodeSimpletree ptr = children.head(); ptr = 0; ptr = ptrnext() ) ptrretrieve()depthfirsttraversal(); // Perform postvisit operations on the element std::cout element ' '; Tree traversals 12 4.3.3 Implementing DepthFirst Traversals Alternatively, we can use a stack: – Create a stack and push the root node onto the stack – While the stack is not empty: • Pop the top node • Push all of the children of that node to the top of the stack in reverse order – Run time is Q(n) – The objects on the stack are all unvisited siblings from the root to the current node • If each node has a maximum of two children, the memory required is Q(h): the height of the tree With the recursive implementation, the memory is Q(h): recursion just hides the memoryTree traversals 13 4.3.4 Guidelines Depthfirst traversals are used whenever: – The parent needs information about all its children or descendants, or – The children require information about all its parent or ancestors In designing a depthfirst traversal, it is necessary to consider: 1. Before the children are traversed, what initializations, operations and calculations must be performed 2. In recursively traversing the children: a) What information must be passed to the children during the recursive call b) What information must the children pass back, and how must this information be collated 3. Once all children have been traversed, what operations and calculations depend on information collated during the recursive traversals 4. What information must be passed back to the parentTree traversals 14 4.3.4 Applications Tree application: displaying information about directory structures and the files contained within – Finding the height of a tree – Printing a hierarchical structure – Determining memory usageTree traversals 15 4.3.4.1 Height The int height() const function is recursive in nature: 1. Before the children are traversed, we assume that the node has no children and we set the height to zero: h = 0 current 2. In recursively traversing the children, each child returns its height h and we update the height if 1 + h h current 3. Once all children have been traversed, we return h current When the root returns a value, that is the height of the treeTree traversals 16 4.3.4.2 Printing a Hierarchy Consider the directory structure presented on the left—how do we display this in the format on the right / usr/ bin/ local/ var/ adm/ cron/ log/ What do we do at each stepTree traversals 17 4.3.4.2 Printing a Hierarchy For a directory, we initialize a tab level at the root to 0 We then do: 1. Before the children are traversed, we must: a) Indent an appropriate number of tabs, and b) Print the name of the directory followed by a '/' 2. In recursively traversing the children: a) A value of one plus the current tab level must be passed to the children, and b) No information must be passed back 3. Once all children have been traversed, we are finishedTree traversals 18 4.3.4.2 Printing a Hierarchy Assume the function void printtabs( int n ) prints n tabs template typename Type void SimpletreeType::print( int depth ) const printtabs( depth ); std::cout retrieve()name() '/' std::endl; for ( ece250::SinglenodeSimpletree ptr = children.head(); ptr = 0; ptr = ptrnext() ) ptrretrieve()print( depth + 1 ); Tree traversals 19 4.3.4.3 Determining Memory Usage Suppose we need to determine the memory usage of a directory and all its subdirectories: – We must determine and print the memory usage of all subdirectories before we can determine the memory usage of the current directoryTree traversals 20 4.3.4.3 Determining Memory Usage Suppose we are printing the directory usage of this tree: bin/ 12 local/ 15 usr/ 31 adm/ 6 cron/ 5 log/ 9 var/ 23 / 61Tree traversals 21 4.3.4.2 Determining Memory Usage For a directory, we initialize a tab level at the root to 0 We then do: 1. Before the children are traversed, we must: a) Initialize the memory usage to that in the current directory. 2. In recursively traversing the children: a) A value of one plus the current tab level must be passed to the children, and b) Each child will return the memory used within its directories and this must be added to the current memory usage. 3. Once all children have been traversed, we must: a) Print the appropriate number of tabs, b) Print the name of the directory followed by a "/ ", and c) Print the memory used by this directory and its descendantsTree traversals 22 4.3.4.3 Printing a Hierarchy template typename Type int SimpletreeType::du( int depth ) const int usage = retrieve()memory(); for ( ece250::SinglenodeSimpletree ptr = children.head(); ptr = 0; ptr = ptrnext() ) usage += ptrretrieve()du( depth + 1 ); printtabs( depth ); std::cout retrieve()name() "/ " usage std::endl; return usage; Tree traversals 23 Summary This topic covered two types of traversals: – Breadthfirst traversals – Depthfirst traversals – Applications – Determination of how to structure a depthfirst traversalTree traversals 24 ReferencesTree traversals 25 Usage Notes • These slides are made publicly available on the web for anyone to use • If you choose to use them, or a part thereof, for a course at another institution, I ask only three things: – that you inform me that you are using the slides, – that you acknowledge my work, and – that you alert me of any mistakes which I made or changes which you make, and allow me the option of incorporating such changes (with an acknowledgment) in my set of slides Sincerely, Douglas Wilhelm Harder, MMath dwharderalumni.uwaterloo.ca
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017