python行為樹

1. python裡面二項樹怎麼表示

class Tree:
def __init__(self,entry,left=None,right=None):
self.entry=entry
self.left=left
self.right=right
def __repr__(self):
args=repr(self.entry)
if self.left or self.right:
args+=',{0},{1}'.format(repr(self.left),repr(self.right))
return 'Tree({0})'.format(args)
def square_tree(t):
if t==None:
return
else:
t.entry=t.entry**2
square_tree(t.left)
square_tree(t.right)
def height(t):
if t==None:
return 0
else:
return 1+max(height(t.left),height(t.right))
def size(t):
if t==None:
return 0
else:
return size(t.left)+size(t.right)+1
def find_path(t,x):
if t==None:
return None
elif t.entry==x:
return (x,)
left=find_path(t.left,x);right=find_path(t.right,x)
if left:
return (t.entry,)+left
elif right:
return (t.entry,)+right
else:
return None
t=Tree(2,Tree(7,Tree(2),Tree(6,Tree(5),Tree(11))),Tree(15))
print(t)
a=find_path(t,5)
print(a)

2. 用python畫一棵樹

1、准備

• 1

  打開我們的Python shell界面，也就是大家所說的idle界面。

  

3. python中的數據結構分析

1.Python數據結構篇

數據結構篇主要是閱讀[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [該網址鏈接可能會比較慢]時寫下的閱讀記錄，當然，也結合了部分[演算法導論](Introction to Algorithms)
中的內容，此外還有不少wikipedia上的內容，所以內容比較多，可能有點雜亂。這部分主要是介紹了如何使用Python實現常用的一些數據結構，例
如堆棧、隊列、二叉樹等等，也有Python內置的數據結構性能的分析，同時還包括了搜索和排序(在演算法設計篇中會有更加詳細的介紹)的簡單總結。每篇文
章都有實現代碼，內容比較多，簡單演算法一般是大致介紹下思想及演算法流程，復雜的演算法會給出各種圖示和代碼實現詳細介紹。

**這一部分是下
面演算法設計篇的前篇，如果數據結構還不錯的可以直接看演算法設計篇，遇到問題可以回來看數據結構篇中的某個具體內容充電一下，我個人認為直接讀演算法設計篇比
較好，因為大家時間也都比較寶貴，如果你會來讀這些文章說明你肯定有一定基礎了，後面的演算法設計篇中更多的是思想，這里更多的是代碼而已，嘿嘿。**

(1)[搜索](Python Data Structures)

簡述順序查找和二分查找，詳述Hash查找(hash函數的設計以及如何避免沖突)

(2)[排序](Python Data Structures)

簡述各種排序演算法的思想以及它的圖示和實現

(3)[數據結構](Python Data Structures)

簡述Python內置數據結構的性能分析和實現常用的數據結構：棧、隊列和二叉堆

(4)[樹總結](Python Data Structures)

簡述二叉樹，詳述二叉搜索樹和AVL樹的思想和實現

2.Python演算法設計篇

演算法設計篇主要是閱讀[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**點擊鏈接可進入Springer免費下載原書電子版**]之後寫下的讀書總結，原書大部分內容結合了經典書籍[演算法導論](Introction to Algorithms)，
內容更加細致深入，主要是介紹了各種常用的演算法設計思想，以及如何使用Python高效巧妙地實現這些演算法，這里有別於前面的數據結構篇，部分演算法例如排
序就不會詳細介紹它的實現細節，而是側重於它內在的演算法思想。這部分使用了一些與數據結構有關的第三方模塊，因為這篇的重點是演算法的思想以及實現，所以並
沒有去重新實現每個數據結構，但是在介紹演算法的同時會分析Python內置數據結構以及第三方數據結構模塊的優缺點，也就意味著該篇比前面都要難不少，但
是我想我的介紹應該還算簡單明了，因為我用的都是比較朴實的語言，並沒有像演算法導論一樣列出一堆性質和定理，主要是對著某個問題一步步思考然後演算法就出來
了，嘿嘿，除此之外，裡面還有很多關於python開發的內容，精彩真的不容錯過！

這里每篇文章都有實現代碼，但是代碼我一般都不會分
析，更多地是分析演算法思想，所以內容都比較多，即便如此也沒有包括原書對應章節的所有內容，因為內容實在太豐富了，所以我只是選擇經典的演算法實例來介紹算
法核心思想，除此之外，還有不少內容是原書沒有的，部分是來自演算法導論，部分是來自我自己的感悟，嘻嘻。該篇對於大神們來說是小菜，請一笑而過，對於菜鳥
們來說可能有點難啃，所以最適合的是和我水平差不多的，對各個演算法都有所了解但是理解還不算深刻的半桶水的程序猿，嘿嘿。

本篇的順序按照原書[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章節來安排的(章節標題部分相同部分不同喲)，為了節省時間以及保持原著的原滋原味，部分內容(一般是比較難以翻譯和理解的內容)直接摘自原著英文內容。

**1.
你也許覺得很多內容你都知道嘛，沒有看的必要，其實如果是我的話我也會這么想，但是如果只是歸納一個演算法有哪些步驟，那這個總結也就沒有意義了，我覺得這
個總結的亮點在於想辦法說清楚一個演算法是怎麼想出來的，有哪些需要注意的，如何進行優化的等等，採用問答式的方式讓讀者和我一起來想出某個問題的解，每篇
文章之後都還有一兩道小題練手喲**

**2.你也許還會說演算法導論不是既權威又全面么，基本上每個演算法都還有詳細的證明呢，讀演算法導論豈
不更好些，當然，你如果想讀演算法導論的話我不攔著你，讀完了感覺自己整個人都不好了別怪小弟沒有提醒你喲，嘻嘻嘻，左一個性質右一個定理實在不適合演算法科
普的啦，沒有多少人能夠堅持讀完的。但是碼農與蛇的故事內容不多喲，呵呵呵**

**3.如果你細讀本系列的話我保證你會有不少收獲的，需要看演算法導論哪個部分的地方我會給出提示的，嘿嘿。溫馨提示，前面三節內容都是介紹基礎知識，所以精彩內容從第4節開始喲，么么噠 O(∩_∩)O~**

(1)[Python Algorithms - C1 Introction](Python Algorithms)

本節主要是對原書中的內容做些簡單介紹，說明演算法的重要性以及各章節的內容概要。

(2)[Python Algorithms - C2 The basics](Python Algorithms)

**本節主要介紹了三個內容：演算法漸近運行時間的表示方法、六條演算法性能評估的經驗以及Python中樹和圖的實現方式。**

(3)[Python Algorithms - C3 Counting 101](Python Algorithms)

原書主要介紹了一些基礎數學，例如排列組合以及遞歸循環等，但是本節只重點介紹計算演算法的運行時間的三種方法

(4)[Python Algorithms - C4 Inction and Recursion and Rection](Python Algorithms)

**本節主要介紹演算法設計的三個核心知識：Inction(推導)、Recursion(遞歸)和Rection(規約)，這是原書的重點和難點部分**

(5)[Python Algorithms - C5 Traversal](Python Algorithms)

**本節主要介紹圖的遍歷演算法BFS和DFS，以及對拓撲排序的另一種解法和尋找圖的(強)連通分量的演算法**

(6)[Python Algorithms - C6 Divide and Combine and Conquer](Python Algorithms)

**本節主要介紹分治法策略，提到了樹形問題的平衡性以及基於分治策略的排序演算法**

(7)[Python Algorithms - C7 Greedy](Python Algorithms)

**本節主要通過幾個例子來介紹貪心策略，主要包括背包問題、哈夫曼編碼和最小生成樹等等**

(8)[Python Algorithms - C8 Dynamic Programming](Python Algorithms)

**本節主要結合一些經典的動規問題介紹動態規劃的備忘錄法和迭代法這兩種實現方式，並對這兩種方式進行對比**

(9)[Python Algorithms - C9 Graphs](Python Algorithms)

**本節主要介紹圖演算法中的各種最短路徑演算法，從不同的角度揭示它們的內核以及它們的異同**

4. Python中的樹你知道嗎

樹與二叉樹

在了解二叉樹之前，我們要先了解樹的一些概念，方便我們對二叉樹的理解。

什麼是樹？

樹(英語:tree)是一種抽象數據類型(ADT)或是實作這種抽象數據類型的數據結構,用來模擬具有樹狀結構性質的數據集合。

它是由n(n>=1)個有限節點組成一個具有層次關系的集合。把它叫做「樹」是因為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。它具有以下的特點:

每個節點有零個或多個子節點;

沒有父節點的節點稱為根節點;

每一個非根節點有且只有一個父節點;

除了根節點外,每個子節點可以分為多個不相交的子樹;

樹的術語：

節點的度: 一個節點含有的子樹的個數稱為該節點的度;

樹的度: 一棵樹中,最大的節點的度稱為樹的度;

根結點： 樹的最頂端的節點，繼續往下分為子節點

父節點： 子節點的上一層為父節點

兄弟節點： 具有同一個父節點的節點稱為兄弟節點

葉子節點/終端節點： 不再有子節點的節點為葉子節點

二叉樹：

二叉樹是樹的特殊一種，具有如下特點：

每個節點最多有兩個子樹，節點的度最大為2

左子樹和右子樹是有順序的，次序不能顛倒

即是某節點只有一個子樹，也要區分左右子樹

二叉樹的性質：

在非空二叉樹的第i層，最多有2i-1個節點(i>=1)

在深度為K的二叉樹上最多有2k-1個節點(k>.1)

對於任意一個非空的二叉樹，如果葉子節點個數為n0，度數為2的節點數為n2，則有n0=n2+1

推倒過程：在一棵二叉樹中，除了葉子節點（度為0）外，就剩下度為2(n2)和度為1(n1)的節點了。則樹的節點總數為T = n0 + n1 + n2；在二叉樹中節點總數為T，而連線總數為T-1 = 2*n2 + n1，所以就有：n0 + n1 + n2 - 1 = 2 *n2 + n1，得到n0=n2+1。

特殊的二叉樹

滿二叉樹

在二叉樹中除了葉子節點，其他所有節點的度為2，且所有的葉子節點都在同一層上，這樣的二叉樹成為滿二叉樹。

滿二叉樹的特點：

葉子節點只能出現在最下一層

非葉子節點度數一定為2

在同樣深度的二叉樹中，滿二叉樹的節點個數最多，葉子節點數最多

完全二叉樹

如果二叉樹中除去最後一層葉子節點後為滿二叉樹，且最後一層的葉子節點依次從左到右分布，則這樣的二叉樹稱為完全二叉樹

完全二叉樹的特點：

葉子節點一般出現在最下一層，如果倒數第二層出現葉子節點，一定出現在右部連續位置

最下層葉子節點一定集中在左部連續位置

同樣節點的二叉樹，完全二叉樹的深度最小（滿二叉樹也對）

小例題：

某完全二叉樹共有200個節點，該二叉樹中共有（）個葉子節點？

解：n0 + n1 + n2 = 200， 其中n0 = n2 + 1，n1 = 0或者1 （n1=1，出現在最下一層節點數為奇數，最下一層節點數為偶數，則n1=0）， 因為n0為整數，所以最後算得n0 = 100。

完全二叉樹的性質：

具有n個節點的完全二叉樹的深度為log2n+1。log2n結果取整數部分。

如果有一棵有n個節點的完全二叉樹的節點按層次序編號，對任一層的節點i(1 <= i <= n)

1. 如果i=1，則節點是二叉樹的根，無父節點，如果i>1,則其父節點為i/2，向下取整

2. 如果2*1>n，那麼節點i沒有左孩子，否則其左孩子為2i

3. 如果2i+1>n那麼節點沒有右孩子，否則右孩子為2i+1

驗證：

第一條：

當i=1時，為根節點。當i>1時，比如結點為7，他的雙親就是7/2= 3；結點9雙親為4.

第二條：

結點6,62 = 12>10，所以結點6無左孩子，是葉子結點。結點5，52 = 10，左孩子是10,結點4，為8.

第三條：

結點5，2*5+1>10,沒有右孩子，結點4，則有右孩子。

更多Python相關知識，請移步Python視頻教程繼續學習！！

5. python 二叉樹實現思想

第一 ：return 的縮進不對 ，

ifself.root==None:
self.root=node
return#如果這里不縮進，下面的語句無意義，直接返回，不會執行。

while queue這個循環的作用的是從root根結點開始，向下查找第一個左(右)子結點為空的結點，將node插入這個位置,queue的作用是將查找到的非空子結點保存在queue中，然後依次向下查找這些子結點的左右子結點

6. 網易游戲和騰訊游戲的服務端是用什麼語言開發的

服務端不同的引擎用的不同的語言，但是核心都是C++寫的。
unity是C#+lua，lua有很多插件xlua 和slua等等。
UE4是C++配合unlua。
網易伺服器是自研服務端引擎，一般是lpc、python或者lua

7. Python 二叉樹的創建和遍歷、重建

幾個有限元素的集合，該集合為空或者由一個根（Root）的元素及兩不相交的（左子樹和右子樹）的二叉樹組成，是有序樹，當集合為空時，稱為空二叉樹，在二叉樹中，一個元素也稱為一個結點。

前序遍歷：若二叉樹為空，則空操作返回，否則先訪問根結點，然後前序遍歷左子樹，再前序遍歷右子樹

中序遍歷：若樹為空，則空操作返回，否則從根結點開始（不是先訪問根結點），中序遍歷根結點的左子樹，然後訪問根節點，最後中序遍歷右子樹。

後序遍歷：若樹為空，則空操作返回，否則從左到右先訪問葉子結點後結點的方式遍歷左右子樹，最後訪問根節點。

層序遍歷：若樹為空，則空操作返回，否則從樹的每一層，即從根節點開始訪問，從上到下逐層遍歷，在同一層中，按從左到右的順序對結點逐個訪問。

假設已知後序遍歷和中序遍歷結果，從後序遍歷的結果可以等到最後一個訪問的結點是根節點，對於最簡單的二叉樹，此時在中序遍歷中找到根節點之後，可以分辨出左右子樹，這樣就可以重建出這個最簡單的二叉樹了。而對於更為復雜的二叉樹，重建得到根結點和暫時混亂的左右結點，通過遞歸將左右結點依次重建為子二叉樹，即可完成整個二叉樹的重建。（在得到根結點之後，需要在中序遍歷序列中尋找根結點的位置，並將中序序列拆分為左右部分，所以要求序列中不能有相同的數字，這是序列重建為二叉樹的前提。）

Root =None

strs="abc##d##e##"   #前序遍歷擴展的二叉樹序列

vals =list(strs)

Roots=Create_Tree(Root,vals)#Roots就是我們要的二叉樹的根節點。

print(Roots)

inorderSearch = inOrderTraverse2(Roots)

print(inorderSearch)

8. python中 怎麼把輸入是一個有包含關系的列表 生成樹形數據結構

fatherid就是節點在list中的下標，childreni[]放所有子節點在list中的下標，總之就是用下標來標記