📄 page271.html
字号:
<HTML><HEAD><TITLE>Breadth-First 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="tex2html4329" HREF="page272.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4327" HREF="page268.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4321" HREF="page270.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4331" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION009613000000000000000">Breadth-First Traversal</A></H3><P>Program <A HREF="page271.html#progtreec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the <tt>breadthFirstTraversal</tt>method of the abstract <tt>Tree</tt> class.As defined in Section <A HREF="page258.html#sectreestraversals"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,a breadth-first traversal of a tree visits the nodesin the order of their depth in the tree andat each level the nodes are visited from left to right.<P><P><A NAME="15857"> </A><A NAME="progtreec"> </A> <IMG WIDTH=575 HEIGHT=313 ALIGN=BOTTOM ALT="program15697" SRC="img1117.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>Tree</tt> class <tt>breadthFirstTraversal</tt> method.<BR><P><P>We have already seen in Section <A HREF="page156.html#secqueuesapps"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> a non-recursivebreadth-first traversal algorithm for <I>N</I>-ary trees.This algorithm makes use of a queue as follows.Initially, the root node of the given tree is enqueued,provided it is not the empty tree.Then, the following steps are repeated until the queue is empty:<OL><LI> Remove the node at the head of the queue and call it <tt>head</tt>.<LI> Visit the object contained in <tt>head</tt>.<LI> Enqueue in order each non-empty subtree of <tt>head</tt>.</OL>Notice that empty trees are never put into the queue.Furthermore, it should be obvious that each node of the treeis enqueued exactly once.Therefore, it is also dequeue exactly once.Consequently, the running time for the breadth-first traversalis <IMG WIDTH=117 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60703" SRC="img667.gif" >.<P><HR><A NAME="tex2html4329" HREF="page272.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4327" HREF="page268.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4321" HREF="page270.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4331" 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 + -