二叉树与堆栈的等价关系.doc_第1页
二叉树与堆栈的等价关系.doc_第2页
二叉树与堆栈的等价关系.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

午）第1问 画出所有4个节点的二叉树第2问 已知字符进栈的顺序为ABCD，求所有可能的出栈顺序的种树。注：这两小题属于组合计数问题。系统内容可参见 组合数学课程 相关教材。第1问 画出4个节点的二叉树的所有二叉树。根据大小排序的所有4节点二叉树，一共14种。解答：二叉树可以其中，排序规则如下：int compare(BiTree t1, BiTree t2) /比较二叉树的大小,返回-1、0或1if (t1 = NULL & t2 = NULL) return 0;if (t1 = NULL & t2 != NULL) return -1;if (t1 != NULL & t2 = NULL) return 1;int cmpleft = compare(t1-left, t2-left);if (cmpleft != 0) return cmpleft;else return compare(t1-right, t2-right);思考题1：树的计数求具有n个结点的二叉树的数目。解答：设具有k个结点的的二叉树的数目为f(k)，则 1。当k=0时，是一棵空树，只有一种。 2。当k0时，二叉树可分为根结点、具有i个结点的左子树与具有k-1-i个结点的右子树。于是具有k个结点的二叉树的数目等于具有i个结点的二叉树的数目与具有k-1-i个结点的二叉树的数目的乘积。写成公式，就是： 可以用递推解得：，但是递推的方法计算复杂度会递增，f(k)需要计算k(k-1)/2次乘法。可以直接计算出通项公式： （详细求解过程参看组合数学教材的“母函数（生成函数）、卡特朗数”章节）。其中的C(n,2n)表示从2n个不同的数中取n个数的组合数。 所以本题的答案为 种。思考题2：遍历构造二叉树打印所有n个结点的二叉树。参考思考题1中的思路，对于make(t, k),可以分解为生成根节点t， make(t-left, i), make(t-right, k-1-i)三步，从而可以遍历构造出所有的二叉树。第2问 第二问可以转化为与第一问等价的问题。将这个问题与上一个问题比较一下：输入序列的排列状态(ABCD)是二叉树的前序序列；ABCD的进栈与出栈对应于二叉树结点的进栈与出栈；ABCD出栈后的排列状态正是二叉树的中序序列。 所以，求出栈的总数就 等价于 求二叉树的个数！将两道题对应起来看，不难发现，字母ABCD出栈后的可能排列方式的数目就是二叉树的中序序列的数目，也就是二叉树的数目。 与第一问一样：14种。思考题3：请问：已知字符入栈顺序为ABCDEFGHI，请问BCDAEGFIH是否可能是出栈序列？解答提示：同理地，如果要判断某个序列B能否构成入栈序列A的出栈序列，等价于判断：以序列A为先序、B为后序，能否够构成二叉树（那个算法你写过的）。思考题4：本题解法中，采用的是 “输入序列 树的先序遍
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论