关于二叉树形态的推导

内容简介：对于二叉树形态，可以从二叉树本身的规律去找，离不开递推先考虑只有一个节点的情况，设此时的形态为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)进行泰勒级数展开得

所以

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

关注我们，获取更多IT资讯^_^

查看所有标签

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。