class  TREE[T]
   
-- generic binary tree with basic search facility and a facility to apply 
-- user-defined operators to the tree, but lacking basic edit facilities such 
-- as insert & remove
   
creation  make
   
feature {ANY}
   
   root : NODE[T]
   count : INTEGER
   
   make is
      do
	 root := Void
	 count := 0
	 found := False
      end -- make
   

feature {ANY}  -- searching
   
   found : BOOLEAN  -- outcome of most recent look_for action
   
   location : NODE[T] is  -- node found by look_for
      require
	 found
      do
	 Result := found_node
      end -- location
   
   look_for( t: T ) is
	 -- look for a node whose item matches t in the sense equal(i,item)
      do
	 found := False
	 look_from( t, root )
      ensure
	 not found or else equal(t,location.item)
      end -- look_for
   
feature {NONE}
   
   found_node : NODE[T]
   
   look_from( t: T; p: NODE[T] ) is
	 -- search subtree rooted at p for an item equal to t
      do
	 if p /= Void and not found then
	    if equal(t,p.item) then
	       found := True
	       found_node := p
	    else
	       look_from(t, p.left)
	       look_from(t, p.right)
	    end
	 end
      end -- look_from
   

feature {ANY}  -- apply user-defined operators
   
   -- The following routine applies a generic tree operator to a binary tree. 
   -- The idea is for the user to create his own operators by inheriting from 
   -- TREE_OPERATOR and supplying his own code for op.apply.  This mechanism 
   -- allows the tree traversal code below to be reused by all tree operators.
   
   apply( op: TREE_OPERATOR[T] ) is
      do
	 op.start  -- notify start of traversal
	 traverse(op,root)
	 op.finish  -- notify end of traversal
      end -- apply
   
feature {NONE}
   
   traverse( op: TREE_OPERATOR[T]; p: NODE[T] ) is
	 -- supply each node in subtree rooted at p to op.apply in the order 
	 -- specified by op.traversal
      do
	 if p /= Void then
	    if op.traversal = op.Preorder then
	       op.apply(p)
	       traverse(op,p.left)
	       traverse(op,p.right)
	    elseif op.traversal = op.Inorder then
	       traverse(op,p.left)
	       op.apply(p)
	       traverse(op,p.right)
	    else
	       traverse(op,p.left)
	       traverse(op,p.right)
	       op.apply(p)
	    end
	 end
      end -- traverse
   
end -- class TREE[T]