LinkedBinaryTree的python实现

重看Data structure and algorithms in python,仍然感觉数据结构真心难。
从tree->binary tree-> linked binary tree->euler tour,看的想吐

"""
p.element( ): Return the element stored at position p.
The tree ADT then supports the following accessor methods, allowing a user to
navigate the various positions of a tree:
T.root( ): Return the position of the root of tree T,
or None if T is empty.
T.is root(p): Return True if position p is the root of Tree T.
T.parent(p): Return the position of the parent of position p,
or None if p is the root of T.
T.num children(p): Return the number of children of position p.
T.children(p): Generate an iteration of the children of position p.
T.is leaf(p): Return True if position p does not have any children.
len(T): Return the number of positions (and hence elements) that
are contained in tree T.
T.is empty( ): Return True if tree T does not contain any positions.
T.positions( ): Generate an iteration of all positions of tree T.
iter(T): Generate an iteration of all elements stored within tree T.
"""

class Tree:
    #Abstract base class representing a tree structure

    class Position:
        #return the element stored at this position
        def element(self):
            raise NotImplementedError('must be implemented by subclass')

        def __eq__(self,other):
            #return true if other position represents the same location
            raise NotImplementedError('must be implemented by subclass')

        def __net__(self,other):
            return not(self ==other)

    #abstract methods that concrete subclass must support
    def root(self):
        #return position representing the tree's root(or None if empty)
        raise NotImplementedError('must be implemented by subclass')

    def parent(self,p):
        #Return the number of children that Position p has.
        raise NotImplementedError('must be implemented by subclass')

    def num_children(self,p):
        #return the number of children that position p has
        raise NotImplementedError('must be implemented by subclass')

    def children(self,p):
        #Generate an iteration of Positions representing p's children
        raise NotImplementedError('must be implemented by subclass')

    def __len__(self):
        #return the total number of elements in the tree
        raise NotImplementedError('must be implemented by subclass')

    #concrete method implemented in this class
    def is_root(self,p):
        #return True if position p represents the root of the tree
        return self.root()==p

    def is_leaf(self,p):
        return self.num_children(p)==0

    def is_empty(self):
        #return true if three is empty
        return len(self)==0

    def depth(self,p):
        #return the number of levels separating Position p from the root
        if self.is_root(p):
            return 0
        else:
            return 1+self.depth(self.parent(p))

    def _height1(self,p): #works ,but n**2 worst-case time
        #return the height of the tree
        return max(self.depth(p) for p in self.positions() is self.is_leaf(p))

    def _height2(self,p):
        #return the height of the subtree rooted at position p
        if self.is_leaf(p):
            return 0
        else:
            return 1+max(self._height2(c) for c in self.children(p))

    def height(self,p=None):
        #return the height of the subtree rooted at Position p
        #if p is None,return the height of the entire tree
        if p is None:
            p=self.root()
        return self._height2(p)

    def __iter__(self):
        #generate an interation of the tree's elements
        for p in self.positions():  #use same order as positions()
            yield p.element()       #but yield each element

    def preorder(self):
        #generate a preorder iterationm of positions in the tree
        if not self.is_empty():
            for p in self._subtree_preorder(self.root()):   #start recursion
                yield p

    def _subtree_preorder(self,p):
        #generate a preorder iteration of position in subtree rooted at p
        yield p     #visit p before its subtrees
        for c in self.children(p):      #for each child c
            for other in self._subtree_preorder(c): #do preorder of c's subtree
                yield other             #yielding each to our caller

    def positions(self):
        #generate an iteration of the tree's positions
        return self.preorder()          #return entire preorder iteration

    def postorder(self):
        #generate a postorder iteration of positions in the tree
        if not self.is_empty():
            for p in self._subtree_postorder(self.root()):  #start recursion
                yield p

    def _subtree_postorder(self,p):
        #generate a postorder iteration of positions in subtree rooted at p
        for c in self.children(p):  #for each child c
            for other in self._subtree_postorder(c):    #do postorder of c's subtree
                yield other                             #yield each to our caller
            yield p                                     #visit p after its subtrees

    def breadfirst(self):
        #generate a breadth-first iteration of the positions of the tree
        if not self.is_empty():
            fringe=LinkedQueue() #known positions not yet yielded
            fringe.enqueue(self.root()) #starting with the root
            while not fringe.is_empty():
                p=fringe.dequeue() #remove from front of the queue
                yield p
                for c in self.children(p):
                    fringe.enqueue(c) #add children to back of queue

"""Binary Tree
T.left(p): Return the position that represents the left child of p,
or None if p has no left child.
T.right(p): Return the position that represents the right child of p,
or None if p has no right child.
T.sibling(p): Return the position that represents the sibling of p,
or None if p has no sibling.
"""

class BinaryTree(Tree):
    #Abstract base class representing a binary tree
    def left(self,p):
        #return a Position representing p's left child
        #return None if p does not have
        raise NotImplementedError('must be implemented by subclass')

    def right(self,p):
        #return a Position representing p's right child
        #return None if p does not have
        raise NotImplementedError('must be implemented by subclass')

    #concrete methods implemented
    def sibling(self,p):
        #return a Position representing p's sibling
        #or None if no sibling
        parent=self.parent(p)
        if parent is None:          #p must be root
            return None             #root has no sibling
        else:
            if p==self.left(parent):
                return self.right(parent)   #possibly None
            else:
                return self.left(parent)    #possibly None

    def children(self,p):
        #Generate an iteration of Position representing p's children
        if self.left(p) is not None:
            yield self.left(p)
        if self.right(p) is not None:
            yield self.right(p)

    def inorder(self):
        #generate an inorder iteration of positions in the tree
        if not self.is_empty():
            for p in self._subtree_inorder(self.root()):
                yield p

    def _subtree_inorder(self,p):
        #generate an inorder iteration of positions in subtree rooted at p
        if self.left(p) is not None: #if left child exists, traverse its subtree
            for other in self._subtree_inorder(self.left(p)):
                yield other
        yield p                             #visit p between its subtree
        if self.right(p) is not None: #if right child exists,traverse its subtree
            for other in self._subtree_inorder(self.right(p)):
                yield other

    #override inherited version to make inorder the default
    def positions(self):
        #generate an iteration of the tree's positions
        return self.inorder()               #make inorder the default




"""
T.add root(e): Create a root for an empty tree, storing e as the element,
and return the position of that root; an error occurs if the
tree is not empty.
T.add left(p, e): Create a new node storing element e, link the node as the
left child of position p, and return the resulting position;
an error occurs if p already has a left child.
T.add right(p, e): Create a new node storing element e, link the node as the
right child of position p, and return the resulting position;
an error occurs if p already has a right child.
T.replace(p, e): Replace the element stored at position p with element e,
and return the previously stored element.
T.delete(p): Remove the node at position p, replacing it with its child,
if any, and return the element that had been stored at p;
an error occurs if p has two children.
T.attach(p, T1, T2): Attach the internal structure of trees T1 and T2, respec-
tively, as the left and right subtrees of leaf position p of
T, and reset T1 and T2 to empty trees; an error condition
occurs if p is not a leaf.
"""

class LinkedBinaryTree(BinaryTree):
    #LInked representation of a binary tree structure

    class _Node:
        __slots__='_element','_parent','_left','_right'

        def __init__(self,element,parent=None,left=None,right=None):
            self._element=element
            self._parent=parent
            self._left=left
            self._right=right

    class Position(BinaryTree.Position):
        #An abstraction representing the location of single element
        def __init__(self,container,node):
            #constructor should not be invoked by user
            self._container=container
            self._node=node

        def element(self):
            #return the element stored at this position
            return self._node._element

        def __eq__(self,other):
            #return true if other is position representing the same location
            return type(other) is type(self) and other._node is self._node

    def _validate(self,p):
        #return associated node,if position is valid
        if not isinstance(p,self.Position):
            raise TypeError('p must be proper Position type')
        if p._container is not self:
            raise ValueError('p does not belong to this container')
        if p._node._parent is p._node:  #convention for deprecated nodes
            raise ValueError('p is no longer valid')
        return p._node

    def _make_position(self,node):
        #return Position instance for given node(or None if no node)
        return self.Position(self,node) if node is not None else None


    def __init__(self):
        #create an initially empty binary tree
        self._root=None
        self._size=0

    #public accessors
    def __len__(self):
        return self._size

    def root(self):
        #return the root position of the ree(or None if tree is mepty)
        return self._make_position(self._root)

    def parent(self,p):
        #return the position of p's parent (or None if p is root)
        node=self._validate(p)
        return self._make_position(node._parent)

    def left(self,p):
        #return the position of p's left child(or NOne if no left child)
        node=self._validate(p)
        return self._make_position(node._left)

    def right(self,p):
        #return the position p's right child (or None if no right child)
        node=self._validate(p)
        return self._make_position(node._right)

    def num_children(self,p):
        #return the number of children of position p
        node=self._validate(p)
        count=0
        if node._left is not None:
            count+=1
        if node._right is not None:
            count+=1
        return count

    def _add_root(self,e):
        #place element e at the root of an empty tree and return new position
        #Raise ValueError if tree nonempty
        if self._root is not None: raise ValueError('Root exists')
        self._size=1
        self._root=self._Node(e)
        return self._make_position(self._root)

    def _add_left(self,p,e):
        #create a new left child for Position p,storing element e
        #return the position of new node
        #Raise ValueError if Position p is invalid or p already has a left child
        node=self._validate(p)
        if node._left is not None: raise ValueError('left child exists')
        self._size+=1
        node._left=self._Node(e,node)
        return self._make_position(node._left)

    def _add_right(self,p,e):
        #create a new right child for position,p storing element e
        #return the position of new node
        #Raise ValueError if position P is invalide or p already has a right child
        node=self._validate(p)
        if node._right is not None: raise ValueError('Right child exists')
        self._size+=1
        node._right=self._Node(e,node)
        return self._make_position(node._right)

    def _replace(self,p,e):
        #replace the element at position p with e,and return old element
        node=self._validate(p)
        old=node._element
        node._element=e
        return old

    def _delete(self,p):
        #Delete the node at position p,and replace it with it's child
        #return the element stored at position p
        #raise ValueError if position p is invalid or p has two children
        node=self._validate(p)
        if self.num_child(p)==2: raise ValueError('p has two children')
        child=node._left if node._left else node._right     #might be none
        if child is not None:
            child._parent=node._parent
        if node is self._root:
            self._root=child
        else:
            parent=node._parent
            if node is parent._left:
                parent._left=child
            else:
                parent._right=child
        self._size-=1
        node._parent=node
        return node._element

    def _attach(self,p,t1,t2):
        #attach tree t1 and t2 as left and right subtress of external p
        node=self._validate(p)
        if not self.is_leaf(p): raise ValueError('Position must be leaf')
        if not type(self) is type(t1) is type(t2):      #all 3 trees must be same type
            raise TypeError('Tree types must match')
        self._size+=len(t1)+len(t2)
        if not t1.is_empty():           #attached t1 as left subtree
            t1._root._parent=node
            node._left=t1._root
            t1._root=None               #set t1 instance to empty
            t1._size=0
        if not t2.is_empty():
            t2._root._parent=node
            node._right=t2._root
            t2._root=None               #set t2 instance to empty
            t2._size=0


