page257.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 56 行
HTML
56 行
<HTML>
<HEAD>
<TITLE>Tree 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="tex2html5094" HREF="page258.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page258.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="tex2html5092" HREF="page250.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page250.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="tex2html5086" HREF="page256.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page256.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="tex2html5096" 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="tex2html5097" 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>
<H1><A NAME="SECTION0010400000000000000000">Tree Traversals</A></H1>
<A NAME="sectreestraversals"> </A>
<P>
There are many different applications of trees.
As a result, there are many different algorithms for manipulating them.
However, many of the different tree algorithms have in common
the characteristic that they systematically visit all the nodes in the tree.
I.e., the algorithm walks through the tree data structure
and performs some computation at each node in the tree.
This process of walking through the tree is called a
<em>tree traversal</em><A NAME=15721> </A><A NAME=15722> </A>.
<P>
There are essentially two different methods in which to
visit systematically all the nodes of a tree--<em>depth-first traversal</em> and <em>breadth-first traversal</em>.
Certain depth-first traversal methods occur frequently enough that they
are given names of their own:
<em>preorder traversal</em>,
<em>inorder traversal</em>
and <em>postorder traversal</em>.
<P>
The discussion that follows uses the tree
in Figure <A HREF="page257.html#figtree5" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page257.html#figtree5"><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 an example.
The tree shown in the figure is a general tree in the sense
of Definition <A HREF="page251.html#defntree" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page251.html#defntree"><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>:
<P><A NAME="eqntreest"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation15730" SRC="img1142.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1142.gif" ><P>
However, we can also consider the tree in Figure <A HREF="page257.html#figtree5" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page257.html#figtree5"><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>
to be an <I>N</I>-ary tree (specifically, a binary tree
if we assume the existence of empty trees at the appropriate positions:
<P> <IMG WIDTH=494 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath63834" SRC="img1143.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1143.gif" ><P>
<P>
<P><A NAME="15861"> </A><A NAME="figtree5"> </A> <IMG WIDTH=575 HEIGHT=181 ALIGN=BOTTOM ALT="figure15734" SRC="img1144.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1144.gif" ><BR>
<STRONG>Figure:</STRONG> Sample Tree<BR>
<P><BR> <HR>
<UL>
<LI> <A NAME="tex2html5098" HREF="page258.html#SECTION0010401000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page258.html#SECTION0010401000000000000000">Preorder Traversal</A>
<LI> <A NAME="tex2html5099" HREF="page259.html#SECTION0010402000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page259.html#SECTION0010402000000000000000">Postorder Traversal</A>
<LI> <A NAME="tex2html5100" HREF="page260.html#SECTION0010403000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page260.html#SECTION0010403000000000000000">Inorder Traversal</A>
<LI> <A NAME="tex2html5101" HREF="page261.html#SECTION0010404000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page261.html#SECTION0010404000000000000000">Breadth-First Traversal</A>
</UL>
<HR><A NAME="tex2html5094" HREF="page258.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page258.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="tex2html5092" HREF="page250.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page250.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="tex2html5086" HREF="page256.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page256.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="tex2html5096" 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="tex2html5097" 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>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?