📄 answer_4.htm
字号:
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>5</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p==pp->Lchild </span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>或</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'> p </span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>*pp</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>.Lchild<o:p></o:p></span></p>
<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>【解析】（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）程序的第一条语句是变量的声明及赋初值，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>指向二叉查找树的根。接下来从</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>while</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>循环的注释部分可以看出，该循环的功能是查找键值为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>e</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的结点。当循环的判断条件</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>e<p->data</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>时，进入左子树查找，否则到右子树查找。程序中没有关于找到结点的处理代码，即循环内部只处理了没找到结点的情况，所以循环条件应该是当找到键值为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>e</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的结点时退出循环。另外，应注意一个隐含的限制条件<span
lang=EN-US>"</span></span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>p=NULL</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:
"Times New Roman"'>"时，表示已经查找完毕，无需进入循环。通过分析，（</span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）应填</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p && p->data!=e</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>。（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>2</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>if</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>程序段是处理第三种情况的，由循环中的语句<span
lang=EN-US>"</span></span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>s=s->Rchild;</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:
"Times New Roman"'>"可看出，</span><span lang=EN-US style='mso-bidi-font-size:
10.5pt'>s</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体;
mso-hansi-font-family:"Times New Roman"'>用于要删结点的左子树中查找键值最大的结点，所以</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>s</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的初值应是要删除结点的左子结点。可见，（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>2</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）应填写</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p->Lchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>。（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>3</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）根据前面所述的二叉树规则可知，要找的结点</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>s</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>应是左子树中查找键值最大的结点，所以</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>s</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的初值应是要删除结点的左子结点。可见，（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>3</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）应填</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p->Rchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>。本题把①、②结合在一起进行处理，所以引入了一个中间变量</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>c</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，用</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>c</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>来存储用于替换</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的结点。现在的关键问题是什么条件可以使这两种情况和在一起，因为若删除的结点为叶子结点时，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p->Rchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>与</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p->Lchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>都为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>NULL</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>；若删除的结点有一个子结点时，如果有左子结点，则</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p->Rchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p->Rchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>；如果有右子结点，则</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p->Lchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>NULL</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>。当</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p->Lchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>不为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>NULL</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>时，说明是第二种情况，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>结点含左子结点，所以</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>c=p->Lchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>；当</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p->Lchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>NULL</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>时，说明有两种可能：<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>第一：</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p->Rchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>也为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>NULL</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，则</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>是叶子结点。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>第二：</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p->Rchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>不为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>NULL</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，则</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>是有右子结点的结点。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='text-align:left;mso-layout-grid-align:
none;text-autospace:none'><span style='mso-bidi-font-size:10.5pt;font-family:
宋体;mso-hansi-font-family:"Times New Roman"'>这两种情况都可以用</span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>c=p->Rchild</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，因为当</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>是叶子结点的时候用</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>NULL</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>代替</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的位置即可，所以第（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>4</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）应填</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p->Lchild</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>。在程序中很多地方都出现了变量</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>pp</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，其实只要仔细看一下前面的程序就知道，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>pp</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>一直指向的是</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>结点的前一个结点，即</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的父结点，所以（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>5</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）的作用是判断</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>p</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>是其父结点的左子结点还是右子结点，（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>5</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）应填</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>pp->Lchild=p</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>。</span><span
style='font-size:8.5pt;font-family:"MS Sans Serif";mso-font-kerning:0pt;
mso-ansi-language:ZH-CN'><o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p>
</div>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -