📄 ds62习.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 class="MsoNormal"><b><span lang="EN-US" style="font-family:宋体"><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes; font-family: 宋体"> </span>6.22
二叉树的遍历算法可写为通用形式。例如，通用的中序遍历为：<o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal" style="text-indent: 0; margin-right: 0; margin-top: 0; margin-bottom: 0"><b><span lang="EN-US" style="font-family:宋体"><font size="5" color="#FFFFFF">void
Inorder(BinTree T,void(*Visit)(Datatype x))<o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal" style="text-indent: 0; margin-right: 0; margin-top: 0; margin-bottom: 0"><b><span lang="EN-US" style="font-family:宋体"><font size="5" color="#FFFFFF">{
if (T)<o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal" style="text-indent: 0; margin-right: 0; margin-top: 0; margin-bottom: 0"><font color="#FFFFFF"><b><span lang="EN-US" style="font-family:宋体"><font size="5"><span style="mso-spacerun: yes; font-family: 宋体"> </span></font></span></b><span lang="EN-US" style="font-family:宋体"><b><font size="5">{Inorder(T->lchild,Visit);<span style="mso-spacerun: yes; font-family: 宋体">
</span>/*遍历左子树*/<o:p>
</o:p>
</font></b></span></font></p>
<p class="MsoNormal" style="text-indent: 0; margin-right: 0; margin-top: 0; margin-bottom: 0"><font color="#FFFFFF"><b><span lang="EN-US" style="font-family:宋体"><font size="5"><span style="mso-spacerun: yes; font-family: 宋体">
</span></font></span></b><span lang="EN-US" style="font-family:宋体"><b><font size="5">Visit(T->data);<span style="mso-spacerun: yes; font-family: 宋体">
</span>/*通过函数指针调用它所指的函数来访问结点*/<o:p>
</o:p>
</font></b></span></font></p>
<p class="MsoNormal" style="text-indent: 0; margin-right: 0; margin-top: 0; margin-bottom: 0"><font color="#FFFFFF"><b><span lang="EN-US" style="font-family:宋体"><font size="5"><span style="mso-spacerun: yes; font-family: 宋体">
</span></font></span></b><span lang="EN-US" style="font-family:宋体"><b><font size="5">Inorder(T->rchild,Visit);<span style="mso-spacerun: yes; font-family: 宋体">
</span>/*遍历右子树*/<o:p>
</o:p>
</font></b></span></font></p>
<p class="MsoNormal" style="text-indent: 0; margin-right: 0; margin-top: 0; margin-bottom: 0"><font color="#FFFFFF"><b><span lang="EN-US" style="font-family:宋体"><font size="5"><span style="mso-spacerun: yes; font-family: 宋体">
</span></font></span></b><span lang="EN-US" style="font-family:宋体"><b><font size="5">}<o:p>
</o:p>
</font></b></span></font></p>
<p class="MsoNormal" style="text-indent: 0; margin-right: 0; margin-top: 0; margin-bottom: 0"><b><span lang="EN-US" style="font-family:宋体"><font size="5" color="#FFFFFF">}<o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal" style="text-indent:31.5pt"><span style="font-family:宋体"><b><font size="5" color="#FFFFFF">其中<span lang="EN-US">Visit是一个函数指针，它指向形如void
f（DdataType x）的函数。因此我们可以将访问结点的操作写在函数f中，通过调用语句Inorder（root，f）将f的地址传递给Visit，来执行遍历操作。请写一个打印结点的数据的函数，通过调用上述算法来完成书中6.3节的中序遍历。</span></font></b></span><span lang="EN-US" style="font-family:宋体"><o:p>
</o:p>
</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体"><b><font size="5" color="#FFFFFF">6.23
以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。</font></b><o:p>
</o:p>
</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体"><b><font size="5" color="#FFFFFF">6.24
以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。<o:p>
</o:p>
</font></b></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体"><font size="5" color="#FFFFFF"><b>6.25
以二叉链表为存储结构，写一算法交换各结点的左右子树。</b></font></span><span lang="EN-US" style="font-family:宋体"><o:p>
</o:p>
</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体"><font size="5" color="#FFFFFF"><b>6．26
以二叉表为存储结构，写一个拷贝二叉表的算法 （BinTree
root,BinTree *newroot）,其中新树的结点是动态申请的，</b></font><o:p>
</o:p>
</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体"><font size="5" color="#FFFFFF"><b>6．27
以二叉树表为存储结构，分别写处在二叉树中查找值为x的结点在树中层数的算法。</b></font><o:p>
</o:p>
</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体"><b><font size="5" color="#FFFFFF">6.28一棵n个结点的完全二叉树以向量作为存储结构，试写一非递归算法实现对该树的前序遍历。</font></b><o:p>
</o:p>
</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体"><b><font size="5" color="#FFFFFF">6．29
以二叉树表为存储结构，写一算法对二叉树进行层次遍历（定义见习题6.13）。提示：应使用队列来保存各层的结点。</font></b><o:p>
</o:p>
</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体"><b><font size="5" color="#FFFFFF">6．30
以二叉树表为存储结构，写一算法用括号形式（keyLT,RT）打印二叉树，其中key是根结点数据，LT和RT分别是括号形式的左右子树。并且要求：空树不打印任何信息，一给结点x的树打印形式是x，而不应是（x，，）d的形式。</font></b><o:p>
</o:p>
</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体"><b><font size="5" color="#FFFFFF">6.31以线索链表为存储结构，分别写出在前序线索树中查找给定结点*p的后继，以及在后序线索树中查找*p的后序前趋的算法。</font></b><o:p>
</o:p>
</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体"><span style="mso-spacerun: yes"><font size="5" color="#FFFFFF"><b> </b></font></span><font size="5" color="#FFFFFF"><b>6．32<span style="mso-spacerun: yes">
</span>完成6.6.1 节算法CreateHuffmanTree中调用的三个函数：InputWeight,SelecMin和InitHuffmanTree.</b></font><o:p>
</o:p>
</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体"><b><font size="5" color="#FFFFFF">6．33
分别写出对文件进行哈夫谩码的算法，以及对编码文件进行解码的算法。为简单起见，可以假设文件存放在一个字符向量。</font></b></span></p>
<!--mstheme--></font>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -