1 08 Trees Hongfei Yan Apr. 13, 20 & 27, 2016

2

3 Note The picture illustrates the queue for the first sample.

4 Note In the first test the initial configuration looks like (123)(456)(78), that is, the first screen contains icons of applications 1, 2, 3, the second screen contains icons 4, 5, 6, the third screen contains icons 7, 8. After application 7 is launched, we get the new arrangement of the icons — (123)(457)(68). To launch it Anya makes 3 gestures. After application 8 is launched, we get configuration (123)(457)(86). To launch it Anya makes 3 gestures. After application 1 is launched, the arrangement of icons in the menu doesn't change. To launch it Anya makes 1 gesture. In total, Anya makes 7 gestures.

5 Note In the first example, Gennady first treats the teeth of the first child who will cry with volume 4. The confidences of the remaining children will get equal to  - 2, 1, 3, 1, respectively. Thus, the second child also cries at the volume of 1 and run to the exit. The confidence of the remaining children will be equal to 0, 2, 0. Then the third child will go to the office, and cry with volume 5. The other children won't bear this, and with a loud cry they will run to the exit. In the second sample, first the first child goes into the office, he will cry with volume 4. The confidence of the remaining children will be equal to 5,  - 1, 6, 8. Thus, the third child will cry with the volume of 1 and run to the exit. The confidence of the remaining children will be equal to 5, 5, 7. After that, the second child goes to the office and cry with the volume of 5. The confidences of the remaining children will be equal to 0, 3. Then the fourth child will go into the office and cry with the volume of 2. Because of this the confidence of the fifth child will be 1, and he will go into the office last.

6

7 Contents 01 Python Primer (P2-51)02 Object-Oriented Programming (P57-103) 03 Algorithm Analysis (P ) 04 Recursion (P ) 05 Array-Based Sequences (P ) 06 Stacks, Queues, and Deques (P ) 07 Linked Lists (P ) 08 Trees (P ) 09 Priority Queues (P ) 10 Maps, Hash Tables, and Skip Lists (P ) 11 Search Trees (P ) 12 Sorting and Selection (P ) 13 Text Processing (P ) 14 Graph Algorithms (P ) 15 Memory Management and B-Trees (P ) ISLR_Print6

8 Contents 8.1 General Trees 8.2 Binary Trees 8.3 Implementing Trees 8.4 Tree Traversal Algorithms 8.5 Case Study: An Expression Tree

9 Preview (1/2) template method pattern

10 Preview (2/2) template method pattern

11 8.1 General Trees 8.1.1 Tree Definitions and Properties The Tree Abstract Data Type Computing Depth and Height

12 General tree Productivity experts say that breakthroughs come by thinking “nonlinearly.” referring to an organizational relationship that is richer than the simple “before” and “after” relationships between objects in sequences. The relationships in a tree are hierarchical, with some objects being “above” and some “below” others. Tree structures allow us to implement a host of algorithms much faster than when using linear data structures, such as array-based lists or linked lists.

13 Trees 11/30/2017 7:26 PM Actually, the main terminology for tree data structures comes from family trees, with the terms “parent,” “child,” “ancestor,” and “descendant” being the most common words used to describe relationships. We show an example of a family tree in Figure 8.1. Figure 8.1: A family tree showing some descendants of Abraham, as recorded in Genesis, chapters 25–36.

14 What is a Tree In computer science, a tree is an abstract model of a hierarchical structure A tree consists of nodes with a parent-child relation Applications: Organization charts File systems Programming environments Computers”R”Us Sales R&D Manufacturing Laptops Desktops US International Europe Asia Canada

15 8.1.1 Tree Definition and PropertiesFormal Tree Definition define a tree T as a set of nodes storing elements such that the nodes have a parent-child relationship that satisfies the following properties: If T is nonempty, it has a special node, called the root of T, that has no parent. Each node v of T different from the root has a unique parent node w; every node with parent w is a child of w.

