精华内容
下载资源
问答
  • 具有n个节点二叉树有多少种形态

    千次阅读 2018-11-02 21:05:37
    n个节点二叉树有多少种形态(Catalan数)】 分析过程: (1)先考虑只有一个节点的情形,设此时的形态有f(1)种,那么很明显f(1)=1 (2)如果有两个节点呢?我们很自然想到,应该在f(1)的基础上考虑递推关系。...

    【n个节点的二叉树有多少种形态(Catalan数)】

    分析过程:
    (1)先考虑只有一个节点的情形,设此时的形态有f(1)种,那么很明显f(1)=1

    (2)如果有两个节点呢?我们很自然想到,应该在f(1)的基础上考虑递推关系。那么,如果固定一个节点后,左右子树的分布情况为1=1+0=0+1,故有f(2) = f(1) + f(1)

    (3)如果有三个节点,(我们需要考虑固定两个节点的情况么?当然不,因为当节点数量大于等于2时,无论你如何固定,其形态必然有多种)我们考虑固定一个节点,即根节点。好的,按照这个思路,还剩2个节点,那么左右子树的分布情况为2=2+0=1+1=0+2。
    所以有3个节点时,递归形式为f(3)=f(2) + f(1)*f(1) + f(2)。(注意这里的乘法,因为左右子树一起组成整棵树,根据排列组合里面的乘法原理即可得出)

    (4)那么有n个节点呢?我们固定一个节点,那么左右子树的分布情况为n-1=n-1 + 0 = n-2 + 1 = … = 1 + n-2 = 0 + n-1。此时递归表达式为f(n) = f(n-1) + f(n-2)f(1) + f(n-3)f(2) + … + f(1)f(n-2) + f(n-1)

    接下来我们定义没有节点的情况,此时也只有一种情况,即f(0)=1
    那么则有:
    f(0)=1,f(1)=1
    f(2)=f(1)f(0)+f(0)f(1)
    f(3)=f(2)f(0)+f(1)f(1)+f(0)f(2)
    .
    .
    .
    .
    f(n)=f(n-1)f(0)+f(n-2)f(1)+……….+f(1)f(n-2)+f(0)f(n-1)
    该数列称为卡特兰数(Catalan数),该递推关系的解为:
    这里写图片描述
    即含n个节点的二叉树有f(n)种形态。

    【其他使用Catalan数解决的问题】
    (1)矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?
    (2)一个栈(无穷大)的进栈序列为1,2,3,…n,有多少个不同的出栈序列?
    (3)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)
    (4)将一个凸多边形区域分成三角形区域的方法数?
    (5)在圆上选择2n个点,将这些点成对连接起来,使得所得到的n条线段不相交的方法数。
    (6)一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?

    展开全文
  • 如题,考研数据结构问题,具有n个结点且深度也为n的二叉树有多少种?
  • 1个节点二叉树只有1种形态,A[1]=1 2)n节点n>=2)的二叉树有 A[n] = ∑ [m=0到n-1] ( A[m]*A[n-m-1] ) ,求和的每项,分别表示根的左子树为m个节点、右子树为 n-m-1个节点的情况 刚好就是catalan数,直接用...

    记n个节点的二叉树形态个数为A[n] 

    1)0个节点的二叉树只有1种形态,A[0]=0;1个节点的二叉树只有1种形态,A[1]=1 

    2)n个节点(n>=2)的二叉树有 A[n] = ∑ [m=0到n-1] ( A[m]*A[n-m-1] ) ,求和的每一项,分别表示根的左子树为m个节点、右子树为 n-m-1个节点的情况 刚好就是catalan数,直接用catalan数的公式:h(n)=C(2n,n)/(n+1) 

    http://zhidao.baidu.com/question/407856789.html?qbl=relate_question_0&word=5%B8%F6%BD%DA%B5%E3%20%B6%FE%B2%E6%CA%F7

    展开全文
  • 具有3个结点二叉树有几种形态? 正确答案: B 你的答案: B (正确) 4 5 6 7 解析 这是一道牛客网上的测试题,因为题目是求3个节点二叉树的形态,所以直接手画了。...

    具有3个结点的二叉树有几种形态?

    正确答案: B   你的答案: B (正确)

    4
    5
    6
    7



    解析

    这是一道牛客网上的测试题,因为题目是求3个节点的二叉树的形态,所以直接手画了。但是看解析的时候,发现评论区居然有计算公式,真的是大开眼界啊。


    那个回答者给出的答案是:

    这是组合计数问题,最常见的catalan数,C(n)=(1/(n+1))*((2*n)!/(n!*n!))
    C(3) = (2*3)!/(3!*3!)/(3+1)=5


















    展开全文
  • N个结点不同结构的二叉树个

    千次阅读 2018-06-17 01:35:56
    n个无差别的节点构成的二叉树有多少种不同的结构?给定一个整数n,请返回不同结构的二叉树的个数。保证结果在int范围内。测试样例:1返回:1class TreeCount {public: int Cmn(int m,int n) { if(m==n||n==0) ...

    求n个无差别的节点构成的二叉树有多少种不同的结构?

    给定一个整数n,请返回不同结构的二叉树的个数。保证结果在int范围内。

    测试样例:
    1

    返回:1

    class TreeCount {
    public:
        int Cmn(int m,int n)
        {
            if(m==n||n==0)
                return 1;
            else
                return Cmn(m-1,n)+Cmn(m-1,n-1);
        }
        int countWays(int n) {
            // write code here
            if(n<2)
                return n;
            return Cmn(2*n,n)/(1+n);
        }
    };

    展开全文
  • 存在一棵总共有2016个结点二叉树,其中有16个结点只有一个孩子 答案:F 分析: 假设没有孩子的结点(叶结点数为n₀,只有一个孩子的结点(度为1结点数为n₁,有两孩子的结点(度为2的结点数为n₂...
  • 因为每个叶结点有2个空指针,而每个度为1的结点1个空指针, 则总的空指针数为 2 * n0 + n1 而 n0 = n2 + 1 (二叉树的特性) 所以对上式化简,德总的空指针为 2 * n0 + n1 = n0 +(n2 + 1)+ n1 ...
  • <ol><li>一棵nn>0)个结点的满二叉树共有____叶子和____非终端结点。</li></ol>
  • 2.完全二叉树:如果一棵具有N个结点二叉树的结构与满二叉树的前N个结点的结构相同,称为完全二叉树。 //判断一棵二叉树是否是完全二叉树--利用层序遍历来处理->关键: //找第一个度不为2的结点->后序结点...
  • 题目: 利用归纳法证明:个有n结点的非空二叉树的高度至少为 证明: ...将n结点的非空二叉树分成左子树k个结点和右子树n-k-1个结点,于是结点数为n的树高度 由假设可知: 当时,即时, 故证。
  • 具有n结点的不同形态的树的数目 Bn=An-1 ,应该和具有n-1个结点的不同二叉树的数目相同。 具有n结点的不同形态的森林树木 Dn=An。 【ps: C(n 2n) 为组合,上面为n,下面为2n 】 转自数据结构与算法C++版
  • n个节点组成二叉树的形态有几种

    千次阅读 2014-04-07 15:22:52
    n个节点n组成的二叉树
  • 可以分析,当n=1时,只有1个节点,则只能组成1种形态的二叉树,令n节点可组成的二叉树数量表示为h(n),则h(1)=1; h(0)=1; 当n=2时,1个节点固定,还有2-1个节点。这节点可以分成(1,0),(0,1)两组。即...
  • 先再读遍题目,里面有“最多”两字,也就是说能满足条件的完全二叉树不止种,要找出结点最多的那个 评论里的人几乎都认为答案唯一且为247,评论里的观点是:非叶节点数目 = 叶节点+1观点并不是完全正确的...
  • =2)的二叉树有 A[n] = ∑ [m=0到n-1] ( A[m]*A[n-m-1] ) ,求和的每项,分别表示根的左子树为m个节点、右子树为 n-m-1个节点的情况刚好就是catalan数,直接用catalan数的公式:h(n)=C(2n,n)...
  • N个节点二叉树的形态数 卡特兰数
  • n个节点二叉树有多少种形态

    万次阅读 多人点赞 2015-06-28 17:32:49
    n个节点二叉树有多少种形态(Catalan数)】分析过程: (1)先考虑只有一个节点的情形,设此时的形态有f(1)种,那么很明显f(1)=1(2)如果有两个节点呢?我们很自然想到,应该在f(1)的基础上考虑递推关系。那么...
  • 严格二叉树,这定义就百度上有,维基百科都没查到。 严格二叉树的定义:如果二叉树的每非终端节点都有且仅有两子树,则称这颗二叉树为严格二叉树。...首先证明一个问题,对于n个叶子的严格二叉树,必...
  • 1.n个节点二叉树,最多可以有多少层? A.n/2 B.log(n) C.n-1 D.n 答案解析: D 假设从根节点开始,根节点的层数为1,每一个节点,则有n层。
  • 问题:具有3个结点二叉树有几种形态? A.4 B.5 C.6 D.7 解析:正确答案: B 你的答案: B(正确)。 C(n)=(1/(n+1))*((2*n)!/(n!*n!)) C(3) = (2*3)!/(3!*3!)/(3+1)=5 【n个节点二叉树有多少种形态...
  • 深度为N的满二叉树第M层节点数为2(m-1);...满二叉树应是210-1=1023个节点,这里是1001个节点,完全二叉树比满二叉树少在最后行,少了1023-1001=22个节点,满二叉树最后行是210-1=512个节点;减去22缺少节点,...
  • treelink *treecreate(int root) //用递归的方法创建一个N个结点的完全二叉树 { treelink *t = (treelink *)malloc(sizeof(treelink)); t->data = root; t->lchild = t->rchild = NULL; if(t
  • =0)的二叉树最少有k个结点,最多有2^k-1个结点。3. 对于任一非空二叉树,若其叶结点数为n0,度为2的非叶结点数为n2,则n0 = n2 +1。4. 具有n结点的完全二叉树的深度为int_UP(log(2,n+1))。5. 如果将...
  • 没耐心的同学们可以直接拉到最底下看结论,有兴趣的话可以浏览全篇文章 ...一棵完全二叉树具有1000个结点,则此完全二叉树有多少度为2的结点? 完全二叉树699个节点,则叶子节点有多少? 已知完全二叉树...
  • 具有1102个结点的完全二叉树一定有__叶子结点。 79 551 √ 1063 不确定 设n2为度为bai2的节点,n1为度为1节点,dun0为度为0的节点; 边数n=节点zhi数-1,即n=1101; n=2n2+n1; 完全二dao叉树度为1节点只能...
  • 输出n个节点二叉树有多少种形态 或 二、实现 import java.util.HashMap; public class Test{ public static void main(String args[]) { int n = 4; int res = getRootNum(n); System.out....
  • 高度为n的平衡二叉树最少需要多少个节点?高度为n的平衡二叉树最少需要多少个节点?参考 高度为n的平衡二叉树最少需要多少个节点? 设f(n)为高度为n的平衡二叉树最少含有的节点数,则:f(1) = 1;f(2) = 2; f(3) = ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,059
精华内容 20,023
关键字:

对于一棵具有n个节点的二叉树