class EulerTour:
    #abstract base class for performing Euler tour of a tree
    #_hook_previsit and _hook_postvisit may be overridden by subclasses

    def __init__(self,tree):
        #prepare an Euler tour template for given tree
        self._tree=tree

    def tree(self):
        #return reference to the tree being traversed
        return self._tree

    def execute(self):
        #perform the tour and return any result from post viist of root
        if len(self._tree)>0:
            return self._tour(self._tree.root(),0,[])       #start the recursion

    def _tour(self,p,d,path):
        #perform tour of subtree rooted at Position p
        #p Position of current node being visited
        #d depth of p in the tree
        #path list of indices of children on path from root to p
        self._hook_previsit(p,d,path)           #"pre visit" p
        results=[]
        path.append(0)                          #add new index to end of path before recursion
        for c in self._tree.children(p):
            results.append(self._tour(c,d+1,path))      #result on child's subtree
            path[-1]+=1                         #increment index
        path.pop() #remove extraneous index
        answer=self._hook_postvisit(p,d,path,results)
        return answer

    def _hook_previsit(self,p,d,path):
        pass

    def _hook_postvisit(self,p,d,path,results):
        pass

下面是用binary tree来做表达式的解析：

class ExpressionTree(LinkedBinaryTree):
    #An arithmetic expression tree
    def __init__(self,token,left=None,right=None):
        #create an expression tree
        super().__init__() #LinkedBinaryTree initialization
        if not isinstance(token,str):
            raise TypeError("Token must be a string")
        self._add_root(token) #use inherited,non public method
        if left is not None: #presumably three-parameter form
            if token not in "+-*x/":
                raise ValueError("token must be valid operator")
            self._attach(self.root(),left,right) #use inherited,nonpublic method

    def __str__(self):
        #return string representation of the expression
        pieces=[] #sequence of piecewise strings to compose
        self._parenthesize_recur(self.root(),pieces)
        return "".join(pieces)

    def _parenthesize_recur(self,p,result):
        #append piecewise representation of p subtree to resulting list
        if self.is_leaf(p):
            result.append(str(p.element())) #leaf value as a string
        else:
            result.append("(") #opening parenthesis
            self._parenthesize_recur(self.left(p),result) #left subtree
            result.append(p.element()) #operator
            self._parenthesize_recur(self.right(p),result) #right subtree
            result.append(")") #closing parenthesis

    def evaluate(self):
        #return the numeric result of the expression
        return self._evaluate_recur(self.root())

    def _evaluate_recur(self,p):
        #return the numeric result of subtree rooted at p
        if self.is_leaf(p):
            return float(p.element()) #we assume element is numeric
        else:
            op=p.element()
            left_val=self._evaluate_recur(self.left(p))
            right_val=self._evaluate_recur(self.right(p))
            if op=="+": return left_val + right_val
            elif op=="-": return left_val - right_val
            elif op=="/": return left_val / right_val
            else:
                return left_val * right_val

def build_expression_tree(tokens):
    #return an expression Tree based upon by a tokenized expression
    S=[] #use list as stack
    for t in tokens:
        if t in "+-*x/": #t is an operator symbol
            S.append(t) #push the operator symbol
        elif t not in "()": #consider t to be a literal
            S.append(ExpressionTree(t)) #push trivial tree storing value
        elif t==")": #compose a new tree from three constituent parts
            right=S.pop() #right subtree as per LIFO
            op=S.pop() #operator symbol
            left=S.pop() #left subtree
            S.append(ExpressionTree(op,left,right)) #repush tree

    return S.pop()


def test_buil_exp_tree():
    exp="(((3+1)x4)/((9-5)+2))"
    exp_tree=build_expression_tree(exp)
    print(exp_tree)
    print(exp_tree.evaluate())


test_buil_exp_tree()