16 Define a tree recursivelya tree T is either empty or consists of a node r, called the root of T, and a (possibly empty) set of subtrees whose roots are the children of r.

17 Tree Terminology subtree Root: node without parent (A)Trees 11/30/2017 7:26 PM Tree Terminology Root: node without parent (A) Internal node: node with at least one child (A, B, C, F) External node (a.k.a. leaf ): node without children (E, I, J, K, G, H, D) External nodes are also known as leaves. Ancestors of a node: parent, grandparent, grand- grandparent, etc. Depth of a node: number of ancestors Height of a tree: maximum depth of any node (3) Descendant of a node: child, grandchild, grand- grandchild, etc. Subtree: tree consisting of a node and its descendants A B D C G H E F I J K subtree The height of a position p in a tree T is also defined recursively: • If p is a leaf, then the height of p is 0. • Otherwise, the height of p is one more than the maximum of the heights of p’s children. The height of a nonempty tree T is the height of the root of T. For example, the tree of Figure 8.2 has height 4. In addition, height can also be viewed as follows. Proposition 8.4: The height of a nonempty tree T is equal to the maximum of the depths of its leaf positions.

18 A node u is an ancestor of a node v if u = v or u is an ancestor of the parent of v. Conversely, we say that a node v is a descendant of a node u if u is an ancestor of v. For example, in Figure 8.3, cs252/ is an ancestor of papers/, and pr3 is a descendant of cs016/. The subtree of T rooted at a node v is the tree consisting of all the descendants of v in T (including v itself). In Figure 8.3, the subtree rooted at cs016/ consists of the nodes cs016/, grades, homeworks/, programs/, hw1, hw2,hw3, pr1, pr2, and pr3.

19 Other Node RelationshipsTwo nodes that are children of the same parent are siblings .

20 Edges and Paths in TreesAn edge of tree T is a pair of nodes (u,v) such that u is the parent of v, or vice versa. A path of T is a sequence of nodes such that any two consecutive nodes in the sequence form an edge. For example, the tree in Figure 8.3 contains the path (cs252/, projects/, demos/, market).

21 Example 8.2: The inheritance relation between classes in a Python program forms a tree when single inheritance is used. For example, in Section 2.4 we provided a summary of the hierarchy for Python’s exception types, as portrayed in Figure 8.4 (originally Figure 2.5). The BaseException class is the root of that hierarchy, while all user-defined exception classes should conventionally be declared as descendants of the more specific Exception class. (See, for example, the Empty class we introduced in Code Fragment 6.1 of Chapter 6.) In Python, all classes are organized into a single hierarchy, as there exists a built-in class named object as the ultimate base class. It is a direct or indirect base class of all other types in Python (even if not declared as such when defining a new class). Therefore, the hierarchy pictured in Figure 8.4 is only a portion of Python’s complete class hierarchy.

22 preview of the remainder of this chapterFigure 8.5: Our own inheritance hierarchy for modeling various abstractions and implementations of tree data structures. In the remainder of this chapter, we provide implementations of Tree, BinaryTree, and LinkedBinaryTree classes, and highlevel sketches for how LinkedTree and ArrayBinaryTree might be designed.

23 Ordered Trees A tree is ordered if there is a meaningful linear order among the children of each node; A family tree that describes generational relationships is often modeled as an ordered tree, with siblings ordered according to their birth. In contrast, an organizational chart for a company is typically considered an unordered tree. Likewise, when using a tree to describe an inheritance hierarchy, there is no particular significance to the order among the subclasses of a parent class.

24 Example 8.3: The components of a structured document, such as a book, are hierarchically organized as a tree whose internal nodes are parts, chapters, and sections, and whose leaves are paragraphs, tables, figures, and so on. (See Figure 8.6.) The root of the tree corresponds to the book itself. We could, in fact, consider expanding the tree further to show paragraphs consisting of sentences, sentences consisting of words, and words consisting of characters. Such a tree is an example of an ordered tree, because there is a well-defined order among the children of each node.

