📄 ds6.2.3.3.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>
<p><font size="5" color="#FFFFFF"><b><span style="mso-bidi-font-size: 10.0pt" lang="EN-US">3.</span></b></font><font size="5" color="#FFFFFF"><b><span style="mso-bidi-font-size: 10.0pt" lang="EN-US">
</span><span style="font-family:黑体">二叉树的基本操作及实现<span lang="EN-US"><o:p>
</span></span></b></font></p>
<h5><font size="5" color="#FFFFFF"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; mso-fareast-font-family: 黑体">1</span><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></b></font></h5>
<p class="MsoNormal"><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"">二叉树的基本操作通常有以下几种：</span></font></b></font></p>
<ul>
<li>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span lang="EN-US">Initiate</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">（</span><span lang="EN-US">bt</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">）建立一棵空二叉树。</span></b></font></li>
<li>
<p class="MsoNormal"><font color="#FFFFFF"><b><font size="5"><span lang="EN-US">Create</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">（</span><span lang="EN-US">x</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">lbt</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">rbt</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">）生成一棵以</span><span lang="EN-US">x</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">为根结点的数据域信息，以二叉树</span><span lang="EN-US">lbt</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">和</span><span lang="EN-US">rbt</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">为左子树和右子树的二叉树。</span></font></b></font></li>
<li>
<p class="MsoNormal"><font color="#FFFFFF"><b><font size="5"><span lang="EN-US">InsertL</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">（</span><span lang="EN-US">bt</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">x</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">x</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">的结点插入到二叉树</span><span lang="EN-US">bt</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">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">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">x</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">的左孩子结点。</span></font></b></font></li>
<li>
<p class="MsoNormal"><font color="#FFFFFF"><b><font size="5"><span lang="EN-US">InsertR</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">（</span><span lang="EN-US">bt</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">x</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">x</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">的结点插入到二叉树</span><span lang="EN-US">bt</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">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">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">x</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">的右孩子结点。</span></font></b></font></li>
<li>
<p class="MsoNormal"><font color="#FFFFFF"><b><font size="5"><span lang="EN-US">DeleteL</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">（</span><span lang="EN-US">bt</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">bt</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></font></b></font></li>
<li>
<p class="MsoNormal"><font color="#FFFFFF"><b><font size="5"><span lang="EN-US">DeleteR</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">（</span><span lang="EN-US">bt</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">bt</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></font></b></font></li>
<li>
<p class="MsoNormal"><font color="#FFFFFF"><b><font size="5"><span lang="EN-US">Search</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">（</span><span lang="EN-US">bt</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">x</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">）在二叉树</span><span lang="EN-US">bt</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">中查找数据元素</span><span lang="EN-US">x</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">。</span></font></b></font></li>
<li>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span lang="EN-US">Traverse</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">（</span><span lang="EN-US">bt</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">）按某种方式遍历二叉树</span><span lang="EN-US">bt</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">的全部结点。</span></b></font></li>
</ul>
<h5><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: 黑体"><font size="5" color="#FFFFFF"><b>2．算法的实现<o:p>
</o:p>
</b></font></span></h5>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font color="#FFFFFF"><b><font size="5">
</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"">算法的实现依赖于具体的存储结构，当二叉树采用不同的存储结构时，上述各种操作的实现算法是不同的。下面讨论基于二叉链表存储结构的上述操作的实现算法。</span></font></b></font></p>
<p class="MsoNormal"><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"">（</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><span lang="EN-US">Initiate</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">（</span><span lang="EN-US">bt</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -