关于二叉树形态的推导

栏目: 数据库 · 发布时间: 5年前

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

关于二叉树形态的推导

所以

关于二叉树形态的推导

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

查看所有标签

猜你喜欢:

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

轻量级Django

轻量级Django

茱莉亚·埃尔曼 (Julia Elman)、马克·拉温 (Mark Lavin) / 侯荣涛、吴磊 / 中国电力出版社; 第1版 / 2016-11-1 / 35.6

自Django 创建以来,各种各样的开源社区已经构建了很多Web 框架,比如JavaScript 社区创建的Angular.js 、Ember.js 和Backbone.js 之类面向前端的Web 框架,它们是现代Web 开发中的先驱。Django 从哪里入手来适应这些框架呢?我们如何将客户端MVC 框架整合成为当前的Django 基础架构? 本书讲述如何利用Django 强大的“自支持”功......一起来看看 《轻量级Django》 这本书的介绍吧!

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具