25 8.1.2 Tree ADT We use positions to abstract nodes Generic methods:Trees 11/30/2017 7:26 PM 8.1.2 Tree ADT We use positions to abstract nodes Generic methods: Integer len() Boolean is_empty() Iterator positions() Iterator iter() Accessor methods: position root() position parent(p) Iterator children(p) Integer num_children(p) Query methods: Boolean is_leaf(p) Boolean is_root(p) Update method: element replace (p, o) Additional update methods may be defined by data structures implementing the Tree ADT An element is stored at each position, and positions satisfy parent-child relationships that define the tree structure. A position object for a tree supports the method: p.element( ): Return the element stored at position p.

26 A more formal mechanism to designate the relationships between different implementations of the same abstraction is through the definition of one class that serves as an abstract base class, via inheritance, for one or more concrete classes. We choose to define a Tree class, in Code Fragment 8.1, that serves as an abstract base class corresponding to the tree ADT. Our reason for doing so is that there is quite a bit of useful code that we can provide, even at this level of abstraction, allowing greater code reuse in the concrete tree implementations we later define. The Tree class provides a definition of a nested Position class (which is also abstract), and declarations of many of the accessor methods included in the tree ADT. However, our Tree class does not define any internal representation for storing a tree, and five of the methods given in that code fragment remain abstract (root, parent, num_children, children, and __len__ ); each of these methods raises a NotImplementedError. The subclasses are responsible for overriding abstract methods, such as children, to provide a working implementation for each behavior, based on their chosen internal representation.

27 Code8.1 & 8.2: Abstract Tree Class in PythonAlthough the Tree class is an abstract base class, it includes several concrete methods with implementations that rely on calls to the abstract methods of the class. In defining the tree ADT in the previous section, we declare ten accessor methods. Five of those are the ones we left as abstract, in Code Fragment 8.1. The other five can be implemented based on the former. Code Fragment 8.2 provides concrete implementations for methods is root, is leaf, and is empty. We note that, with the Tree class being abstract, there is no reason to create a direct instance of it, nor would such an instance be useful. The class exists to serve as a base for inheritance, and users will create instances of concrete subclasses. The beauty of this design is that the concrete methods defined within the Tree abstract base class will be inherited by all subclasses. This promotes greater code reuse, as there will be no need for those subclasses to reimplement such behaviors.

28 8.1.3 Computing Depth and HeightLet p be the position of a node of a tree T. The depth of p is the number of ancestors of p, excluding p itself. Note that this definition implies that the depth of the root of T is 0. The depth of p can also be recursively defined as follows: If p is the root, then the depth of p is 0. Otherwise, the depth of p is one plus the depth of the parent of p.

29 Height The height of a position p in a tree T is also defined recursively: If p is a leaf, then the height of p is 0. Otherwise, the height of p is one more than the maximum of the heights of p’s children. The height of a nonempty tree T is the height of the root of T.

30 Proposition 8.4: The height of a nonempty tree T is equal to the maximum of the depths of its leaf positions.

31

32 compute the height of the entire tree without explicitly designating the tree root.

33 8.2 Binary Trees 8.2.1 The Binary Tree Abstract Data Type Properties of Binary Trees

34 Binary Trees A binary tree is a tree with the following properties:Each internal node has at most two children (exactly two for proper binary trees) The children of a node are an ordered pair We call the children of an internal node left child and right child Alternative recursive definition: a binary tree is either a tree consisting of a single node, or a tree whose root has an ordered pair of children, each of which is a binary tree Applications: arithmetic expressions decision processes searching A B C D E F G H I

35 Arithmetic Expression TreeBinary tree associated with an arithmetic expression internal nodes: operators external nodes: operands Example: arithmetic expression tree for the expression (2  (a - 1) + (3  b)) +  - 2 a 1 3 b

