📄 ds6.4.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="#FFFF00" size="6">6.4.1
树的存储结构</font></span></b></p>
<p class="MsoNormal"><b><span style="mso-spacerun: yes" lang="EN-US"><font color="#FFFFFF" size="5">
</font></span><font color="#FFFFFF" size="5"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">在计算机中，树的存储有多种方式，既可以采用顺序存储结构，也可以采用链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系。下面介绍几种基本的树的存储方式。</span></font></b></p>
<p class="MsoNormal"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; mso-fareast-font-family: 黑体"><font color="#FFFFFF" size="5">1</font></span><font color="#FFFFFF" size="5"><span style="mso-bidi-font-size: 10.0pt; font-family: 黑体; mso-ascii-font-family: Times New Roman">．双亲表示法</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; mso-fareast-font-family: 黑体"><o:p>
</o:p>
</span></font></b></p>
<p class="MsoNormal"><b><span style="mso-spacerun: yes" lang="EN-US"><font color="#FFFFFF" size="5">
</font></span><font color="#FFFFFF" size="5"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">由树的定义可以知道，树中的每个结点都有唯一的一个双亲结点，根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，数组元素为结构体类型，其中包括结点本身的信息以及结点的双亲结点在数组中的序号，树的这种存储方法称为双亲表示法。其存储表示可描述为：</span></font></b></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><b><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF" size="5"> </font></span><font color="#FFFFFF" size="5">#define
MAXNODE <</font></span><font color="#FFFFFF" size="5"><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">树中结点的最大个数</span><span lang="EN-US">></span></font></b></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font size="5"><b><font color="#FFFFFF"> </font></b></font></span><font color="#FFFFFF" size="5"><b>typedef
struct {</b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font size="5"><b><font color="#FFFFFF">
</font></b></font></span><font color="#FFFFFF" size="5"><b>elemtype<span style="mso-spacerun: yes">
</span>data;</b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font size="5"><b><font color="#FFFFFF">
</font></b></font></span><font color="#FFFFFF" size="5"><b>int<span style="mso-spacerun: yes">
</span>parent;</b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font size="5"><b><font color="#FFFFFF">
</font></b></font></span><font color="#FFFFFF" size="5"><b>}NodeType;</b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font size="5"><b><font color="#FFFFFF"> </font></b></font></span><font color="#FFFFFF" size="5"><b>NodeType<span style="mso-spacerun: yes">
</span>t[MAXNODE];</b></font></span></p>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font size="5"><b><font color="#FFFFFF">
</font></b></font></span><b><font color="#FFFFFF" size="5"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">下</span></font></b><font size="5"><b><font color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">图</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">所示的树的双亲表示如表</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">所示。图中用</span><span lang="EN-US">parent</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">域的值为</span><span lang="EN-US">-1</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">表示该结点无双亲结点，即该结点是一个根结点。</span></font></b></font></p>
<p class="MsoNormal" align="center"><img border="0" src="ds6.4.1.gif" align="left" width="180" height="238"></p>
<div align="center">
<center><!--mstheme--></font>
<table border="1" width="35%" bordercolorlight="#3366CC" bordercolordark="#000000">
<tr>
<td width="33%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>序号</b></font><!--mstheme--></font></td>
<td width="33%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>data</b></font><!--mstheme--></font></td>
<td width="34%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>parent</b></font><!--mstheme--></font></td>
</tr>
<tr>
<td width="33%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>0</b></font><!--mstheme--></font></td>
<td width="33%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>A</b></font><!--mstheme--></font></td>
<td width="34%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>-1</b></font><!--mstheme--></font></td>
</tr>
<tr>
<td width="33%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>1</b></font><!--mstheme--></font></td>
<td width="33%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>B</b></font><!--mstheme--></font></td>
<td width="34%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>0</b></font><!--mstheme--></font></td>
</tr>
<tr>
<td width="33%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>2</b></font><!--mstheme--></font></td>
<td width="33%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>C</b></font><!--mstheme--></font></td>
<td width="34%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>0</b></font><!--mstheme--></font></td>
</tr>
<tr>
<td width="33%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>3</b></font><!--mstheme--></font></td>
<td width="33%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>D</b></font><!--mstheme--></font></td>
<td width="34%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>1</b></font><!--mstheme--></font></td>
</tr>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -