📄 page309.html

📁 Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and
💻 HTML
字号:
<HTML><HEAD><TITLE>Traversing a Search Tree</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="tex2html4759" HREF="page310.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4757" HREF="page305.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4753" HREF="page308.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html4761" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0010340000000000000000">Traversing a Search Tree</A></H2><A NAME="secsrchtreetraversal">&#160;</A><P>In Section&nbsp;<A HREF="page258.html#sectreestraversals"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the inorder traversal of a binary tree is defined as follows:<OL><LI> Traverse the left subtree; and then<LI> visit the root; and then<LI> traverse the right subtree.</OL>It should not come as a surprise that whenan <em>inorder traversal</em><A NAME=18589>&#160;</A><A NAME=18590>&#160;</A>of a binary search tree is done,the nodes of the tree are visited <em>in order</em>!<P>In an inorder traversal the root of the tree is visited afterthe entire left subtree has been traversedand in a binary search tree everything in the left subtreeis less than the root.Therefore, the root is visited only after all the keysless than the root have been visited.<P>Similarly, in an inorder traversal the root is visited before the rightsubtree is traversed and everything in the right subtreeis greater than the root.Hence, the root is visited before all the keys greater than the rootare visited.Therefore, by induction, the keys in the search tree are visited in order.<P>Inorder traversal is not defined for arbitrary <I>N</I>-ary trees--it is only defined for the case of <I>N</I>=2.Essentially this is because the nodes of <I>N</I>-ary treescontain only a single key.On the other hand, if a node of an <I>M</I>-way search tree has <I>n</I> subtrees,then it must contain <I>n</I>-1 keys, such that  <IMG WIDTH=76 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64101" SRC="img1230.gif"  >.Therefore, we can define<em>inorder traversal of an <I>M</I>-way tree</em><A NAME=18593>&#160;</A> as follows:<P>To traverse a node of an <I>M</I>-way tree having <I>n</I> subtrees,<DL COMPACT><DT><DD> Traverse  <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63001" SRC="img1066.gif"  >; and then    <DT><DD> visit  <IMG WIDTH=13 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63723" SRC="img1169.gif"  >; and then    <DT><DD> traverse  <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62767" SRC="img1038.gif"  >; and then    <DT><DD> visit  <IMG WIDTH=13 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63725" SRC="img1170.gif"  >; and then    <DT><DD> traverse  <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62769" SRC="img1039.gif"  >; and then    <DT><STRONG> <IMG WIDTH=2 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline64121" SRC="img1231.gif"  ></STRONG><DD>    <DT><STRONG>2<I>n</I>-2. </STRONG><DD> visit  <IMG WIDTH=31 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline63727" SRC="img1171.gif"  >; and then    <DT><STRONG>2<I>n</I>-1. </STRONG><DD> traverse  <IMG WIDTH=32 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline63719" SRC="img1168.gif"  >.<P> </DL><HR><A NAME="tex2html4759" HREF="page310.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4757" HREF="page305.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4753" HREF="page308.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html4761" 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 &#169; 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 + -