36 Decision Tree Binary tree associated with a decision processinternal nodes: questions with yes/no answer external nodes: decisions Example: dining decision Want a fast meal? Yes No How about coffee? On expense account? Yes No Yes No Starbucks Spike’s Al Forno Café Paragon

37 Figure 8. 19: A binary search tree storing integersFigure 8.19: A binary search tree storing integers. The solid path is traversed when searching (successfully) for 36. The dashed path is traversed when searching (unsuccessfully) for 70.

38 8.2.1 BinaryTree ADT The BinaryTree ADT extends the Tree ADT, i.e., it inherits all the methods of the Tree ADT Additional methods: position left(p) position right(p) position sibling(p) Update methods may be defined by data structures implementing the BinaryTree ADT

39

40 8.2.2 Properties of Proper Binary TreesBinary trees have several interesting properties dealing with relationships between their heights and number of nodes. We denote the set of all nodes of a tree T at the same depth d as level d of T. In a binary tree, level 0 has at most one node (the root), level 1 has at most two nodes (the children of the root), level 2 has at most four nodes, and so on. In general, level d has at most 2d nodes.

41 8.2.2 Properties of Proper Binary Treese = i + 1 n = 2e - 1 h  i h  (n - 1)/2 e  2h h  log2 e h  log2 (n + 1) - 1 Notation n number of nodes e number of external nodes i number of internal nodes h height

42 8.3 Implementing Trees 8.3.1 Linked Structure for Binary Trees Array-Based Representation of a Binary Tree Linked Structure for General Trees

43 The Tree and BinaryTree classes that we have defined thus far in this chapter are both formally abstract base classes. Although they provide a great deal of support, neither of them can be directly instantiated. We have not yet defined key implementation details for how a tree will be represented internally, and how we can effectively navigate between parents and children. Specifically, a concrete implementation of a tree must provide methods root, parent, num_children, children, __len__ , and in the case of BinaryTree, the additional accessors left and right. There are several choices for the internal representation of trees. We describe the most common representations in this section. We begin with the case of a binary tree, since its shape is more narrowly defined.

44 8.3.1 Linked Structure for Binary TreesA node is represented by an object storing Element Parent node Left child node Right child node Node objects implement the Position ADT  B   A D B A D     C E C E

45 Python Implementation of a Linked Binary Tree Structure (1/2)define a concrete LinkedBinaryTree class that implements the binary tree ADT by subclassing the BinaryTree class. define a simple, nonpublic Node class to represent a node, and a public Position class that wraps a node provide a validate utility for robustly checking the validity of a given position instance when unwrapping it, and a _make_position utility for wrapping a node as a position to return to a caller. Those definitions are provided in Code Fragment 8.8. As a formality, the new Position class is declared to inherit immediately from BinaryTree.Position. Technically, the BinaryTree class definition (see Code Fragment 8.7) does not formally declare such a nested class; it trivially inherits it from Tree.Position.

46 Python Implementation of a Linked Binary Tree Structure (2/2)Our class definition continues, in Code Fragment 8.9, with a constructor and with concrete implementations for the methods that remain abstract in the Tree and BinaryTree classes. The constructor creates an empty tree by initializing _root to None and _size to zero. These accessor methods are implemented with careful use of the validate and _make_position utilities to safeguard against boundary cases.

47 Operations for Updating a Linked Binary Treewe have provided functionality for examining an existing binary tree. However, the constructor for our LinkedBinaryTree class results in an empty tree and we have not provided any means for changing the structure or content of a tree. We chose not to declare update methods as part of the Tree or BinaryTree abstract base classes for several reasons. Although the principle of encapsulation suggests that the outward behaviors of a class need not depend on the internal representation, the efficiency of the operations depends greatly upon the representation. We prefer to have each concrete implementation of a tree class offer the most suitable options for updating a tree. The second reason we do not provide update methods in the base class is that we may not want such update methods to be part of a public interface. There are many applications of trees, and some forms of update operations that are suitable for one application may be unacceptable in another.

