收藏本站 收藏本站
積木網首頁 - 軟件測試 - 常用手冊 - 站長工具 - 技術社區
首頁 > python > 正文

首頁 - PHP - 數據庫 - 操作系統 - 游戲開發 - JS - Android - MySql - Redis - MongoDB - Win8 - Shell編程 - DOS命令 - jQuery - CSS樣式 - Python - Perl

Access - Oracle - DB2 - SQLServer - MsSql2008 - MsSql2005 - Sqlite - PostgreSQL - node.js - extjs - JavaScript vbs - Powershell - Ruby

Python算法之求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)
# 節點
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 列表理解及使用方法
Python列表理解及使用方法列表是最常用的Python最常用的數據類型,它和其它序列一樣,可以進行包括索引,切片,加,乘,檢查成員的操作。列表的數據

Python探索之爬取電商售賣信息代碼示例
網絡爬蟲(又被稱為網頁蜘蛛,網絡機器人,在FOAF社區中間,更經常的稱為網頁追逐者),是一種按照一定的規則,自動的抓取萬維網信息的程序或者

Python探索之靜態方法和類方法的區別詳解
面相對象程序設計中,類方法和靜態方法是經常用到的兩個術語。邏輯上講:類方法是只能由類名調用;靜態方法可以由類名或對象名進行調用。pythonst

本周排行

更新排行

強悍的草根IT技術社區,這里應該有您想要的! 友情鏈接:b2b電子商務
Copyright © 2010 Gimoo.Net. All Rights Rreserved  京ICP備05050695號
时时彩免费分析软件