page252.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 86 行
HTML
86 行
<HTML><HEAD><TITLE>Basics</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="tex2html4104" HREF="page253.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4102" HREF="page251.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4096" HREF="page251.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4106" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION009100000000000000000">Basics</A></H1><P>The following is a mathematical definition of a tree:<P><BLOCKQUOTE> <b>Definition (Tree)</b><A NAME="defntree"> </A>A <em>tree</em><A NAME=14217> </A> <I>T</I>is a finite, non-empty set of <em>nodes</em><A NAME=14219> </A>,<P> <IMG WIDTH=350 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath62759" SRC="img1037.gif" ><P>with the following properties:<OL><LI> A designated node of the set, <I>r</I>, is called the <em>root</em><A NAME=14222> </A> of the tree; and<LI> The remaining nodes are partitioned into <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" > subsets, <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62767" SRC="img1038.gif" >, <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62769" SRC="img1039.gif" >, ..., <IMG WIDTH=17 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62771" SRC="img1040.gif" >, each of which is a tree.</OL>For convenience,we shall use the notation <IMG WIDTH=155 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62773" SRC="img1041.gif" > to denote the tree <I>T</I>.</BLOCKQUOTE><P>Notice that Definition <A HREF="page252.html#defntree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is <em>recursive</em>--a tree is defined in terms of itself!Fortunately, we do not have a problem with infinite recursionbecause every tree has a <em>finite</em> number of of nodesand because in the base case a tree has <I>n</I>=0 subtrees.<P>It follows from Definition <A HREF="page252.html#defntree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>that the minimal tree is a tree comprised of a single root node.For example <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62779" SRC="img1042.gif" > is such a tree.When there is more than one node,the remaining nodes are partitioned into subtrees.For example, the <IMG WIDTH=101 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62781" SRC="img1043.gif" > is a tree which is comprised ofthe root node <I>B</I> and the subtree <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62785" SRC="img1044.gif" >.Finally, the following is also a tree<P><A NAME="eqntreestc"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation14229" SRC="img1045.gif" ><P><P>How do <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62787" SRC="img1046.gif" >, <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62789" SRC="img1047.gif" >, and <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62791" SRC="img1048.gif" > resemble their arboreal namesake?The similarity becomes apparent when we consider the graphicalrepresentation of these trees shown in Figure <A HREF="page252.html#figtree1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.To draw such a pictorial representation of a tree, <IMG WIDTH=155 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62773" SRC="img1041.gif" >,the following recursive procedure is used:First, we first draw the root node <I>r</I>.Then, we draw each of the subtrees, <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62767" SRC="img1038.gif" >, <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62769" SRC="img1039.gif" >, ..., <IMG WIDTH=17 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62771" SRC="img1040.gif" >,beside each other below the root.Finally, lines are drawn from <I>r</I> to the roots of each of the subtrees.<P><P><A NAME="14440"> </A><A NAME="figtree1"> </A> <IMG WIDTH=575 HEIGHT=207 ALIGN=BOTTOM ALT="figure14233" SRC="img1049.gif" ><BR><STRONG>Figure:</STRONG> Examples of trees.<BR><P><P>Of course, trees drawn in this fashion are upside down.Nevertheless, this is the conventional wayin which tree data structures are drawn.In fact, it is understood that when we speak of ``up'' and ``down,''we do so with respect to this pictorial representation.For example, when we move from a root to a subtree,we will say that we are moving <em>down</em> the tree.<P>The inverted pictorial representation of trees is probably due tothe way that genealogical <em>lineal charts</em> are drawn.A <em>lineal chart</em> is a family treethat shows the descendants of some person.And it is from genealogy that much of the terminology associatedwith tree data structures is taken.<P><BR> <HR><UL> <LI> <A NAME="tex2html4107" HREF="page253.html#SECTION009101000000000000000">Terminology</A><LI> <A NAME="tex2html4108" HREF="page254.html#SECTION009102000000000000000">More Terminology</A><LI> <A NAME="tex2html4109" HREF="page255.html#SECTION009103000000000000000">Alternate Representations for Trees</A></UL><HR><A NAME="tex2html4104" HREF="page253.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4102" HREF="page251.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4096" HREF="page251.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4106" 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 + -
显示快捷键?