📄 ds6.1.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>数 据 结 构</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>
<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">
<!--mstheme--><font face="宋体"><p:colorscheme
colors="#0000FF,#FFFFFF,#000000,#FFCC66,#00FFFF,#3366FF,#FF0033,#FFFF00"/>
<p align="center"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font color="#FFFFFF" size="6">6.1
树的定义和基本术语</font></span></b></p>
<p class="MsoNormal"><b><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF" face="宋体">
</font></span><font size="5" color="#FFFFFF" face="宋体"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">树（</span><span lang="EN-US">Tree</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）是</span><span lang="EN-US">n</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">n</span><span style="mso-hansi-font-family: Times New Roman">≥<span lang="EN-US">0</span></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）个有限数据元素的集合。当</span><span lang="EN-US">n</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">＝</span><span lang="EN-US">0</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></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"><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></font></b></font><!--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"><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">n>1</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，除根结点之外的其余数据元素被分成</span><span lang="EN-US">m</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">m>0</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">…</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，</span><span lang="EN-US">T<sub>m</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>i</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">1</span><span style="mso-hansi-font-family: Times New Roman">≤</span><span lang="EN-US">i</span><span style="mso-hansi-font-family: Times New Roman">≤</span><span lang="EN-US">m</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">…</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，</span><span lang="EN-US">T<sub>m</sub></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">称为这个根结点的子树。</span></font></b></font><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<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></font></b></font><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" style="margin-left:21.0pt"><span lang="EN-US"><span style="mso-spacerun: yes"><font face="宋体"><b><font size="5" color="#FFFFFF">
</font></b></font></span><font size="5" color="#FFFFFF" face="宋体"><b>T</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">D</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，</span><span lang="EN-US">R</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"><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">D</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">R</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">为树中结点之间关系的集合。</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><font size="5" color="#FFFFFF" face="宋体"><span lang="EN-US">D</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">＝</span><span style="mso-hansi-font-family: Times New Roman">Φ；当树<span lang="EN-US">T不为空树时有：<o:p>
</o:p>
</span></span></font></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>D＝{Root}<span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">U</span>D</b></font></span><b><font size="5" color="#FFFFFF"><sub><span lang="EN-US">F</span></sub><span lang="EN-US" style="mso-hansi-font-family: Times New Roman"><o:p>
</o:p>
</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的根结点，DF为树T的根Root的子树集合。D</span></font></span><font size="5" color="#FFFFFF" face="宋体"><sub><span lang="EN-US">F</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"><font face="宋体"><span lang="EN-US" style="mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFFFF"><b>D</b></font></span><b><font size="5" color="#FFFFFF"><sub><span lang="EN-US">F</span></sub><span style="mso-hansi-font-family: Times New Roman">＝<span lang="EN-US">D</span></span><sub><span lang="EN-US">1</span></sub><span style="mso-hansi-font-family: Times New Roman">∪<span lang="EN-US">D</span></span><sub><span lang="EN-US">2</span></sub><span style="mso-hansi-font-family: Times New Roman">∪</span><span lang="EN-US" style="mso-ascii-font-family:宋体">…</span><span style="mso-hansi-font-family: Times New Roman">∪<span lang="EN-US">D</span></span><sub><span lang="EN-US">m</span></sub><span style="mso-hansi-font-family: Times New Roman">且<span lang="EN-US">D</span></span><sub><span lang="EN-US">i</span></sub><span style="mso-hansi-font-family: Times New Roman">∩<span lang="EN-US">D</span></span><sub><span lang="EN-US">j</span></sub><span style="mso-hansi-font-family: Times New Roman">＝Φ<span lang="EN-US">i≠j,1≤i≤m,1≤j≤m）<o:p>
</o:p>
</span></span></font></b></font></p>
<p class="MsoNormal" style="margin-left: 0"><b><span style="mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFFFF" face="宋体">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -