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__属性详解等，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！