page273.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 72 行
HTML
72 行
<HTML><HEAD><TITLE>Tree Iterators</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="tex2html4349" HREF="page274.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4347" HREF="page267.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4341" HREF="page272.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4351" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION009620000000000000000">Tree Iterators</A></H2><P>This section describes the implementation of an iteratorwhich can be used to step through the contents of any tree instance.For example, suppose we have declared a variable <tt>tree</tt>which refers to a <tt>BinaryTree</tt>.Then we can view the <tt>tree</tt> instance as a containerand print its contents as follows:<PRE>tree = BinaryTree()# ...it = iter(tree)while True: try: print it.next() except StopIteration: break</PRE>The loop above can also be written using a Python <tt>for</tt> loop like this:<PRE>for obj in tree: print obj</PRE><P>Every concrete class that extends the abstract <tt>Container</tt> classmust provide an <tt>__iter__</tt> method.This method returns an instance of a class that extendsthe abstract <tt>Iterator</tt> class defined in Section <A HREF="page121.html#secadtsiterators"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The iterator can then be used to systematically visit the contentsof the associated container.<P>We have already seen that when we systematically visit the nodes of a tree,we are doing a tree traversal.Therefore, the implementation of the iterator must also do a tree traversal.However, there is a catch.A recursive tree traversal method such as <tt>depthFirstTraversal</tt>keeps track of where it is <em>implicitly</em>using the Python virtual machine stack.However, when we implement an iteratorwe must keep track of the state of the traversal <em>explicitly</em>.This section presents an iterator implementation which doesa preorder traversal of the tree and keeps track of the current stateof the traversal using a stack from Chapter <A HREF="page130.html#chapstacks"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P>Program <A HREF="page273.html#progtreee"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the nested class <tt>Tree.Iterator</tt>.The <tt>Tree.Iterator</tt> class extendsthe abstract <tt>Iterator</tt> class defined in Section <A HREF="page121.html#secadtsiterators"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The <tt>Iterator</tt> contains two instance attributes--<tt>_container</tt> and <tt>_stack</tt>.As shown in Program <A HREF="page273.html#progtreee"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the <tt>__iter__</tt> method of the abstract <tt>Tree</tt> classreturns a new instance of the <tt>Tree.Iterator</tt> class each time it is called.<P><P><A NAME="15862"> </A><A NAME="progtreee"> </A> <IMG WIDTH=575 HEIGHT=504 ALIGN=BOTTOM ALT="program15756" SRC="img1119.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>Tree</tt> class <tt>__iter__</tt> method and the <tt>Tree.Iterator</tt> class.<BR><P><BR> <HR><UL> <LI> <A NAME="tex2html4352" HREF="page274.html#SECTION009621000000000000000"><tt>__init__</tt> Method</A><LI> <A NAME="tex2html4353" HREF="page275.html#SECTION009622000000000000000"><tt>next</tt> Method</A></UL><HR><A NAME="tex2html4349" HREF="page274.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4347" HREF="page267.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4341" HREF="page272.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4351" 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 + =
减小字号Ctrl + -
显示快捷键?