内容简介:对于二叉树形态,可以从二叉树本身的规律去找,离不开递推先考虑只有一个节点的情况,设此时的形态为f(1)种,很明显f(1)=1; 那么有两个节点的时候呢?我们很容易的想到,应该在一个节点的基础上考虑递推关系。所以,当固定一个节点后,有两种情况,一种是左子树一个节点,一种是右子树一个节点,共有两种情况,所以f(2) = f(1)+f(1);当三个节点的时候呢?我们要考虑固定两个节点吗?看样子好像不行,因为固定两个节点的形态不是唯一的。那么当节点数量大于2的时候,我们是在固定不同的形态的基础下,在安排剩下的节点吗
对于二叉树形态,可以从二叉树本身的规律去找,离不开递推
先考虑只有一个节点的情况,设此时的形态为f(1)种,很明显f(1)=1; 那么有两个节点的时候呢?我们很容易的想到,应该在一个节点的基础上考虑递推关系。所以,当固定一个节点后,有两种情况,一种是左子树一个节点,一种是右子树一个节点,共有两种情况,所以f(2) = f(1)+f(1);当三个节点的时候呢?我们要考虑固定两个节点吗?看样子好像不行,因为固定两个节点的形态不是唯一的。
那么当节点数量大于2的时候,我们是在固定不同的形态的基础下,在安排剩下的节点吗? 我们应该这样想,固定一个节点就是根节点,二叉树本来就是由左子树,右子树,根节点组成的,所以固定根节点,遍历左右子树。下图是4个节点的形态图
当固定根节点时,剩下3个节点,分成如下几种情况,左3右0,左2右1,左1右2,左0右3这四种情况。 所以f(4)=f(3)+f(2)*f(1)+f(1)*f(2)+f(3),当有n个节点呢?此时我们固定根节点左右子树的分布情况为(n-1,0),(n-2,1),(n-3,2)...(2,n-3),(1,n-2),所以我们不难推出f(n)=f(n-1)+f(n-2)f(1)+....+f(1)f(n-2)+f(n-1),通过表达式可以看出,这和普通的递归表达式有点区别,不是单纯的看前一步或前两步,而是考虑到从1到n-1的情况,这里我们可以定义f(0)=1,原递推公式可变为f(n) = f(n-1)f(0) + f(n-2)f(1) + f(n-3)f(2) + ... + f(1)f(n-2) +... f(n-1)f(0),这个表达式叫做 Catalan数。那么我们会想这个表达式有没有通项公式呢,答案是肯定的。
Catalan数通项公式推导
在推导通项公式之前,首先说一下生成函数
Catanlan数通向公式推导过程,这里用到了生成函数:我们可以写出f(n)的生成函数:f(x) = f(0)x^0+f(1)x+f(2)x^2+...+...
[f(x)]²= f(0)^2x^0+(f(0)f(1)+f(1)f(0))x+(f(0)f(2)+f(1)f(1)+f(2)f(0))x^2+...+(f(0)f(n-1)+f(1)f(n-2)+...+f(n-1)f(0))x^(n-1)+...
因为f(n) = f(n-1)f(0) + f(n-2)f(1) + f(n-3)f(2) + ... + f(1)f(n-2) +...
所以[f(x)]^2 = f(0)+f(2)x+f(3)x^2+...+f(n)x^(n-1)+...,因为f(0)=f(1)=1, 所以[f(x)]^2 = f(x)-f(1)x = f(x)-x,解得
, 根据广义牛顿二项式,将f(x)进行泰勒级数展开得
所以
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- Service Mesh 形态刍议
- 一起来学opencv(四):形态转换
- 敏捷DoD和DoR的多种形态
- Opencv图像处理系列(五)—— 形态变化
- opencv中的图像形态学——腐蚀膨胀
- 深度 | 解读神经形态计算:从基本原理到实验验证
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
爱上Arduino
Massimo Banzi / 于欣龙、郭浩赟 / 人民邮电出版社 / 2012-10 / 38.00元
《硬件开源电子设计平台:爱上Arduino(第2版)》全面透彻地介绍了arduino的相关内容,它会给你带来许多项目的点子,并帮助你顺利地实现从开始策划直到完成安装的全过程。由于《硬件开源电子设计平台:爱上Arduino(第2版)》是arduino项目合作创始人massimobanzi所著,其中一定融入了创始人对开源硬件的独到见解。《硬件开源电子设计平台:爱上Arduino(第2版)》内容完全考虑......一起来看看 《爱上Arduino》 这本书的介绍吧!