Binary Tree

File System Tree

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)