欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2017年10月27日 15:22:34   作者:玩蛇的  
本文先向大家分享了建立二叉樹的簡單代碼,其次介紹了Python計算n個節(jié)點不同二叉樹個數(shù)的問題及實現(xiàn)代碼示例,具有一定參考價值,需要的朋友可以了解下。

問題

創(chuàng)建一個二叉樹

二叉樹有限多個節(jié)點的集合,這個集合可能是:

空集

由一個根節(jié)點,和兩棵互不相交的,分別稱作左子樹和右子樹的二叉樹組成

創(chuàng)建二叉樹:

創(chuàng)建節(jié)點

再創(chuàng)建節(jié)點之間的關系

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é)點
A = TreeNode('A')
B = TreeNode('B')
C = TreeNode('C')
D = TreeNode('D')
# 節(jié)點間的關系
A.left = B
A.right = C
B.right = D
print 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代碼示例

# !/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)

總結

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

相關文章

  • 使用Numpy打亂數(shù)組或打亂矩陣行

    使用Numpy打亂數(shù)組或打亂矩陣行

    這篇文章主要介紹了使用Numpy打亂數(shù)組或打亂矩陣行問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-05-05
  • 對python中的iter()函數(shù)與next()函數(shù)詳解

    對python中的iter()函數(shù)與next()函數(shù)詳解

    今天小編就為大家分享一篇對python中的iter()函數(shù)與next()函數(shù)詳解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-10-10
  • Python Tkinter對話框控件使用詳解

    Python Tkinter對話框控件使用詳解

    Tkinter中提供了三種對話框控件:文件選擇對話框、顏色選擇對話框和消息對話框。本文將具體為大家介紹一下這三種對話框的使用,需要的可以參考一下
    2022-01-01
  • 淺談算法之最小生成樹Kruskal的Python實現(xiàn)

    淺談算法之最小生成樹Kruskal的Python實現(xiàn)

    最小生成樹Kruskal算法可以稱為“加邊法”,初始最小生成樹邊數(shù)為0,每迭代一次就選擇一條滿足條件的最小代價邊,加入到最小生成樹的邊集合里。本文將介紹它的原理,并用Python進行實現(xiàn)
    2021-06-06
  • Python numpy 模塊介紹

    Python numpy 模塊介紹

    這篇文章主要介紹了Python numpy 模塊,在motplotlib的學習過程中,我們使用最多的就是numpy模塊。下面我們將使用numpy進行創(chuàng)建數(shù)組、切片、索引、廣播等功能實操,需要的朋友可以參考一下
    2022-01-01
  • Python數(shù)據(jù)結構之隊列詳解

    Python數(shù)據(jù)結構之隊列詳解

    棧和隊列是在程序設計中常見的數(shù)據(jù)類型。本節(jié)將詳細介紹隊列的定義及其不同實現(xiàn),并且給出隊列的一些實際應用,感興趣的小伙伴可以了解一下
    2022-03-03
  • Python pkg_resources模塊動態(tài)加載插件實例分析

    Python pkg_resources模塊動態(tài)加載插件實例分析

    當編寫應用軟件時,我們通常希望程序具有一定的擴展性,額外的功能——甚至所有非核心的功能,都能通過插件實現(xiàn),具有可插拔性。特別是使用 Python 編寫的程序,由于語言本身的動態(tài)特性,為我們的插件方案提供了很多種實現(xiàn)方式
    2022-08-08
  • 如何利用Python開發(fā)一個簡單的猜數(shù)字游戲

    如何利用Python開發(fā)一個簡單的猜數(shù)字游戲

    這篇文章主要給大家介紹了關于如何利用Python開發(fā)一個簡單的猜數(shù)字游戲的相關資料,文中通過示例代碼介紹的非常詳細,對大家學習或者使用Python具有一定的參考學習價值,需要的朋友們下面來一起學習學習吧
    2019-09-09
  • Python上級目錄文件導入的幾種方法(from.import)

    Python上級目錄文件導入的幾種方法(from.import)

    有時候我們可能需要import另一個路徑下的python文件,下面這篇文章主要給大家介紹了關于Python上級目錄文件導入的幾種方法,文中通過代碼介紹的非常詳細,需要的朋友可以參考下
    2023-12-12
  • Django urls.py重構及參數(shù)傳遞詳解

    Django urls.py重構及參數(shù)傳遞詳解

    這篇文章主要介紹了Django urls.py重構及參數(shù)傳遞詳解,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-07-07

最新評論