📄 ds6.1.htm
字号:
当树<span lang="EN-US">T中结点个数n≤1时，R＝Φ；当树T中结点个数n>1时有：<o:p>
</o:p>
</span></font></span></b></p>
<p class="MsoNormal" style="margin-left:21.0pt"><font face="宋体"><b><span style="mso-spacerun: yes; mso-hansi-font-family: Times New Roman" lang="EN-US"><font size="5" color="#FFFFFF">
</font></span></b><span lang="EN-US" style="mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFFFF"><b>R＝{<Root，r</b></font></span><b><font size="5" color="#FFFFFF"><sub><span lang="EN-US">i</span></sub><span lang="EN-US" style="mso-hansi-font-family: Times New Roman">>，i＝1，2，</span><span lang="EN-US" style="mso-ascii-font-family:
宋体">…</span><span style="mso-hansi-font-family: Times New Roman">，<span lang="EN-US">m}<o:p>
</o:p>
</span></span></font></b></font></p>
<p class="MsoNormal"><b><span style="mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFFFF" face="宋体">其中，<span lang="EN-US">Root为树T的根结点，r</span></font></span><font size="5" color="#FFFFFF" face="宋体"><sub><span lang="EN-US">i</span></sub><span style="mso-hansi-font-family: Times New Roman">是树<span lang="EN-US">T的根结点Root的子树T</span></span><sub><span lang="EN-US">i</span></sub><span style="mso-hansi-font-family: Times New Roman">的根结点。<span lang="EN-US"><o:p>
</o:p>
</span></span></font></b></p>
<p class="MsoNormal" style="margin-left:21.0pt"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFFFF" face="宋体">树定义的形式化，主要用于树的理论描述。</font></span></b></p>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font face="宋体"><b><font size="5" color="#FFFFFF">
</font></b></font></span><font face="宋体"><b><font size="5" color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">图</span><span lang="EN-US">7.1(a)</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">是一棵具有</span><span lang="EN-US">9</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">个结点的树，即</span><span lang="EN-US">T</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">＝</span><span lang="EN-US">{A</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，</span><span lang="EN-US">B</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，</span><span lang="EN-US">C</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，</span><span lang="EN-US">…</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，</span><span lang="EN-US">H</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，</span><span lang="EN-US">I}</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，结点</span><span lang="EN-US">A</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">为树</span><span lang="EN-US">T</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">的根结点，除根结点</span><span lang="EN-US">A</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">之外的其余结点分为两个不相交的集合：</span><span lang="EN-US">T<sub>1</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">＝</span><span lang="EN-US">{B,D,E,F,H,I}</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">和</span><span lang="EN-US">T<sub>2</sub>={C,G}</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，</span><span lang="EN-US">T<sub>1</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">和</span><span lang="EN-US">T<sub>2</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">构成了结点</span><span lang="EN-US">A</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">的两棵子树，</span><span lang="EN-US">T<sub>1</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">和</span><span lang="EN-US">T<sub>2</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">本身也分别是一棵树。例如，子树</span><span lang="EN-US">T<sub>1</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">的根结点为</span><span lang="EN-US">B</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，其余结点又分为两个不相交的集合：</span><span lang="EN-US">T<sub>11</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">＝</span><span lang="EN-US">{D}</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，</span><span lang="EN-US">T<sub>12</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">＝</span><span lang="EN-US">{E,H,I}</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">和</span><span lang="EN-US">T<sub>13</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">＝</span><span lang="EN-US">{F}</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">。</span><span lang="EN-US">T<sub>11</sub></span><sub><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">、</span></sub><span lang="EN-US">T<sub>12</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">和</span><span lang="EN-US">T<sub>13</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">构成了子树</span><span lang="EN-US">T<sub>1</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">的根结点</span><span lang="EN-US">B</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">的三棵子树。如此可继续向下分为更小的子树，直到每棵子树只有一个根结点为止。</span></font></b></font></p>
<p class="MsoNormal" style="margin-left: 0"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFFFF" face="宋体">
从树的定义和图</font></span><font size="5" color="#FFFFFF" face="宋体"><span lang="EN-US">7.1(a)</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">的示例可以看出，树具有下面两个特点：</span></font></b></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
<!--msthemelist--><tr>
<!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
<td valign="top" width="100%"><!--mstheme--><font face="宋体">
<p class="MsoNormal" style="text-indent: -26.25pt; mso-list: l40 level1 lfo13; tab-stops: list 47.25pt; margin-left: 30"><b><font size="5" color="#FFFFFF" face="宋体"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。</span></font></b><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--><tr>
<!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
<td valign="top" width="100%"><!--mstheme--><font face="宋体">
<p class="MsoNormal" style="text-indent: -26.25pt; mso-list: l40 level1 lfo13; tab-stops: list 47.25pt; margin-left: 30"><b><font size="5" color="#FFFFFF" face="宋体"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">树中所有结点可以有零个或多个后继结点。</span></font></b><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p class="MsoNormal" style="margin-left:21.0pt"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFFFF" face="宋体">由此特点可知，图</font></span><font size="5" color="#FFFFFF" face="宋体"><span lang="EN-US">6.1(b)</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">、</span><span lang="EN-US">(c)</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">、</span><span lang="EN-US">(d)</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">所示的都不是树结构。</span></font></b></p>
<p align="center"><img border="0" src="ds6.1.1.gif" width="595" height="168"></p>
<p class="MsoNormal"><font color="#FFFFFF" size="4"><span style="mso-bidi-font-size: 10.0pt"><b><span lang="EN-US">
</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">(a)</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">一棵树结构</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt">
<span> </span> </span></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">(b)</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">一个非树结构</span><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">
</span><span> </span></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt"><span>
</span> </span>(c)</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">一个非树结构</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt">
</span>(d)</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">一个非树结构</span></b></span></font></p>
<p class="MsoNormal" style="margin-left:21.0pt" align="center"><b><font size="5" color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt"><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">图</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">6.1<span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt">
</span></span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">树结构和非树结构的示意</span></span></font></b></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF" face="宋体"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">树的表示方法有以下四种，各用于不同的目的。</span></b></font></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
<!--msthemelist--><tr>
<!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
<td valign="top" width="100%"><!--mstheme--><font face="宋体"><!--mstheme--></font>
<h5><!--mstheme--><font face="宋体" color="#6666FF"><font size="5" color="#FFFFFF" face="宋体"><b><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman">直观表示法</span><span style="mso-ascii-font-family: Times New Roman; mso-bidi-font-size: 10.0pt">:</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">树的直观表示法就是以倒着的分支树的形式表示，图</span><span lang="EN-US">7.1(a)</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">就是一棵树的直观表示。其特点就是对树的逻辑结构的描述非常直观。是数据结构中最常用的树的描述方法。</span></b></font><!--mstheme--></font></h5>
<!--mstheme--><font face="宋体"><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--><tr>
<!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
<td valign="top" width="100%"><!--mstheme--><font face="宋体"><!--mstheme--></font>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -