📄 page256.html
字号:
<HTML><HEAD><TITLE>N-ary 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="tex2html4149" HREF="page257.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4147" HREF="page251.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4141" HREF="page255.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4151" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION009200000000000000000"><I>N</I>-ary Trees</A></H1><P>In the preceding section we considered trees in whichthe nodes can have arbitrary degrees.In particular, the general case allows each of the nodes of a treeto have a different degree.In this section we consider a variation in which all of thenodes of the tree are required to have exactly the same degree.<P>Unfortunately, simply adding to Definition <A HREF="page252.html#defntree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>the additional requirement that all of the nodes of the treehave the same degree does not work.It is not possible to construct a tree which has a finite number of nodesall of which have the same degree <I>N</I>in any case except the trivial case of <I>N</I>=0.In order to make it work,we need to introduce the notion of an empty tree as follows:<P><BLOCKQUOTE> <b>Definition (<I>N</I>-ary Tree)</b><A NAME="defnnarytree"> </A>An <em><I>N</I>-ary tree</em><A NAME=14672> </A><A NAME=14673> </A> <I>T</I>is a finite set of <em>nodes</em><A NAME=14675> </A>with the following properties:<OL><LI> Either the set is empty, <IMG WIDTH=40 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline62991" SRC="img1064.gif" >; or<LI> The set consists of a root, <I>R</I>, and exactly <I>N</I> distinct <I>N</I>-ary trees. That is, the remaining nodes are partitioned into <IMG WIDTH=44 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62999" SRC="img1065.gif" > subsets, <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63001" SRC="img1066.gif" >, <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62767" SRC="img1038.gif" >, ..., <IMG WIDTH=36 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline63005" SRC="img1067.gif" >, each of which is an <I>N</I>-ary tree such that <IMG WIDTH=180 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63009" SRC="img1068.gif" >.</OL></BLOCKQUOTE><P>According to Definition <A HREF="page256.html#defnnarytree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,an <I>N</I>-ary tree is either the empty tree, <IMG WIDTH=6 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline63013" SRC="img1069.gif" >,or it is a non-empty set of nodes which consists of a rootand exactly <I>N</I> subtrees.Clearly, the empty set contains neither a root, nor any subtrees.Therefore, the degree of each node of an <I>N</I>-ary tree is either zero or <I>N</I>.<P>There is subtle, yet extremely important consequenceof Definition <A HREF="page256.html#defnnarytree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> that often goes unrecognized.The empty tree, <IMG WIDTH=40 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline62991" SRC="img1064.gif" >, is a tree.That is, it is an object of the same type as a non-empty tree.Therefore, from the perspective of object-oriented program design,an empty tree must be an instance of some object class.It is inappropriate to use the <tt>None</tt> reference to represent an empty tree,since the <tt>None</tt> reference refers to nothing at all!<P>The empty trees are called <em>external nodes</em><A NAME=14686> </A>because they have no subtrees and therefore appearat the extremities of the tree.Conversely, the non-empty trees are called<em>internal nodes</em><A NAME=14688> </A>.<P>Figure <A HREF="page256.html#figtree3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the following<em>tertiary</em><A NAME=14691> </A><A NAME=14692> </A>(<I>N</I>=3) trees:<P> <IMG WIDTH=500 HEIGHT=112 ALIGN=BOTTOM ALT="eqnarray14693" SRC="img1070.gif" ><P>In the figure, square boxes denote the empty treesand circles denote non-empty nodes.Except for the empty trees,the tertiary trees shown in the figure contain the same sets ofnodes as the corresponding trees shown in Figure <A HREF="page252.html#figtree1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="14868"> </A><A NAME="figtree3"> </A> <IMG WIDTH=575 HEIGHT=419 ALIGN=BOTTOM ALT="figure14696" SRC="img1071.gif" ><BR><STRONG>Figure:</STRONG> Examples of <I>N</I>-ary trees.<BR><P><P>Definitions <A HREF="page252.html#defntree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page256.html#defnnarytree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> both define treesin terms of sets.In mathematics, elements of a set are normally unordered.Therefore, we might conclude that the relative ordering of thesubtrees is not important.However, most practical implementations of trees definean implicit ordering of the subtrees.Consequently, it is usual to assume that the subtrees are ordered.As a result, the two tertiary trees, <IMG WIDTH=169 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63033" SRC="img1072.gif" >and <IMG WIDTH=162 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63035" SRC="img1073.gif" >,are considered to be distinct unequal trees.Trees in which the subtrees are ordered are called<em>ordered trees</em><A NAME=14874> </A><A NAME=14875> </A>.On the other hand, trees in which the order does not matterare called <em>oriented trees</em><A NAME=14877> </A><A NAME=14878> </A>.In this book, we shall assume that all trees are orderedunless otherwise specified.<P>Figure <A HREF="page256.html#figtree3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> suggests that every <I>N</I>-ary tree containsa significant number of external nodes.The following theorem tells us precisely how many external nodes we can expect:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremtreesi"> </A>An <I>N</I>-ary tree with <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" > internal nodescontains (<I>N</I>-1)<I>n</I>+1 external nodes.</BLOCKQUOTE><P> extbfProofLet the number of external nodes be <I>l</I>.Since every node except the root (empty or not) has a parent,there must be (<I>n</I>+<I>l</I>-1)/<I>N</I> parents in the treesince every parent has <I>N</I> children.Therefore, <I>n</I>=(<I>n</I>+<I>l</I>-1)/<I>N</I>.Rearranging this gives <I>l</I>=(<I>N</I>-1)<I>n</I>+1.<P>Since the external nodes have no subtrees,it is tempting to consider them to be the leaves of the tree.However, in the context of <I>N</I>-ary trees,it is customary to define a <em>leaf node</em><A NAME=14886> </A>as an internal node which has only external subtrees.According to this definition,the trees shown in Figure <A HREF="page256.html#figtree3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> have exactly the samesets of leaves as the correspondinggeneral trees shown in Figure <A HREF="page252.html#figtree1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P>Furthermore, since height is defined with respect to the leaves,by having the leaves the same for both kinds of trees,the heights are also the same.The following theorem tells us something aboutthe maximum size of a tree of a given height <I>h</I>:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremtreesii"> </A>Consider an <I>N</I>-ary tree <I>T</I> of height <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63063" SRC="img1074.gif" >.The maximum number of internal nodes in <I>T</I> is given by<P> <IMG WIDTH=285 HEIGHT=35 ALIGN=BOTTOM ALT="displaymath62969" SRC="img1075.gif" ><P></BLOCKQUOTE><P> extbfProof (By induction).<P><b>Base Case</b>Consider an <I>N</I>-ary tree of height zero.It consists of exactly one internal node and <I>N</I> empty subtrees.Clearly the theorem holds for <I>h</I>=0 since<P> <IMG WIDTH=315 HEIGHT=40 ALIGN=BOTTOM ALT="displaymath62970" SRC="img1076.gif" ><P><P><b>Inductive Hypothesis</b>Suppose the theorem holds for <IMG WIDTH=111 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63073" SRC="img1077.gif" >, for some <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60883" SRC="img708.gif" >.Consider a tree of height <I>k</I>+1.Such a tree consists of a root and <I>N</I> subtrees each of whichcontains at most <IMG WIDTH=138 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline63081" SRC="img1078.gif" > nodes.Therefore, altogether the number of nodes is at most<P> <IMG WIDTH=500 HEIGHT=40 ALIGN=BOTTOM ALT="equation14902" SRC="img1079.gif" ><P>That is, the theorem holds for <I>k</I>+1.Therefore, by induction on <I>k</I>,the theorem is true for all values of <I>h</I>.<P>An interesting consequence of Theorems <A HREF="page256.html#theoremtreesi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page256.html#theoremtreesii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is that the maximum number of external nodesin an <I>N</I>-ary tree of height <I>h</I> is given by<P> <IMG WIDTH=370 HEIGHT=40 ALIGN=BOTTOM ALT="displaymath62971" SRC="img1080.gif" ><P><P>The final theorem of this section addresses the maximum number of <em>leaves</em>in an <I>N</I>-ary tree of height <I>h</I>:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremtreesiii"> </A>Consider an <I>N</I>-ary tree <I>T</I> of height <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63063" SRC="img1074.gif" >.The maximum number of leaf nodes in <I>T</I> is <IMG WIDTH=22 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline63105" SRC="img1081.gif" >.</BLOCKQUOTE><P> extbfProof (By induction).<P><b>Base Case</b>Consider an <I>N</I>-ary tree of height zero.It consists of exactly one internal node which has <I>N</I> empty subtrees.Therefore, the one node is a leaf.Clearly the theorem holds for <I>h</I>=0 since <IMG WIDTH=50 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline63113" SRC="img1082.gif" >.<P><b>Inductive Hypothesis</b>Suppose the theorem holds for <IMG WIDTH=111 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63073" SRC="img1077.gif" >, for some <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60883" SRC="img708.gif" >.Consider a tree of height <I>k</I>+1.Such a tree consists of a root and <I>N</I> subtrees each of whichcontains at most <IMG WIDTH=21 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline63123" SRC="img1083.gif" > leaf nodes.Therefore, altogether the number of leaves is at most <IMG WIDTH=114 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63125" SRC="img1084.gif" >.That is, the theorem holds for <I>k</I>+1.Therefore, by induction on <I>k</I>,the theorem is true for all values of <I>h</I>.<P><HR><A NAME="tex2html4149" HREF="page257.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4147" HREF="page251.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4141" HREF="page255.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4151" 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 + -