1. Trees
Tree is a recursive structure.
1.1 math nodes
https://class.coursera.org/principlescomputing-001/wiki/view?page=trees
1.2 CODE无parent域的树
#poc_tree.py
class Tree:"""Recursive definition for trees plus various tree methods"""def __init__(self, value, children):"""Create a tree whose root has specific value (a string)Children is a list of references to the roots of the subtrees."""self._value = valueself._children = childrendef __str__(self):"""Generate a string representation of the treeUse an pre-order traversal of the tree"""ans = "["ans += str(self._value)for child in self._children:ans += ", "ans += str(child)return ans + "]"def get_value(self):"""Getter for node's value"""return self._valuedef children(self):"""Generator to return children"""for child in self._children:yield childdef num_nodes(self):"""Compute number of nodes in the tree"""ans = 1for child in self._children:ans += child.num_nodes()return ansdef num_leaves(self):"""Count number of leaves in tree"""if len(self._children) == 0:return 1ans = 0for child in self._children:ans += child.num_leaves()return ansdef height(self):"""Compute height of a tree rooted by self"""height = 0for child in self._children:height = max(height, child.height() + 1)return heightdef run_examples():"""Create some trees and apply various methods to these trees"""tree_a = Tree("a", [])tree_b = Tree("b", [])print "Tree consisting of single leaf node labelled 'a'", tree_aprint "Tree consisting of single leaf node labelled 'b'", tree_btree_cab = Tree("c", [tree_a, tree_b])print "Tree consisting of three node", tree_cabtree_dcabe = Tree("d", [tree_cab, Tree("e", [])])print "Tree consisting of five nodes", tree_dcabeprintmy_tree = Tree("a", [Tree("b", [Tree("c", []), Tree("d", [])]),Tree("e", [Tree("f", [Tree("g", [])]), Tree("h", []), Tree("i", [])])])print "Tree with nine nodes", my_treeprint "The tree has", my_tree.num_nodes(), "nodes,",print my_tree.num_leaves(), "leaves and height",print my_tree.height()#import poc_draw_tree#poc_draw_tree.TreeDisplay(my_tree)#run_examples()
1.3 CODE有parent域的树
#user36_3SjNfYqJMV_4.py
import poc_treeclass NavTree(poc_tree.Tree):"""Recursive definition for navigable trees plus extra tree methods"""def __init__(self, value, children, parent = None):"""Create a tree whose root has specific value (a string)children is a list of references to the roots of the children.parent (if specified) is a reference to the tree's parent node"""poc_tree.Tree.__init__(self, value, children)self._parent = parentfor child in self._children:child._parent = selfdef set_parent(self, parent):"""Update parent field"""self._parent = parentdef get_root(self):"""Return the root of the tree"""if self._parent == None:return self;else:return self._parent.get_root();def depth(self):"""Return the depth of the self with respect to the root of the tree"""passdef run_examples():"""Create some trees and apply various methods to these trees"""tree_a = NavTree("a", [])tree_b = NavTree("b", [])tree_cab = NavTree("c", [tree_a, tree_b])tree_e = NavTree("e", [])tree_dcabe = NavTree("d", [tree_cab, tree_e])print "This is the main tree -", tree_dcabeprint "This is tree that contains b -", tree_b.get_root()import poc_draw_treepoc_draw_tree.TreeDisplay(tree_dcabe)print "The node b has depth", tree_b.depth()print "The node e has depth", tree_e.depth()run_examples()# Expect output#This is the main tree – [d, [c, [a], [b]], [e]]]#This is tree that contains b – [d, [c, [a], [b]], [e]]#The node b has depth 2#The node e has depth 1
1.4 CODE arithmetic expreesion由树来表达
Interior nodes in the tree are always arithmetic operators.The leaves of the tree are always numbers.
#poc_arith_expression.py
# import Tree class definitionimport poc_tree# Use dictionary of lambdas to abstract function definitionsOPERATORS = {"+" : (lambda x, y : x + y),"-" : (lambda x, y : x – y),"*" : (lambda x, y : x * y),"/" : (lambda x, y : x / y),"//" : (lambda x, y : x // y),"%" : (lambda x, y : x % y)}class ArithmeticExpression(poc_tree.Tree):"""Basic operations on arithmetic expressions"""def __init__(self, value, children, parent = None):"""Create an arithmetic expression as a tree"""poc_tree.Tree.__init__(self, value, children)def __str__(self):"""Generate a string representation for an arithmetic expression"""if len(self._children) == 0:return str(self._value)ans = "("ans += str(self._children[0])ans += str(self._value)ans += str(self._children[1])ans += ")"return ansdef evaluate(self):"""Evaluate the arithmetic expression"""if len(self._children) == 0:if "." in self._value:return float(self._value)else:return int(self._value)else:function = OPERATORS[self._value]left_value = self._children[0].evaluate()right_value = self._children[1].evaluate()return function(left_value, right_value) def run_example():"""Create and evaluate some examples of arithmetic expressions"""one = ArithmeticExpression("1", [])two = ArithmeticExpression("2", [])three = ArithmeticExpression("3", [])print oneprint one.evaluate()one_plus_two = ArithmeticExpression("+", [one, two])print one_plus_twoprint one_plus_two.evaluate()one_plus_two_times_three = ArithmeticExpression("*", [one_plus_two, three])print one_plus_two_times_threeimport poc_draw_treepoc_draw_tree.TreeDisplay(one_plus_two_times_three)print one_plus_two_times_three.evaluate()run_example()2 List
我们摇摇头说，困难其实没什么大不了。
