A special kind of binary tree in which each leaf node contains a single operand. Each non-leaf  node contains a single binary operator. The left and right subtrees of an operator node represent subexpressions that must be evaluated before applying the operator at the root of the subtree.

—The levels of the nodes in the tree indicate their relative precedence of evaluation (we do not need parentheses to indicate precedence). —Operations at higher levels of the tree are evaluated later than those below them. —The operation at the root is always the last operation performed.

A Four-Level Binary Expression

A Binary Expression Tree

Its easy to generate the infix, prefix, postfix expressions using binary expression trees (how?)

In-order Traversal

(A + H) / (M – Y)

Pre-order Traversal

/ + A H – M Y

Post-order Traversal

A H + M Y – /


struct   TreeNode
    InfoNode     info ;   		// Data member
    TreeNode*   left ;   		// Pointer to left child
    TreeNode*   right ; 		// Pointer to right child

struct   InfoNode
    bool        type;    // ‘1’ means operator, ‘0’ means operand
    union				// ANONYMOUS union
	char    operation ;
   	int       operand ;

int   Eval ( TreeNode*  ptr )

{      switch  ( ptr->info.type )
	case 0 :  return  ptr->info.operand ;
	case 1 :
	    switch ( ptr->info.operation )
	        case  ‘+’  :  return  ( Eval ( ptr->left ) + Eval ( ptr->right ) ) ;

	        case  ‘-’  :  return  ( Eval ( ptr->left )  -  Eval ( ptr->right ) ) ;

 	        case  ‘*’  :  return  ( Eval ( ptr->left )  *  Eval ( ptr->right ) ) ;
	        case  ‘/’  :  return  ( Eval ( ptr->left )  /  Eval ( ptr->right ) ) ;

Building a Binary Expression Tree from an expression in prefix notation

—Insert new nodes, each time moving to the left until an operand has been inserted. —Backtrack to the last operator, and put the next node to its right. —Continue in the same pattern.

Tagged with: C/C++ languageData structures

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.