page255.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 190 行 · 第 1/2 页
HTML
190 行
<HTML>
<HEAD>
<TITLE>N-ary Trees</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="tex2html5070" HREF="page256.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page256.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="tex2html5068" 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="tex2html5062" HREF="page254.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page254.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="tex2html5072" 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="tex2html5073" 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="SECTION0010200000000000000000"><I>N</I>-ary Trees</A></H1>
<P>
In the preceding section we considered trees in which
the nodes can have arbitrary degrees.
In particular, the general case allows each of the nodes of a tree
to have a different degree.
In this section we consider a variation in which all of the
nodes of the tree are required to have exactly the same degree.
<P>
Unfortunately, simply adding to 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>
the additional requirement that all of the nodes of the tree
have the same degree does not work.
It is not possible to construct a tree which has a finite number of nodes
all 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=15301> </A><A NAME=15302> </A> <I>T</I>
is a finite set of <em>nodes</em><A NAME=15304> </A>
with the following properties:
<OL><LI> Either the set is empty, <IMG WIDTH=40 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline63628" SRC="img1112.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1112.gif" >; or<LI> The set consists of a root, <I>R</I>,
and exactly <I>N</I> distinct <I>N</I>-ary trees.
I.e., the remaining nodes are partitioned into <IMG WIDTH=43 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63636" SRC="img1113.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1113.gif" > subsets,
<IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63638" SRC="img1114.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1114.gif" >, <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63404" SRC="img1086.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1086.gif" >, ..., <IMG WIDTH=37 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline63642" SRC="img1115.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1115.gif" >, each of which is an <I>N</I>-ary tree
such that <IMG WIDTH=182 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63646" SRC="img1116.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1116.gif" >.
</OL></BLOCKQUOTE>
<P>
According to Definition <A HREF="page255.html#defnnarytree" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page255.html#defnnarytree"><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>,
an <I>N</I>-ary tree is either the empty tree, <IMG WIDTH=6 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline63650" SRC="img1117.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1117.gif" >,
or it is a non-empty set of nodes which consists of a root
and 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 consequence
of Definition <A HREF="page255.html#defnnarytree" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page255.html#defnnarytree"><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> that often goes unrecognized.
The empty tree, <IMG WIDTH=40 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline63628" SRC="img1112.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1112.gif" >, is a tree.
I.e., 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 a null pointer to represent an empty tree,
since a null pointer points to nothing at all!
<P>
The empty trees are called <em>external nodes</em><A NAME=15313> </A>
because they have no subtrees and therefore appear
at the extremities of the tree.
Conversely, the non-empty trees are called
<em>internal nodes</em><A NAME=15315> </A>.
<P>
Figure <A HREF="page255.html#figtree3" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page255.html#figtree3"><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> shows the following
<em>tertiary</em><A NAME=15318> </A><A NAME=15319> </A>
(<I>N</I>=3) trees:
<P> <IMG WIDTH=500 HEIGHT=111 ALIGN=BOTTOM ALT="eqnarray15320" SRC="img1118.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1118.gif" ><P>
In the figure, square boxes denote the empty trees
and circles denote non-empty nodes.
Except for the empty trees,
the tertiary trees shown in the figure contain the same sets of
nodes as the corresponding trees shown in Figure <A HREF="page251.html#figtree1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page251.html#figtree1"><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>
<P><A NAME="15495"> </A><A NAME="figtree3"> </A> <IMG WIDTH=575 HEIGHT=422 ALIGN=BOTTOM ALT="figure15323" SRC="img1119.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1119.gif" ><BR>
<STRONG>Figure:</STRONG> Examples of <I>N</I>-ary Trees<BR>
<P>
<P>
Definitions <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> and <A HREF="page255.html#defnnarytree" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page255.html#defnnarytree"><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> both define trees
in terms of sets.
In mathematics, elements of a set are normally unordered.
Therefore, we might conclude that that relative ordering of the
subtrees is not important.
However, most practical implementations of trees define
an 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_inline63670" SRC="img1120.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1120.gif" >
and
<IMG WIDTH=162 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63672" SRC="img1121.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1121.gif" >,
are considered to be distinct unequal trees.
Trees in which the subtrees are ordered are called
<em>ordered trees</em><A NAME=15501> </A><A NAME=15502> </A>.
On the other hand, trees in which the order does not matter
are called <em>oriented trees</em><A NAME=15504> </A><A NAME=15505> </A>.
In this book, we shall assume that all trees are ordered
unless otherwise specified.
<P>
Figure <A HREF="page255.html#figtree3" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page255.html#figtree3"><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> suggests that every <I>N</I>-ary tree contains
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?