?? page269.html
字號(hào):
<HTML>
<HEAD>
<TITLE>Preorder, Inorder and Postorder Traversals</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html5253" HREF="page270.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page270.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html5251" HREF="page267.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page267.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html5245" HREF="page268.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page268.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html5255" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html5256" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H3><A NAME="SECTION0010612000000000000000">Preorder, Inorder and Postorder Traversals</A></H3>
<P>
Preorder, inorder and postorder traversals are special cases
of 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=16215> </A>,
which allows the single routine to provide all the needed functionality.
<P>
Suppose we have an instance of the <tt>PuttingVisitor</tt> class
(see Section <A HREF="page118.html#secadtsvisitors" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page118.html#secadtsvisitors"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>).
As shown in Program <A HREF="page120.html#progcontainer2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page120.html#progcontainer2c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>,
the <tt>PuttingVisitor</tt> class is derived from the abstract <tt>Visitor</tt>
base class and it provides a <tt>Visit</tt>
routine that prints every object it visits.
However, we cannot pass a <tt>PuttingVisitor</tt> instance
to the <tt>DepthFirstTraversal</tt> routine shown in Program <A HREF="page268.html#progtree1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page268.html#progtree1c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
because it expects a <tt>PrePostVisitor</tt> instance.
<P>
The problem is that the interface provided by the <tt>PuttingVisitor</tt>
does not match the interface expected by the <tt>DepthFirstTraversal</tt> routine.
The solution to this problem is to use an adapter.
An <em>adapter</em> converts the interface provided by one class
to the interface 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> member function
(provided by the <tt>PuttingVisitor</tt>).
Similarly, a postorder traversal is obtained by mapping
<tt>PostVisit</tt> to <tt>Visit</tt>.
<P>
<P><A NAME="16480"> </A><A NAME="progvisitor2h"> </A> <IMG WIDTH=575 HEIGHT=715 ALIGN=BOTTOM ALT="program16235" SRC="img1162.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1162.gif" ><BR>
<STRONG>Program:</STRONG> <tt>PrePostVisitor</tt>, <tt>PreOrder</tt>, <tt>InOrder</tt> and <tt>PostOrder</tt> Class Definitions<BR>
<P>
<P>
Program <A HREF="page269.html#progvisitor2h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page269.html#progvisitor2h"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> defines three adapter classes--<tt>PreOrder</tt>, <tt>PostOrder</tt> and <tt>InOrder</tt>.
All three classes are similar:
They are all derived from the <tt>Visitor</tt> abstract base class;
all have a single member variable that is a reference to a <tt>Visitor</tt>
class instance; and
all have a constructor that takes a <tt>Visitor</tt> reference
and initializes the member variable.
<P>
Each class provides a different interface mapping.
For example, the <tt>PreVisit</tt> member function of the <tt>PreVisit</tt>
simply calls the <tt>Visit</tt> function on the <tt>visitor</tt> member variable.
Notice that the adapter provides no functionality of its own--it simply forwards member function calls to the <tt>visitor</tt> instance
as required.
<P>
The following code fragment illustrates
how these adapters are used:
<PRE>PuttingVisitor v;
SomeTree t;
t.DepthFirstTraversal (PreOrder (v));
t.DepthFirstTraversal (InOrder (v));
t.DepthFirstTraversal (PostOrder (v));</PRE>
<P>
<HR><A NAME="tex2html5253" HREF="page270.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page270.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html5251" HREF="page267.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page267.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html5245" HREF="page268.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page268.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html5255" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html5256" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -