收藏本站 收藏本站
积木网首页 - 软件测试 - 常用手册 - 站长工具 - 技术社区
首页 > python > 正文

首页 - PHP - 数据库 - 操作系统 - 游戏开发 - JS - Android - MySql - Redis - MongoDB - Win8 - Shell编程 - DOS命令 - jQuery - CSS样式 - Python - Perl

Access - Oracle - DB2 - SQLServer - MsSql2008 - MsSql2005 - Sqlite - PostgreSQL - node.js - extjs - JavaScript vbs - Powershell - Ruby

Python算法之求n个节点不同二叉树个数

问题

创建一个二叉树

二叉树有限多个节点的集合,这个集合可能是:

空集

由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成

创建二叉树:

创建节点

再创建节点之间的关系

Python代码示例

# !/usr/bin/env python
# -*-encoding: utf-8-*-
# author:LiYanwei
# version:0.1
class TreeNode(object):
  def __init__ (self, data, left = None, right = None):
    self.data = data
    self.left = left
    self.right = right
  def __str__(self):
    return str(self.data)
# 节点
A = TreeNode('A')
B = TreeNode('B')
C = TreeNode('C')
D = TreeNode('D')
# 节点间的关系
A.left = B
A.right = C
B.right = D
print B.right

问题

求n个节点不同二叉树个数

1个节点
根节点1 1种
1种二叉树

2个节点
根节点1 左节点1 1种(依照1节点的推断)
根节点1 右节点1 1种(依照1节点的推断)
2种二叉树

3个节点
根节点1 左节点0 右节点2 2种(依照2节点的推断)
根节点1 左节点1 右节点1 1种(依照1节点的推断)
根节点1 左节点2 右节点0 2种(依照2节点的推断)
5种二叉树

4个节点
根节点1 左节点0 右节点3 5种(依照3节点的推断)
根节点1 左节点1 右节点2 2种(依照2节点的推断)
根节点1 左节点2 右节点1 2种(依照2节点的推断)
根节点1 左节点3 右节点0 5种(依照4上面的推断)
共14种二叉树

...

n个节点

递归进行累加

Python代码示例

# !/usr/bin/env python
# -*-encoding: utf-8-*-
# author:LiYanwei
# version:0.1
# 求n个节点不同二叉树个数
def count(n):
  # root : 1
  # left : k
  # right : n - 1- k
  # s = 0
  # if n == 0:
  #   # 空树
  #   return 1
  s = count.cache.get(n, 0)
  if s:
    return s
  for k in xrange(n):
    s += count(k) * count(n - 1 - k)
  count.cache[n] = s
  return s
# 重复计算优化
count.cache = {0 : 1}
print count(100)

总结

以上就是本文关于Python算法之求n个节点不同二叉树个数的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:Python探索之自定义实现线程池、python中模块的__all__属性详解等,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

Python 列表理解及使用方法
Python列表理解及使用方法列表是最常用的Python最常用的数据类型,它和其它序列一样,可以进行包括索引,切片,加,乘,检查成员的操作。列表的数据

Python探索之爬取电商售卖信息代码示例
网络爬虫(又被称为网页蜘蛛,网络机器人,在FOAF社区中间,更经常的称为网页追逐者),是一种按照一定的规则,自动的抓取万维网信息的程序或者

Python探索之静态方法和类方法的区别详解
面相对象程序设计中,类方法和静态方法是经常用到的两个术语。逻辑上讲:类方法是只能由类名调用;静态方法可以由类名或对象名进行调用。pythonst

本周排行

更新排行

强悍的草根IT技术社区,这里应该有您想要的! 友情链接:b2b电子商务
Copyright © 2010 Gimoo.Net. All Rights Rreserved  京ICP备05050695号