快捷導(dǎo)航

Python算法之求n個(gè)節(jié)點(diǎn)不同二叉樹(shù)個(gè)數(shù)

更新時(shí)間：2017年10月27日 15:22:34 作者：玩蛇的

本文先向大家分享了建立二叉樹(shù)的簡(jiǎn)單代碼，其次介紹了Python計(jì)算n個(gè)節(jié)點(diǎn)不同二叉樹(shù)個(gè)數(shù)的問(wèn)題及實(shí)現(xiàn)代碼示例，具有一定參考價(jià)值，需要的朋友可以了解下。

問(wèn)題

創(chuàng)建一個(gè)二叉樹(shù)

二叉樹(shù)有限多個(gè)節(jié)點(diǎn)的集合，這個(gè)集合可能是：

空集

由一個(gè)根節(jié)點(diǎn)，和兩棵互不相交的，分別稱(chēng)作左子樹(shù)和右子樹(shù)的二叉樹(shù)組成

創(chuàng)建二叉樹(shù):

創(chuàng)建節(jié)點(diǎn)

再創(chuàng)建節(jié)點(diǎn)之間的關(guā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)
# 節(jié)點(diǎn)
A = TreeNode('A')
B = TreeNode('B')
C = TreeNode('C')
D = TreeNode('D')
# 節(jié)點(diǎn)間的關(guān)系
A.left = B
A.right = C
B.right = D
print B.right

問(wèn)題

求n個(gè)節(jié)點(diǎn)不同二叉樹(shù)個(gè)數(shù)

1個(gè)節(jié)點(diǎn)
根節(jié)點(diǎn)1 1種
1種二叉樹(shù)

2個(gè)節(jié)點(diǎn)
根節(jié)點(diǎn)1 左節(jié)點(diǎn)1 1種（依照1節(jié)點(diǎn)的推斷）
根節(jié)點(diǎn)1 右節(jié)點(diǎn)1 1種（依照1節(jié)點(diǎn)的推斷）
2種二叉樹(shù)

3個(gè)節(jié)點(diǎn)
根節(jié)點(diǎn)1 左節(jié)點(diǎn)0 右節(jié)點(diǎn)2 2種（依照2節(jié)點(diǎn)的推斷）
根節(jié)點(diǎn)1 左節(jié)點(diǎn)1 右節(jié)點(diǎn)1 1種（依照1節(jié)點(diǎn)的推斷）
根節(jié)點(diǎn)1 左節(jié)點(diǎn)2 右節(jié)點(diǎn)0 2種（依照2節(jié)點(diǎn)的推斷）
5種二叉樹(shù)

4個(gè)節(jié)點(diǎn)
根節(jié)點(diǎn)1 左節(jié)點(diǎn)0 右節(jié)點(diǎn)3 5種（依照3節(jié)點(diǎn)的推斷）
根節(jié)點(diǎn)1 左節(jié)點(diǎn)1 右節(jié)點(diǎn)2 2種（依照2節(jié)點(diǎn)的推斷）
根節(jié)點(diǎn)1 左節(jié)點(diǎn)2 右節(jié)點(diǎn)1 2種（依照2節(jié)點(diǎn)的推斷）
根節(jié)點(diǎn)1 左節(jié)點(diǎn)3 右節(jié)點(diǎn)0 5種（依照4上面的推斷）
共14種二叉樹(shù)

...

n個(gè)節(jié)點(diǎn)

遞歸進(jìn)行累加

Python代碼示例

# !/usr/bin/env python
# -*-encoding: utf-8-*-
# author:LiYanwei
# version:0.1
# 求n個(gè)節(jié)點(diǎn)不同二叉樹(shù)個(gè)數(shù)
def count(n):
  # root : 1
  # left : k
  # right : n - 1- k
  # s = 0
  # if n == 0:
  #   # 空樹(shù)
  #   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
# 重復(fù)計(jì)算優(yōu)化
count.cache = {0 : 1}
print count(100)

總結(jié)

以上就是本文關(guān)于Python算法之求n個(gè)節(jié)點(diǎn)不同二叉樹(shù)個(gè)數(shù)的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站：Python探索之自定義實(shí)現(xiàn)線(xiàn)程池、python中模塊的__all__屬性詳解等，如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！

您可能感興趣的文章: