二叉树和堆栈等价关系.docVIP

午） 第1问 画出所有4个节点的二叉树 第2问 已知字符进栈的顺序为ABCD，求所有可能的出栈顺序的种树。 注：这两小题属于组合计数问题。系统内容可参见 组合数学课程 相关教材。 第1问 画出4个节点的二叉树的所有二叉树。 根据大小排序的所有4节点二叉树，一共14种。解答： 根据大小排序的所有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。当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： 本题解法中，采用的是 “输入序列 ~~ 树的先序遍历，输出序列 ~~ 树的中序遍历”，是否有其他的映射方法。 能否用 中序遍历、后序遍历 对应？ 或者 先序遍历、后序遍历 对应？ 为什么？