posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

搜索二叉树中节点数为m的子树的数量

Posted on 2007-06-06 17:40 ZelluX 阅读(621) 评论(0)  编辑  收藏 所属分类: Algorithm

发信人: DragonZhao (狂抽猛干·抽时间干事业), 信区: Algorithm
标 题: 一个问题
发信站: 日月光华 (2007年05月21日01:26:41 星期一), 站内信件


已知存在二叉树节点结构node{node* left; node* right};,现在给出树的根节点node*
root与自然数int m,要求搜索此树中节点数为m的子树的数量。如何做效率最高?

发信人: wshxzt (WKFB2008), 信区: Algorithm
标 题: Re: 一个问题
发信站: 日月光华 (2007年05月21日01:28:34 星期一), 站内信件

树的动态规划

发信人: lovebei (0124·皮皮和卡卡), 信区: Algorithm
标 题: Re: 一个问题
发信站: 日月光华 (2007年06月06日13:36:43 星期三), 站内信件


以i为根节点 节点数为j的子树个数

p[i][j]=∑{p[left(i)][k]*p[right(i)][j-k-1]} 0<=k<=j-1

发信人: Jeru (柠檬树), 信区: Algorithm
标 题: Re: 一个问题
发信站: 日月光华 (2007年06月06日13:59:36 星期三), 站内信件

没错的。不过硬要说是动态规划也没错,这个概念太宽泛了。


发信人: jesseg (Jesse : 我是花朵,祖国的希望!), 信区: Algorithm
标 题: Re: 一个问题
发信站: 日月光华 (2007年06月06日16:12:04 星期三)

其实这不至于算dp啦,dp的好处没发挥出来,呵呵,树状的搜索不用dp的,要图状的时候
dp才能省计算。


只有注册用户登录后才能发表评论。


网站导航: