📄 page258.html
字号:
<HTML><HEAD><TITLE>Tree Traversals</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="tex2html4171" HREF="page259.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4169" HREF="page251.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4163" HREF="page257.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4173" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION009400000000000000000">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 commonthe characteristic that they systematically visit all the nodes in the tree.That is, the algorithm walks through the tree data structureand 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=15100> </A><A NAME=15101> </A>.<P>There are essentially two different methods in which tovisit 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 theyare 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 treein Figure <A HREF="page258.html#figtree5"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> as an example.The tree shown in the figure is a general tree in the senseof Definition <A HREF="page252.html#defntree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>:<P><A NAME="eqntreest"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation15109" SRC="img1094.gif" ><P>However, we can also consider the tree in Figure <A HREF="page258.html#figtree5"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>to be an <I>N</I>-ary tree (specifically, a binary treeif we assume the existence of empty trees at the appropriate positions:<P> <IMG WIDTH=495 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath63197" SRC="img1095.gif" ><P><P><P><A NAME="15240"> </A><A NAME="figtree5"> </A> <IMG WIDTH=575 HEIGHT=181 ALIGN=BOTTOM ALT="figure15113" SRC="img1096.gif" ><BR><STRONG>Figure:</STRONG> Sample tree.<BR><P><BR> <HR><UL> <LI> <A NAME="tex2html4174" HREF="page259.html#SECTION009401000000000000000">Preorder Traversal</A><LI> <A NAME="tex2html4175" HREF="page260.html#SECTION009402000000000000000">Postorder Traversal</A><LI> <A NAME="tex2html4176" HREF="page261.html#SECTION009403000000000000000">Inorder Traversal</A><LI> <A NAME="tex2html4177" HREF="page262.html#SECTION009404000000000000000">Breadth-First Traversal</A></UL><HR><A NAME="tex2html4171" HREF="page259.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4169" HREF="page251.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4163" HREF="page257.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4173" 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 + -