page355.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 83 行
HTML
83 行
<HTML><HEAD><TITLE>Complete 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="tex2html5281" HREF="page356.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5279" HREF="page354.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5275" HREF="page354.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5283" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0011211000000000000000">Complete <I>N</I>-ary Trees</A></H3><P>The definition for complete binary trees can be easily extendedto trees with arbitrary fixed degree <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65659" SRC="img1396.gif" > as follows:<P><BLOCKQUOTE> <b>Definition (Complete <I>N</I>-ary Tree)</b><A NAME="defncompletent"> </A>A <em>complete <I>N</I>-ary tree</em><A NAME=23703> </A><A NAME=23757> </A>of height <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63063" SRC="img1074.gif" >,is an <I>N</I>-ary tree <IMG WIDTH=170 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65671" SRC="img1397.gif" >with the following properties.<OL><LI> If <I>h</I>=0, <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65675" SRC="img1398.gif" > for all <I>i</I>, <IMG WIDTH=70 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65679" SRC="img1399.gif" >.<LI> For <I>h</I><I>></I>0 there exists a <I>j</I>, <IMG WIDTH=72 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65685" SRC="img1400.gif" > such that <OL><LI> <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62823" SRC="img1051.gif" > is a perfect <I>N</I>-ary tree of height <I>h</I>-1 for all <IMG WIDTH=81 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65693" SRC="img1401.gif" >;<LI> <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline62845" SRC="img1054.gif" > is a complete <I>N</I>-ary tree of height <I>h</I>-1; and,<LI> <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62823" SRC="img1051.gif" > is a perfect <I>N</I>-ary tree of height <I>h</I>-2 for all <I>i</I>:<I>j</I><I><</I><I>i</I><I><</I><I>N</I>. </OL></OL></BLOCKQUOTE><P>Note that while it is expressed in somewhat different terms,the definition of a complete <I>N</I>-ary tree is consistentwith the definition of a binary tree for <I>N</I>=2.Figure <A HREF="page355.html#figtree17"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows an example of a complete ternary (<I>N</I>=3) tree.<P><P><A NAME="24002"> </A><A NAME="figtree17"> </A> <IMG WIDTH=575 HEIGHT=181 ALIGN=BOTTOM ALT="figure23712" SRC="img1402.gif" ><BR><STRONG>Figure:</STRONG> A complete ternary tree.<BR><P><P>Informally, a complete tree is a tree in which all the levelsare full except for the bottom leveland the bottom level is filled from left to right.For example in Figure <A HREF="page355.html#figtree17"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the first three levels are full.The fourth level which comprises nodes 14-21is partially full and has been filled from left to right.<P>The main advantage of using complete binary trees is thatthey can be easily stored in an array.Specifically, consider the nodes of a complete treenumbered consecutively in <em>level-order</em><A NAME=24007> </A> as they arein Figures <A HREF="page354.html#figtree16"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page355.html#figtree17"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.There is a simple formula that relates the number of a nodewith the number of its parentand the numbers of its children.<P>Consider the case of a complete binary tree.The root node is node 1 and its children are nodes 2 and 3.In general, the children of node <I>i</I> are 2<I>i</I> and 2<I>i</I>+1.Conversely, the parent of node <I>i</I> is <IMG WIDTH=31 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65723" SRC="img1403.gif" >.Figure <A HREF="page355.html#figheap1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates this idea by showing howthe complete binary tree shown in Figure <A HREF="page354.html#figtree16"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is mapped into an array.<P><P><A NAME="24259"> </A><A NAME="figheap1"> </A> <IMG WIDTH=575 HEIGHT=194 ALIGN=BOTTOM ALT="figure24012" SRC="img1404.gif" ><BR><STRONG>Figure:</STRONG> Array representation of a complete binary tree.<BR><P><P>A remarkable characteristic of complete trees is that filling the bottom levelfrom left to right corresponds to adding elements at the end of the array!Thus, a complete tree containing <I>n</I> nodes occupies the first<I>n</I> consecutive array positions.<P>The array subscript calculations given abovecan be easily generalized to complete <I>N</I>-ary trees.Assuming that the root occupies position 1 of the array,its <I>N</I> children occupy positions 2, 3, ..., <I>N</I>+1.In general, the children of node <I>i</I> occupy positions<P> <IMG WIDTH=431 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath65653" SRC="img1405.gif" ><P>and the parent of node <I>i</I> is found at<P> <IMG WIDTH=291 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath65654" SRC="img1406.gif" ><P><HR><A NAME="tex2html5281" HREF="page356.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5279" HREF="page354.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5275" HREF="page354.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5283" 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 + -
显示快捷键?