Python算法之求n个节点不同二叉树个数
问题
创建一个二叉树
二叉树有限多个节点的集合,这个集合可能是:
空集
由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成
创建二叉树:
创建节点
再创建节点之间的关系
Python代码示例
#!/usr/bin/envpython #-*-encoding:utf-8-*- #author:LiYanwei #version:0.1 classTreeNode(object): def__init__(self,data,left=None,right=None): self.data=data self.left=left self.right=right def__str__(self): returnstr(self.data) #节点 A=TreeNode('A') B=TreeNode('B') C=TreeNode('C') D=TreeNode('D') #节点间的关系 A.left=B A.right=C B.right=D printB.right
问题
求n个节点不同二叉树个数
1个节点
根节点11种
1种二叉树
2个节点
根节点1左节点11种(依照1节点的推断)
根节点1右节点11种(依照1节点的推断)
2种二叉树
3个节点
根节点1左节点0右节点22种(依照2节点的推断)
根节点1左节点1右节点11种(依照1节点的推断)
根节点1左节点2右节点02种(依照2节点的推断)
5种二叉树
4个节点
根节点1左节点0右节点35种(依照3节点的推断)
根节点1左节点1右节点22种(依照2节点的推断)
根节点1左节点2右节点12种(依照2节点的推断)
根节点1左节点3右节点05种(依照4上面的推断)
共14种二叉树
...
n个节点
递归进行累加
Python代码示例
#!/usr/bin/envpython #-*-encoding:utf-8-*- #author:LiYanwei #version:0.1 #求n个节点不同二叉树个数 defcount(n): #root:1 #left:k #right:n-1-k #s=0 #ifn==0: ##空树 #return1 s=count.cache.get(n,0) ifs: returns forkinxrange(n): s+=count(k)*count(n-1-k) count.cache[n]=s returns #重复计算优化 count.cache={0:1} printcount(100)
以上就是本文关于Python算法之求n个节点不同二叉树个数的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:Python探索之自定义实现线程池、python中模块的__all__属性详解等,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!