Interfaces
Interfaces
Trees
Trees
Tree Abstraction Recursive Description Relative Description (wooden trees)】 (family trees) Root 3 Branch Nodes Labels Leaf A tree has a root and a list of branches Each location in a tree is called a node Each branch is a tree Each node has a label value A tree with zero branches is called a leaf One node can be the parent/child of another
Branch Nodes Tree Abstraction 3 1 2 0 1 1 1 0 1 Recursive Description (wooden trees) Root Leaf Relative Description (family trees) A tree has a root and a list of branches Each branch is a tree A tree with zero branches is called a leaf Each location in a tree is called a node Each node has a label value One node can be the parent/child of another Labels
1 class Tree: 2 def __init__(self,label,branches=[]): 3 for b in branches: 4 assert isinstance(b,Tree) 5 self.label label 6 self.branches branches 7 def is_leaf(self): 8 return not self.branches >>> t=Tree(3,[Tree(2.[Tree(5)]) Tree(4)]) >>> tlabel 3 >>>t.branches[0]label 2 >>>t.branches[1]is_leaf() True
>>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)]) 3 2 4 5 >>> t.label 3 >>> t.branches[0].label 2 >>> t.branches[1].is_leaf() True 1 class Tree: 2 def __init__(self, label, branches=[]): 5 self.label = label 6 self.branches = branches 3 for b in branches: 4 assert isinstance(b, Tree) 7 def is_leaf(self): 8 return not self.branches
Pruning Demo Goal:Given a Tree,t,and a value x,remove each branch with label equal to x 3 prune(t,1) 3 2 0 7 0 1
Pruning Goal: Given a Tree, t, and a value x, remove each branch with label equal to x prune(t, 1) Demo