問題
創(chuàng)建一個二叉樹
二叉樹有限多個節(jié)點的集合，這個集合可能是：
空集
由一個根節(jié)點，和兩棵互不相交的，分別稱作左子樹和右子樹的二叉樹組成
創(chuàng)建二叉樹:
創(chuàng)建節(jié)點
再創(chuàng)建節(jié)點之間的關(guān)系
Python代碼示例
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
# !/usr/bin/env python# -*-encoding: utf-8-*-# author:LiYanwei# version:0.1class 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)# 節(jié)點A = TreeNode('A')B = TreeNode('B')C = TreeNode('C')D = TreeNode('D')# 節(jié)點間的關(guān)系A.left = BA.right = CB.right = Dprint B.right |
問題
求n個節(jié)點不同二叉樹個數(shù)
1個節(jié)點
根節(jié)點1 1種
1種二叉樹
2個節(jié)點
根節(jié)點1 左節(jié)點1 1種（依照1節(jié)點的推斷）
根節(jié)點1 右節(jié)點1 1種（依照1節(jié)點的推斷）
2種二叉樹
3個節(jié)點
根節(jié)點1 左節(jié)點0 右節(jié)點2 2種（依照2節(jié)點的推斷）
根節(jié)點1 左節(jié)點1 右節(jié)點1 1種（依照1節(jié)點的推斷）
根節(jié)點1 左節(jié)點2 右節(jié)點0 2種（依照2節(jié)點的推斷）
5種二叉樹
4個節(jié)點
根節(jié)點1 左節(jié)點0 右節(jié)點3 5種（依照3節(jié)點的推斷）
根節(jié)點1 左節(jié)點1 右節(jié)點2 2種（依照2節(jié)點的推斷）
根節(jié)點1 左節(jié)點2 右節(jié)點1 2種（依照2節(jié)點的推斷）
根節(jié)點1 左節(jié)點3 右節(jié)點0 5種（依照4上面的推斷）
共14種二叉樹
...
n個節(jié)點
遞歸進行累加
Python代碼示例
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
# !/usr/bin/env python# -*-encoding: utf-8-*-# author:LiYanwei# version:0.1# 求n個節(jié)點不同二叉樹個數(shù)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# 重復計算優(yōu)化count.cache = {0 : 1}print count(100) |
總結(jié)
以上就是本文關(guān)于Python算法之求n個節(jié)點不同二叉樹個數(shù)的全部內(nèi)容，希望對大家有所幫助。如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://www.cnblogs.com/Py00/p/7726550.html