48 For linked binary trees, a reasonable set of update methods to support for general usage are the following:

49

50

51

52

53 Performance of the Linked Binary Tree ImplementationTable 8.1: Running times for the methods of an n-node binary tree implemented with a linked structure. The space usage is O(n).

54 8.3.2 Array-Based Representation of Binary Trees

55 Figure 8.12: Binary tree level numbering: (a) general scheme; (b) an example.

56

57

58 8.3.3 Linked Structure for General TreesA node is represented by an object storing Element Parent node Sequence of children nodes Node objects implement the Position ADT  B D A C E F When representing a binary tree with a linked structure, each node explicitly maintains fields left and right as references to individual children. For a general tree, there is no a priori limit on the number of children that a node may have. A natural way to realize a general tree T as a linked structure is to have each node store a single container of references to its children. For example, a children field of a node can be a Python list of references to the children of the node (if any). Such a linked representation is schematically illustrated in Figure 8.14. For a general tree, there is no a priori limit on the number of children that a node may have. A natural way to realize a general tree T as a linked structure is to have each node store a single container of references to its children.

59 Table 8.2: Running times of the accessor methods of an n-node general tree implemented with a linked structure. We let cp denote the number of children of a position p. The space usage is O(n).

60 8.4 Tree Traversal Algorithms8.4.1 Preorder and Postorder Traversals of General Trees 8.4.1 Breath-First Tree Traversal 8.4.3 Inorder Traversal of a Binary Tree 8.4.4 Implementing Tree Traversals in Python

61 8.4.1 Preorder and Postorder Traversals of General Trees11/30/2017 7:26 PM 8.4.1 Preorder and Postorder Traversals of General Trees A traversal visits the nodes of a tree in a systematic manner In a preorder traversal, a node is visited before its descendants Application: print a structured document Algorithm preOrder(v) visit(v) for each child w of v preorder (w) 1 Make Money Fast! A traversal of a tree T is a systematic way of accessing, or “visiting,” all the positions of T. The specific action associated with the “visit” of a position p depends on the application of this traversal, and could involve anything from incrementing a counter to performing some complex computation for p. In this section, we describe several common traversal schemes for trees, implement them in the context of our various tree classes, and discuss several common applications of tree traversals. 2 5 9 1. Motivations 2. Methods References 6 7 8 3 4 2.1 Stock Fraud 2.2 Ponzi Scheme 2.3 Bank Robbery 1.1 Greed 1.2 Avidity

62 Postorder Traversal Algorithm postOrder(v) for each child w of vIn a postorder traversal, a node is visited after its descendants Application: compute space used by files in a directory and its subdirectories Algorithm postOrder(v) for each child w of v postOrder (w) visit(v) 9 cs16/ 8 3 7 todo.txt 1K homeworks/ programs/ 1 2 4 5 6 h1c.doc 3K h1nc.doc 2K DDR.java 10K Stocks.java 25K Robot.java 20K

63 8.4.2 Breath-First Tree TraversalVisit all the positions at depth d before we visit the positions at depth d +1. Such an algorithm is known as a breadth-first traversal. A breadth-first traversal is a common approach used in software for playing games. A game tree represents the possible choices of moves that might be made by a player (or computer) during a game, with the root of the tree being the initial configuration for the game. For example, Figure 8.17 displays a partial game tree for Tic-Tac-Toe. A breadth-first traversal of such a game tree is often performed because a computer may be unable to explore a complete game tree in a limited amount of time. So the computer will consider all moves, then responses to those moves, going as deep as computational time allows.

