📄 ds9.3.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><font size="5" color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">9.3.1</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; 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></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"><b><span style="mso-bidi-font-size: 10.0pt"><font size="5" color="#FFFF00">二叉排序树定义</font><font size="5" color="#FFFFFF"><span lang="EN-US"><o:p>
</o:p>
</span></font></span></b><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF"><b>
</b></font></span><font size="5" color="#FFFFFF"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">二叉排序树（</span><span lang="EN-US">Binary
Sort Tree</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）或者是一棵空树；或者是具有下列性质的二叉树：</span></b></font></p>
<blockquote>
<ol>
<li>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">右子树上所有结点的值均大于根结点的值。</span></b></font></li>
<li>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="mso-bidi-font-size: 10.0pt; 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">左右子树也都是二叉排序树。</span></b></font></li>
</ol>
</blockquote>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman""> <font size="5"><b><font color="#FFFFFF">由右图</font></b></font></span><font color="#FFFFFF"><b><font size="5"><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">可以看出，对二叉排序树进行中<img border="0" src="ds9.3.1.gif" align="right" width="144" height="137"></span></font></b></font></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>序遍历，便可得到一个按关键码有序的序列，</b></font></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>因此，一个无序序列，可通过构一棵二叉排序</b></font></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>树而成为有序序列。</b></font></span></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"><b><span style="mso-bidi-font-size: 10.0pt"><font size="5" color="#FFFF00">二叉排序树查找过程</font><font size="5" color="#FFFFFF"><span lang="EN-US"><o:p>
</o:p>
</span></font></span></b><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p class="MsoNormal"><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></p>
<ol>
<li>
<p class="MsoNormal"><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></li>
<li>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">查找树非空,将给定值</span></font><span lang="EN-US"><font color="#FFFFFF" size="4">key</font></span><font size="5" color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">与查找树的根结点关键码比较。</span></font></b></li>
<li>
<p class="MsoNormal" style="margin-bottom: 0"><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></li>
</ol>
<blockquote>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFF00">a.</font><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">k</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">ey小于根结点关键码，查找将在以左子女为根的子树上继续进行，转①</span></font></b></p>
<p class="MsoNormal" style="margin-top: 0"><font color="#FFFF00"><span lang="EN-US"><b><font size="5">b</font></b></span></font><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFF00">.</font><font size="5" color="#FFFFFF">当给</font></span><font size="5" color="#FFFFFF"><span lang="EN-US">key</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">大于根结点关键码，查找将在以右子女为根的子树上继续进行，转①</span></font></b></p>
</blockquote>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes" lang="EN-US">
</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-top: 0; margin-bottom: 0"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFF00">【算法</font></span><font size="5" color="#FFFF00"><span lang="EN-US">9.4</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-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>BitRree
SeBST(BiTree T, KeyType key)</b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>{</b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
if(!T|| key==T->data.key) return(T);</b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
else if (key<T->data.key) </b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
return(SeBST(T->lchild,key));</b></font></p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -