为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

二叉树与客栈的等价关系[精华]

2018-10-04 3页 doc 13KB 3阅读

用户头像

is_358746

暂无简介

举报
二叉树与客栈的等价关系[精华]二叉树与客栈的等价关系[精华] 午) 第1问 画出所有4个节点的二叉树 第2问 已知字符进栈的顺序为ABCD,求所有可能的出栈顺序的种树。 注:这两小题属于组合计数问题。系统内容可参见 组合数学课程 相关教材。 第1问 画出4个节点的二叉树的所有二叉树。 解答: 根据大小排序的所有4节点二叉树,一共14种。 二叉树可以其中,排序规则如下: int compare(BiTree t1, BiTree t2) {//比较二叉树的大小,返回-1、0或1 if (t1 == NULL && t2 == NULL) retu...
二叉树与客栈的等价关系[精华]
二叉树与客栈的等价关系[精华] 午) 第1问 画出所有4个节点的二叉树 第2问 已知字符进栈的顺序为ABCD,求所有可能的出栈顺序的种树。 注:这两小题属于组合计数问题。系统内容可参见 组合数学课程 相关教材。 第1问 画出4个节点的二叉树的所有二叉树。 解答: 根据大小排序的所有4节点二叉树,一共14种。 二叉树可以其中,排序规则如下: int compare(BiTree t1, BiTree t2) {//比较二叉树的大小,返回-1、0或1 if (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。当k>0时,二叉树可分为根结点、具有i个结点的左子树与具有k-1-i个结点的右子树。于是具有k个结点的二叉树的数目等于具有i个结点的二叉树的数目与具有k-1-i个结点的二叉树的数目的乘积。写成公式,就是: f(0),1 n,1 f(k),(f(i),f(n,1,i)),i,0,1??,k,1.,k,0 可以用递推解得:,但是递推的方法f(0),1,f(1),1,f(2),3,f(3),5,f(4),14??计算复杂度会递增,f(k)需要计算k(k-1)/2次乘法。 可以直接计算出通项公式: n C2nf(n),n,1 (详细求解过程参看《组合数学》教材的“母函数(生成函数)、卡特朗数”章节)。 其中的C(n,2n)表示从2n个不同的数中取n个数的组合数。 4 C8所以本题的答案为 种。 f(4),,144,1 思考题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: 本题解法中,采用的是 “输入序列 ~~ 树的先序遍历,输出序列 ~~ 树的中序遍历”,是否有其他的映射方法。 能否用 中序遍历、后序遍历 对应, 或者 先序遍历、后序遍历 对应, 为什么,
/
本文档为【二叉树与客栈的等价关系[精华]】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
热门搜索

历史搜索

    清空历史搜索