Lab 9: Part 1

  • Go over trees from Wednesday lecture
  • In-lab assignment
    • To the binary tree program, you are to add a function that performs a post order traversal of the tree. (This is what is provided as input to create a tree.) This means that if you are at a node, add the traversal of the left node to the string, then the traversal of the right node to the string, then the node itself. After writing the function, write a __main__ program that constructs a tree, and then compares the postorder traversal generated by your function to the string used to create it. They should match.
      def postorder(tree, carryover=""): 
          if tree.left != None:
              carryover = postorder(tree.left, carryover)
          if tree.right != None:
              carryover = postorder(tree.right, carryover)
          if carryover != "":
              carryover += " " + tree.data
          else:
              carryover = tree.data
          return carryover
       
      def test(expression, answer):
          x = parse(expression)
          print x, "=", x.evaluate()
          print postorder(x)
          assert(postorder(x) == expression)
          assert(x.evaluate() == answer)
    • In the file system tree program, turn the two functions readfs and walktree into methods of the class FileSystemNode. Be sure to use the special keyword self in your conversion.
         def readfs(self, path):
              '''Read the file system starting at self.path.  Return a node representing
              all files and directories starting at that path.'''
              if os.path.isdir(path):
                  try:
                      for f in os.listdir(path):
                          subdir = FileSystemNode(path + "\\" + f)
                          self.appendNode(subdir.readfs(path + "\\" + f))
                  except WindowsError:
                      print "ignoring:", path
              return self
       
          def walktree(self, pat=None):
              '''Walk the result of reading in the file system.  Print files and
              directories that match pat.'''
              if pat:
                  if self.path.find(pat) >= 0:
                      print self.path
              else:
                  print self.path
              for f in self.nodes:
                  f.walktree(pat)
 
cs190c/lab9.txt · Last modified: 2008/07/24 12:12 by seh
 
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki