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

yipeiwu_com5年前Python基础

问题

创建一个二叉树

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

空集

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

创建二叉树:

创建节点

再创建节点之间的关系

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 openpyxl读取单元格字体颜色过程解析

问题 我试图打印some_cell.font.color.rgb并得到各种结果。 对于一些人,我得到了我想要的东西(比如“ FF000000”),但对于其他人,它给了我Value mus...

python 实现手机自动拨打电话的方法(通话压力测试)

现在能用自动化实现的,尽量使用自动化程序去操作,代替人工去操作,更有效率。 今天说下用python结合adb命令去实现安卓手机端的通话压力测试。 #操作前先在设置里打开power键可...

python开发之thread线程基础实例入门

本文实例讲述了python开发之thread线程基础。分享给大家供大家参考,具体如下: 说到线程,我们要知道啥是串行,啥是并行程序 举个例子: 串行程序,就是一个一个的执行程序 #p...

Python实现的简单线性回归算法实例分析

本文实例讲述了Python实现的简单线性回归算法。分享给大家供大家参考,具体如下: 用python实现R的线性模型(lm)中一元线性回归的简单方法,使用R的women示例数据,R的运行结...

Python获取航线信息并且制作成图的讲解

Python获取航线信息并且制作成图的讲解

获取航线信息并且制作成图 航线信息 航线信息查询网站 本次实例使用的航班号为 CES5496 查询后在network中可以寻找到如下内容https://zh.flighta...