page334.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 49 行
HTML
49 行
<HTML><HEAD><TITLE>Inorder Traversal</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="tex2html5043" HREF="page335.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5041" HREF="page331.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5037" HREF="page333.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5045" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0010613000000000000000">Inorder Traversal</A></H3><P>Whereas inorder traversal of an <I>N</I>-ary tree is <em>not</em> defined for <I>N</I><I>></I>2,inorder traversal <em>is</em> defined for an <I>M</I>-way search tree:By definition, the inorder traversal of a search tree visitsall the keys contained in the search tree <em>in order</em>.<P>Program <A HREF="page334.html#progmWayTreeb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is an implementation ofthe algorithm for depth-first traversal of an <I>M</I>-way search treegiven in Section <A HREF="page309.html#secsrchtreetraversal"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The keys contained in a given node are visited(by calling the <tt>inVisit</tt> method of the visitor)<em>in between</em> the appropriate subtrees of that node.That is, key <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63737" SRC="img1177.gif" > is visited <em>in between</em> subtrees <IMG WIDTH=29 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline63735" SRC="img1176.gif" > and <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62823" SRC="img1051.gif" >.<P><P><A NAME="21034"> </A><A NAME="progmWayTreeb"> </A> <IMG WIDTH=575 HEIGHT=313 ALIGN=BOTTOM ALT="program20868" SRC="img1302.gif" ><BR><STRONG>Program:</STRONG> <tt>MWayTree</tt> class <tt>depthFirstTraversal</tt> method.<BR><P><P>In addition,the <tt>postVisit</tt> method is called on <IMG WIDTH=27 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline64777" SRC="img1303.gif" ><em>after</em> subtree <IMG WIDTH=29 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline63735" SRC="img1176.gif" > has been visited,and the <tt>preVisit</tt> method is called on <IMG WIDTH=26 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64781" SRC="img1304.gif" >before subtree <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62823" SRC="img1051.gif" > is visited.<P>It is clear that the amount of work done at each nodeduring the course of a depth-first traversalis proportional to the number of keys contained in that node.Therefore, the total running time for the depth-first traversal is <IMG WIDTH=341 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64785" SRC="img1305.gif" >,where <I>K</I> is the number of keys contained in the search tree.<P><HR><A NAME="tex2html5043" HREF="page335.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5041" HREF="page331.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5037" HREF="page333.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5045" 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 + -
显示快捷键?