64 Use a queue to produce a FIFO (i. eUse a queue to produce a FIFO (i.e., first-in first-out) semantics for the order in which we visit nodes. The overall running time is O(n), due to the n calls to enqueue and n calls to dequeue.

65 8.4.3 Inorder Traversal of a Binary TreeIn an inorder traversal a node is visited after its left subtree and before its right subtree Application: draw a binary tree x(v) = inorder rank of v y(v) = depth of v Algorithm inOrder(v) if v has a left child inOrder (left (v)) visit(v) if v has a right child inOrder (right (v)) 6 2 8 1 4 7 9 3 5

66 Print Arithmetic ExpressionsAlgorithm printExpression(v) if v has a left child print(“(’’) inOrder (left(v)) print(v.element ()) if v has a right child inOrder (right(v)) print (“)’’) Specialization of an inorder traversal print operand or operator when visiting node print “(“ before traversing left subtree print “)“ after traversing right subtree +  - 2 a 1 3 b ((2  (a - 1)) + (3  b))

67 Evaluate Arithmetic ExpressionsSpecialization of a postorder traversal recursive method returning the value of a subtree when visiting an internal node, combine the values of the subtrees Algorithm evalExpr(v) if is_leaf (v) return v.element () else x  evalExpr(left (v)) y  evalExpr(right (v))   operator stored at v return x  y +  - 2 5 1 3

68 Binary Search Trees An example of a binary search tree is shown in Figure The above properties assure that an inorder traversal of a binary search tree T visits the elements in nondecreasing order.

69 8.4.4 Implementing Tree Traversals in PythonT should include support for the following methods: T.positions( ): Generate an iteration of all positions of tree T. iter(T): Generate an iteration of all elements stored within tree T.

70 To implement the positions method, we have a choice of tree traversal algorithms.Given that there are advantages to each of those traversal orders, we will provide independent implementations of each strategy that can be called directly by a user of our class. We can then trivially adapt one of those as a default order for the positions method of the tree ADT.

71

72

73

74

75

76 8.4.5 Applications of Tree Traversalsdemonstrate several representative applications of tree traversals, including some customizations of the standard traversal algorithms. Table of Contents Parenthetic Representation of a Tree Computing Disk Space

77 Table of Contents Figure 8.15: Preorder traversal of an ordered tree, where the children of each position are ordered from left to right. Figure 8.20: Table of contents for a document represented by the tree in Figure 8.15: (a) without indentation; (b) with indentation based on depth within the tree.

78 The unindented version of the table of contentsgiven a tree T, can be produced with the following code:

79

80 produce an indented table of contents is to redesign a top-down recursion that includes the current depth as an additional parameter. Such an implementation is provided in Code Fragment This implementation runs in worst-case O(n) time

81 In the example of Figure 8In the example of Figure 8.20, we were fortunate in that the numbering was embedded within the elements of the tree. More generally, we might be interested in using a preorder traversal to display the structure of a tree, with indentation and also explicit numbering that was not present in the tree. For example, we might display the tree from Figure 8.2 beginning as: Figure 8.2

82 This is more challenging, because the numbers used as labels are implicit inthe structure of the tree. A label depends on the index of each position, relative to its siblings, along the path from the root to the current position. To accomplish the task, we add a representation of that path as an additional parameter to the recursive signature. Specifically, we use a list of zero-indexed numbers, one for each position along the downward path, other than the root. (We convert those numbers to oneindexed form when printing.) At the implementation level, we wish to avoid the inefficiency of duplicating such lists when sending a new parameter from one level of the recursion to the next. A standard solution is to share the same list instance throughout the recursion. At one level of the recursion, a new entry is temporarily added to the end of the list before making further recursive calls. In order to “leave no trace,” that same block of code must remove the extraneous entry from the list before completing its task. An implementation based on this approach is given in Code Fragment 8.24.

83 Parenthetic Representations of a TreeThe parenthetic string representation P(T) of tree T is recursively defined as follows. If T consists of a single position p, then P(T) = str(p.element()). Otherwise, it is defined recursively as, P(T) = str(p.element())+ ( +P(T1)+ , + · · · + , +P(Tk)+ ) where p is the root of T and T1,T2, ,Tk are the subtrees rooted at the children of p, which are given in order if T is an ordered tree. We are using “+” here to denote string concatenation. As an example, the parenthetic representation of the tree of Figure 8.2 would appear as follows (line breaks are cosmetic): Electronics R’Us (R&D, Sales (Domestic, International (Canada, S. America, Overseas (Africa, Europe, Asia, Australia))), Purchasing, Manufacturing (TV, CD, Tuner))

84

85 Computing Disk Space The recursive computation of disk space is emblematic of a postorder traversal, as we cannot effectively compute the total space used by a directory until after we know the space that is used by its children directories. Code Fragment 8.26: Recursive computation of disk space for a tree. We assume that a space( ) method of each tree element reports the local space used at that position.

86 8.4.6 Euler Tour Traversal and Template PatternTrees 11/30/2017 7:26 PM 8.4.6 Euler Tour Traversal and Template Pattern in some contexts it was important to know the depth of a position, or the complete path from the root to that position, or to return information from one level of the recursion to another. For each of the previous applications, we were able to develop a custom implementation to properly adapt the recursive ideas, Includes a special cases the preorder, postorder and inorder traversals but the great principles of object-oriented programming include adaptability and reusability.

87 Euler Tour Traversal of a TreeTrees 11/30/2017 7:26 PM Euler Tour Traversal of a Tree develop a more general framework for implementing tree traversals based on a concept known as an Euler tour traversal. The Euler tour traversal of a general tree T can be informally defined as a “walk” around T, where we start by going from the root toward its leftmost child, viewing the edges of T as being “walls” that we always keep to our left. +  - 2 5 1 3 L B R Figure 8.21.

88 The complexity of the walk is O(n), because it progresses exactly two times along each of the n−1 edges of the tree once going downward along the edge, and later going upward along the edge. To unify the concept of preorder and postorder traversals, we can think of there being two notable “visits” to each position p: A “pre visit” occurs when first reaching the position, that is, when the walk passes immediately left of the node in our visualization. A “post visit” occurs when the walk later proceeds upward from that position, that is, when the walk passes to the right of the node in our visualization.

89 The complexity of the walk is O(n), because it progresses exactly two timesalong each of the n−1 edges of the tree—once going downward along the edge, and later going upward along the edge. To unify the concept of preorder and postorder traversals, we can think of there being two notable “visits” to each position p: • A “pre visit” occurs when first reaching the position, that is, when the walk passes immediately left of the node in our visualization. • A “post visit” occurs when the walk later proceeds upward from that position, that is, when the walk passes to the right of the node in our visualization. The process of an Euler tour can easily be viewed recursively. In between the “pre visit” and “post visit” of a given position will be a recursive tour of each of its subtrees. Code Fragment 8.27: Algorithm eulertour for performing an Euler tour traversal of a subtree rooted at position p of a tree.

90 The Template Method PatternTo provide a framework that is reusable and adaptable, we rely on an object-oriented software design pattern, the template method pattern. The template method pattern describes a generic computation mechanism that can be specialized for a particular application by redefining certain steps. To allow customization, the primary algorithm calls auxiliary functions known as hooks at designated steps of the process. In the context of an Euler tour traversal, define two separate hooks, a previsit hook that is called before the subtrees are traversed, and a postvisit hook that is called after the completion of the subtree traversals. Our implementation will take the form of an EulerTour class that manages the process, and defines trivial definitions for the hooks that do nothing. The traversal can be customized by defining a subclass of EulerTour and overriding one or both hooks to provide specialized behavior.

91 Our implementation of an EulerTour class is provided in Code Fragment 8.28. Theprimary recursive process is defined in the nonpublic tour method. A tour instance is created by sending a reference to a specific tree to the constructor, and then by calling the public execute method, which beings the tour and returns a final result of the computation. Code Fragment 8.28: An EulerTour base class providing a framework for performing Euler tour traversals of a tree.

92 Two hooks that can be specializedmethod hook previsit(p, d, path) This function is called once for each position, immediately before its subtrees (if any) are traversed. Parameter p is a position in the tree, d is the depth of that position, and path is a list of indices. No return value is expected from this function. method hook postvisit(p, d, path, results) This function is called once for each position, immediately after its subtrees (if any) are traversed. The first three parameters use the same convention as did hook previsit. The final parameter is a list of objects that were provided as return values from the post visits of the respective subtrees of p. Any value returned by this call will be available to the parent of p during its postvisit. Parameter p is a position in the tree, d is the depth of that position, and path is a list of indices, using the convention described in the discussion of Code Fragment 8.24. For more complex tasks, subclasses of EulerTour may also choose to initialize and maintain additional state in the form of instance variables that can be accessed within the bodies of the hooks.

93 Using the Euler Tour FrameworkAs a simple example, an indented preorder traversal, akin to that originally produced by Code Fragment 8.23, can be generated with the simple subclass given in Code Fragment 8.29. akin to 英 [ əˈkɪn tu: ] 美 [ əˈkɪn tu ] 释义类似于

94 A labeled version of an indented, preorder presentation

95 the parenthetic string representationNotice that in this implementation, we need to invoke a method on the tree instance that is being traversed from within the hooks. The public tree() method of the EulerTour class serves as an accessor for that tree.

96 Computing disk space

97 The Euler Tour Traversal of a Binary Treethe concept of an Euler tour traversal of a general graph, using the template method pattern in designing the EulerTour class. That class provided methods _hook_previsit and _hook_postvisit that could be overridden to customize a tour. we provide a BinaryEulerTour specialization that includes an additional _hook_invisit that is called once for each position after its left subtree is traversed, but before its right subtree is traversed. implementation of BinaryEulerTour replaces the original tour utility to specialize to the case in which a node has at most two children. Our implementation of BinaryEulerTour replaces the original tour utility to specialize to the case in which a node has at most two children. If a node has only one child, a tour differentiates between whether that is a left child or a right child, with the “in visit” taking place after the visit of a sole left child, but before the visit of a sole right child. In the case of a leaf, the three hooks are called in succession.

98

99

100

101 8.5 Case Study: An Expression TreeDefine a new ExpressionTree class that provides support for constructing such trees (like the use of binary tree to represent the structure of an arithmetic expression), and for displaying and evaluating the arithmetic expression that such a tree represents. Our ExpressionTree class is define as a subclass of LinkedBinaryTree, and we rely on the nonpublic mutators to construct such trees. Each internal node must store a string that defines a binary operator (e.g., + ), and each leaf must store a numeric value (or a string representing a numeric value).

102 The goal is to build arbitrarily complex expression trees for compound arithmetic expressionssuch as (((3+1)×4)/((9−5)+2)). It suffices for the ExpressionTree class to support two basic forms of initialization: ExpressionTree(value): Create a tree storing the given value at the root. ExpressionTree(op,E1,E2): Create a tree storing string op at the root (e.g., +), and with the structures of existing ExpressionTree instances E1 and E2 as the left and right subtrees of the root, respectively.

103

104

105 Expression Tree Evaluation:The numeric evaluation of an expression tree can be accomplished with a simple application of a postorder traversal.

106 Building and Expression Treerely on a bottom-up construction algorithm, assuming that a string can first be tokenized so that multidigit numbers are treated atomically, and that the expression is fully parenthesized. The algorithm uses a stack S while scanning tokens of the input expression E to find values, operators, and right parentheses. (Left parentheses are ignored.)

107

108 1: http://net.pku.edu.cn/~course/cs202/2015/resource/dsap_python_code/ch08/3 2 (Pdb) ?next n(ext) Continue execution until the next line in the current function is reached or it returns.

109 (Pdb) ?step s(tep) Execute the current line, stop at the first possible occasion (either in a function that is called or in the current function).

110 Summary (1/2) template method pattern

111 Summary (2/2) template method pattern