📄 ds6.2.3.2.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">
<p:colorscheme
colors="#0000FF,#FFFFFF,#000000,#FFCC66,#00FFFF,#3366FF,#FF0033,#FFFF00"/>
<p align="center"><b><font size="6" color="#FFFF00">6.2.3 <span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: 黑体; 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">二叉树的存储结构</span></font></b></p>
<h5><b><font size="5" color="#FFFFFF" face="宋体"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; mso-fareast-font-family: 黑体">
</o:p></span></font></b><font size="5" color="#FFFFFF"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">2</span><span style="mso-bidi-font-size: 10.0pt; font-family: 黑体; mso-ascii-font-family: Arial">．链式存储结构</span></b></font></h5>
<h4><font size="5" color="#FFFFFF"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 黑体; mso-ascii-font-family: Arial">
所谓</span></b></font><span style="mso-bidi-font-size: 10.0pt; font-family: 黑体; 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; mso-ascii-font-family: Arial"><b><font size="5" color="#FFFFFF">二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常有下面两种形式。</font></b></span><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF"><b><o:p>
</o:p>
</b></font></span></h4>
<p class="MsoNormal"><span lang="EN-US"><font size="5" color="#FFFFFF"><b><span style="font-family: 宋体; mso-hansi-font-family: Times New Roman">(</span></b></font></span><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF"><b>1)二叉链表存储<o:p>
</o:p>
</b></font></span></p>
<font size="5" color="#FFFFFF"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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">
</span></b></font><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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 size="5" color="#FFFFFF"><b>链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储的结构为：</b></font></span>
<p align="center"><img border="0" src="ds6.2.10.gif" width="204" height="30"></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><span style="font-family: 宋体; mso-hansi-font-family: Times New Roman"><b>
其中，<span lang="EN-US">data</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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">域</span><span lang="EN-US" style="font-family: 宋体; mso-hansi-font-family: Times New Roman">存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，</span></b></span></font><font size="5" color="#FFFFFF"><span style="font-family: 宋体; mso-hansi-font-family: Times New Roman"><b><span lang="EN-US" style="font-family: 宋体; mso-hansi-font-family: Times New Roman">相应指针域值为空（用符号∧或NULL表示）。<o:p>
</o:p>
</span></b></span></font></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span style="font-family: 宋体; mso-hansi-font-family: Times New Roman" lang="EN-US"><span style="font-family: 宋体; mso-hansi-font-family: Times New Roman">图</span><span style="font-family: 宋体; mso-hansi-font-family: Times New Roman">6.7(a)给</span><span style="font-family:宋体;mso-hansi-font-family:
"Times New Roman"">出了图6.3(b)所示的一棵二叉树的二叉链表示。<o:p>
</o:p>
</span></span></font></b></p>
<b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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 size="5" color="#FFFFFF">二叉链表也可以带头结点的方式存放，如图6.7(b)所示：</font></span></b>
<p><img border="0" src="ds6.2.11.gif" width="600" height="332"></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family: 宋体; mso-hansi-font-family: Times New Roman"><b><font size="5" color="#FFFFFF">(2)三叉链表存储<o:p>
</o:p>
</font></b></span></p>
<b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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 size="5" color="#FFFFFF">每个结点由四个域组成，具体结构为：</font></span></b>
<p><b><font size="5" color="#FFFFFF"><img border="0" src="ds6.2.12.gif" width="272" height="29"></font></b></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman"">
其中，<span lang="EN-US">data</span></span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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">、</span><span lang="EN-US" style="font-family: 宋体; mso-hansi-font-family: Times New Roman">lchild</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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">以</span><span lang="EN-US" style="font-family: 宋体; mso-hansi-font-family: Times New Roman">及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。<o:p>
</o:p>
</span></font></b></p>
<b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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 size="5" color="#FFFFFF"><span style="mso-spacerun: yes">
</span>(6.8)出了图6.3(b)所示的一棵二叉树的三叉链表示。</font></span></b>
<p align="center"><img border="0" src="ds6.2.14.gif" width="472" height="197"></p>
<p align="center" style="margin-bottom: 0"> </p>
<p align="center" style="margin-top: 0"><img border="0" src="ds6.2.13.gif" width="500" height="41"></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><b><font size="5" color="#FFFFFF">
尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。本书后面所涉及到的二叉树的链式存储结构不加特别说明的都是指二叉链表结构。<span lang="EN-US"><o:p>
</o:p>
</span></font></b></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><b><font size="5" color="#FFFFFF">二</font></b></span><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF">叉树的二叉链表存储表示可描述为：<o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>typedef struct BiTNode{<o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal"><font color="#FFFFFF"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font></span></b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><b><font size="5">elemtype data;<o:p>
</o:p>
</font></b></span></font></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><span style="font-family: 宋体; mso-hansi-font-family: Times New Roman"><b><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman" lang="EN-US">
</span></b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><b>struct BiTNode *lchild;*rchild;<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></b></span><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><o:p>
</o:p>
</span></b></span></font></p>
<p class="MsoNormal"><font color="#FFFFFF"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font></span></b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><b><font size="5">}BiTNode,*BiTree;<o:p>
</o:p>
</font></b></span></font></p>
<b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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 size="5" color="#FFFFFF">即将<span lang="EN-US">BiTree</span>定<span lang="EN-US">义为指向二叉链表结点结构的指针类型。</span></font></span></b>
<p align="left" style="margin-top: 0"> </p>
<p align="center"><b><font size="5"><a href="ds6.2.3.HTM"><font color="#FFFF00">返回</font></a></font></b></p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -