📄 page270.html
字号:
<HTML><HEAD><TITLE>Preorder, Inorder, and Postorder Traversals</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="tex2html4318" HREF="page271.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4316" HREF="page268.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4310" HREF="page269.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4320" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION009612000000000000000">Preorder, Inorder, and Postorder Traversals</A></H3><P>Preorder, inorder, and postorder traversals are special casesof the more general depth-first traversal described in the preceding section.Rather than implement each of these traversals directly,we make use a design pattern pattern, called <em>adapter</em><A NAME=15618> </A>,which allows the single method to provide all the needed functionality.<P>Suppose we have an instance of the <tt>PrintingVisitor</tt> class(see Section <A HREF="page123.html#secadtsvisitors"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).The <tt>PrintingVisitor</tt> class extends the <tt>Visitor</tt> class.However, we cannot pass a <tt>PrintingVisitor</tt> instanceto the <tt>DepthFirstTraversal</tt> method shown in Program <A HREF="page269.html#progtreeb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>because it expects an object that extendsthe <tt>PrePostVisitor</tt> class.<P>The problem is that the protocol implemented by the <tt>PrintingVisitor</tt>does not match the protocol expected by the <tt>DepthFirstTraversal</tt> method.The solution to this problem is to use an adapter.An <em>adapter</em><A NAME=15630> </A> converts the protocol provided by one classto the protocol required by another.For example, if we want a preorder traversal,then the call to the <tt>preVisit</tt>(made by <tt>depthFirstTraversal</tt>)should be mapped to the <tt>visit</tt> method(provided by the <tt>PrintingVisitor</tt>).Similarly, a postorder traversal is obtained by mapping<tt>postVisit</tt> to <tt>visit</tt>.<P>Programs <A HREF="page270.html#progpreOrdera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, <A HREF="page270.html#proginOrdera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page270.html#progpostOrdera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> define three adapter classes--<tt>PreOrder</tt>, <tt>InOrder</tt>, and <tt>PostOrder</tt>.All three classes are similar:They all extend the <tt>PrePostVisitor</tt> classdefined in Program <A HREF="page269.html#progprePostVisitora"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>;all have a single instance attribute that refers to a <tt>Visitor</tt>; andall have a <tt>__init__</tt> method that takes a <tt>Visitor</tt>.<P><P><A NAME="15842"> </A><A NAME="progpreOrdera"> </A> <IMG WIDTH=575 HEIGHT=219 ALIGN=BOTTOM ALT="program15648" SRC="img1114.gif" ><BR><STRONG>Program:</STRONG> <tt>PreOrder</tt> class.<BR><P><P><P><A NAME="15847"> </A><A NAME="proginOrdera"> </A> <IMG WIDTH=575 HEIGHT=219 ALIGN=BOTTOM ALT="program15661" SRC="img1115.gif" ><BR><STRONG>Program:</STRONG> <tt>InOrder</tt> class.<BR><P><P><P><A NAME="15852"> </A><A NAME="progpostOrdera"> </A> <IMG WIDTH=575 HEIGHT=219 ALIGN=BOTTOM ALT="program15674" SRC="img1116.gif" ><BR><STRONG>Program:</STRONG> <tt>PostOrder</tt> class.<BR><P><P>Each class provides a different interface mapping.For example, the <tt>preVisit</tt> method of the <tt>PreOrder</tt> classsimply calls the <tt>visit</tt> method on the <tt>_visitor</tt> instance attribute.Notice that the adapter provides no functionality of its own--it simply forwards method calls to the <tt>_visitor</tt> instance as required.<P>The following code fragment illustrateshow these adapters are used:<PRE>v = PrintingVisitor()t = SomeTree()# ...t.depthFirstTraversal(preOrder(v))t.depthFirstTraversal(inOrder(v))t.depthFirstTraversal(postOrder(v))</PRE><P><HR><A NAME="tex2html4318" HREF="page271.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4316" HREF="page268.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4310" HREF="page269.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4320" 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 + -