page276.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 65 行
HTML
65 行
<HTML><HEAD><TITLE>General Trees</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="tex2html4382" HREF="page277.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4380" HREF="page267.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4374" HREF="page275.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4384" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION009630000000000000000">General Trees</A></H2><A NAME="sectreesgeneral"> </A><P>This section outlines an implementation of general treesin the sense of Definition <A HREF="page252.html#defntree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The salient features of the definition are first,that the nodes of a general tree have arbitrary degrees;and second, that there is no such thing as an empty tree.<P>The recursive nature of Definition <A HREF="page252.html#defntree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> has importantimplications when considering the implementation of such trees as containers.In effect, since a tree contains zero or more subtrees,when implemented as a container,we get a container which contains other containers!<P>Figure <A HREF="page276.html#figtree7"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the approach we have chosenfor implementing general trees.This figure shows how the general tree <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62791" SRC="img1048.gif" > in Figure <A HREF="page252.html#figtree1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>can be stored in memory.The basic idea is that each node has associated with it a linked listof the subtrees of that node.A linked list is used because there is no <em>a priori</em> restrictionon its length.This allows each node to have an arbitrary degree.Furthermore, since there are no empty trees,we need not worry about representing them.An important consequence of this is that the implementationnever makes use of the <tt>None</tt> reference!<P><P><A NAME="15968"> </A><A NAME="figtree7"> </A> <IMG WIDTH=575 HEIGHT=267 ALIGN=BOTTOM ALT="figure15798" SRC="img1120.gif" ><BR><STRONG>Figure:</STRONG> Representing general trees using linked lists.<BR><P><P>Program <A HREF="page276.html#proggeneralTreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces the <tt>GeneralTree</tt> classwhich is used to represent general treesas specified by Definition <A HREF="page252.html#defntree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The <tt>GeneralTree</tt> class extends the abstract <tt>Tree</tt> classintroduced in Program <A HREF="page267.html#progtreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="16085"> </A><A NAME="proggeneralTreea"> </A> <IMG WIDTH=575 HEIGHT=237 ALIGN=BOTTOM ALT="program15977" SRC="img1121.gif" ><BR><STRONG>Program:</STRONG> <tt>GeneralTree</tt> class <tt>__init__</tt> and <tt>purge</tt> methods.<BR><P><BR> <HR><UL> <LI> <A NAME="tex2html4385" HREF="page277.html#SECTION009631000000000000000">Instance Attributes</A><LI> <A NAME="tex2html4386" HREF="page278.html#SECTION009632000000000000000"><tt>__init__</tt> and <tt>Purge</tt> Methods</A><LI> <A NAME="tex2html4387" HREF="page279.html#SECTION009633000000000000000"><tt>getKey</tt> and <tt>GetSubtree</tt> Methods</A><LI> <A NAME="tex2html4388" HREF="page280.html#SECTION009634000000000000000"><tt>attachSubtree</tt> and <tt>detachSubtree</tt> Methods</A></UL><HR><A NAME="tex2html4382" HREF="page277.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4380" HREF="page267.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4374" HREF="page275.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4384" 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 + -
显示快捷键?