Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint
Share this Page URL
Help

Chapter 13. Binary Trees > Expression Trees

13.3. Expression Trees

Arithmetic expressions such as (9+3)*(8-4) can be represented using an expression tree. An expression tree is a binary tree in which the operators are stored in the interior nodes and the operands (the variables or constant values) are stored in the leaves. Once constructed, an expression tree can be used to evaluate the expression or for converting an infix expression to either prefix or postfix notation.

Example 13.5. Breadth-first traversal on a binary tree.

1 def  breadthFirstTrav( bintree ):
2   # Create a queue and add the root node to it. 
3  Queue q
4  q.enqueue( bintree )
5
6   # Visit each node in the tree. 
7  while not  q.isEmpty( ) :
8   # Remove the next node from the queue and visit it. 
9   node = q.dequeue( )
10  print  ( node.data )
11
12   # Add the two children to the queue. 
13   if  node.left is not None  :
14    q.enqueue( node.left )
15   if  node.right is not None  :
16    q.enqueue( node.right )


  

You are currently reading a PREVIEW of this book.

                                                                                                                    

Get instant access to over $1 million worth of books and videos.

  

Start a Free Trial


  
  • Safari Books Online
  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint