📄 page263.html
字号:
<HTML><HEAD><TITLE>Expression Trees</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html4228" HREF="page264.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4226" HREF="page251.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4220" HREF="page262.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4230" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION009500000000000000000">Expression Trees</A></H1><A NAME="sectreesexprtrees"> </A><P>Algebraic expressions such as<P><A NAME="eqntreesexpr"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation15277" SRC="img1101.gif" ><P>have an inherent tree-like structure.For example,Figure <A HREF="page263.html#figtree6"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is a representationof the expression in Equation <A HREF="page263.html#eqntreesexpr"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.This kind of tree is calledan <em>expression tree</em><A NAME=15283> </A><A NAME=15284> </A>.<P>The terminal nodes (leaves) of an expression tree are the variablesor constants in the expression (<I>a</I>, <I>b</I>, <I>c</I>, <I>d</I>, and <I>e</I>).The non-terminal nodes of an expression tree are the operators(+, -, <IMG WIDTH=8 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline60753" SRC="img676.gif" >, and <IMG WIDTH=10 HEIGHT=18 ALIGN=MIDDLE ALT="tex2html_wrap_inline60923" SRC="img721.gif" >).Notice that the parentheses which appear in Equation <A HREF="page263.html#eqntreesexpr"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>do not appear in the tree.Nevertheless, the tree representation has captured the intent of theparentheses since the subtraction is lower in the tree than the multiplication.<P><P><A NAME="15439"> </A><A NAME="figtree6"> </A> <IMG WIDTH=575 HEIGHT=181 ALIGN=BOTTOM ALT="figure15286" SRC="img1102.gif" ><BR><STRONG>Figure:</STRONG> Tree representing the expression <I>a</I>/<I>b</I>+(<I>c</I>-<I>d</I>)<I>e</I>.<BR><P><P>The common algebraic operators are either unary or binary.For example, addition, subtraction, multiplication, and division are all binaryoperations and negation is a unary operation.Therefore, the non-terminal nodes of the corresponding expression treeshave either one or two non-empty subtrees.That is, expression trees are usually binary trees.<P>What can we do with an expression tree?Perhaps the simplest thing to do isto print the expression represented by the tree.Notice that an inorder traversal of the tree in Figure <A HREF="page263.html#figtree6"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>visits the nodes in the order<P> <IMG WIDTH=313 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath63217" SRC="img1103.gif" ><P>Except for the missing parentheses,this is precisely the order in which the symbols appearin Equation <A HREF="page263.html#eqntreesexpr"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>!<P>This suggests that an <em>inorder</em> traversalshould be used to print the expression.Consider an inorder traversal which,when it encounters a terminal node simply prints it out;and when it encounters a non-terminal node, does the following:<OL><LI> Print a left parenthesis; and then<LI> traverse the left subtree; and then<LI> print the root; and then<LI> traverse the right subtree; and then<LI> print a right parenthesis.</OL>Applying this procedure to the tree given in Figure <A HREF="page263.html#figtree6"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> we get<P><A NAME="eqntreesinfix"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation15448" SRC="img1104.gif" ><P>which, despite the redundant parentheses,represents exactly the same expression as Equation <A HREF="page263.html#eqntreesexpr"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><BR> <HR><UL> <LI> <A NAME="tex2html4231" HREF="page264.html#SECTION009501000000000000000">Infix Notation</A><LI> <A NAME="tex2html4232" HREF="page265.html#SECTION009502000000000000000">Prefix Notation</A><LI> <A NAME="tex2html4233" HREF="page266.html#SECTION009503000000000000000">Postfix Notation</A></UL><HR><A NAME="tex2html4228" HREF="page264.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4226" HREF="page251.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4220" HREF="page262.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4230" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -