⑴ 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視頻教程繼續學習！！
⑵ 一道演算法題，用python初始化一顆二叉樹並求解其最短路徑的值
二叉樹演算法，可能按照你的需求不是很多：
下面是我用的一個，不過你可以借鑒一下的：
# -*- coding: cp936 -*-
import os
class Node(object):
"""docstring for Node"""
def __init__(self, v = None, left = None, right=None, parent=None):
self.value = v
self.left = left
self.right = right
self.parent = parent
class BTree(object):
"""docstring for BtTee """
def __init__(self):
self.root = None
self.size = 0
def insert(self, node):
n = self.root
if n == None:
self.root = node
return
while True:
if node.value <= n.value:
if n.left == None:
node.parent = n
n.left = node
break
else:
n = n.left
if node.value > n.value:
if n.right == None:
n.parent = n
n.right = node
break
else:
n = n.right
def find(self, v):
n = self.root # http://yige.org
while True:
if n == None:
return None
if v == n.value:
return n
if v < n.value:
n = n.left
continue
if v > n.value:
n = n.right
def find_successor(node):
'''查找後繼結點'''
assert node != None and node.right != None
n = node.right
while n.left != None:
n = n.left
return n
def delete(self, v):
n = self.find(v)
print "delete:",n.value
del_parent = n.parent
if del_parent == None:
self.root = None;
return
if n != None:
if n.left != None and n.right != None:
succ_node = find_successor(n)
parent = succ_node.parent
if succ_node == parent.left:
#if succ_node is left sub tree
parent.left = None
if succ_node == parent.right:
#if succ_node is right sub tree
parent.right = None
if del_parent.left == n:
del_parent.left = succ_node
if del_parent.right == n:
del_parent.right = succ_node
succ_node.parent = n.parent
succ_node.left = n.left
succ_node.right = n.right
del n
elif n.left != None or n.right != None:
if n.left != None:
node = n.left
else:
node = n.right
node.parent = n.parent
if del_parent.left == n:
del_parent.left = node
if del_parent.right == n:
del_parent.right = node
del n
else:
if del_parent.left == n:
del_parent.left = None
if del_parent.right == n:
del_parent.right = None
def tranverse(self):
def pnode(node):
if node == None:
return
if node.left != None:
pnode(node.left)
print node.value
if node.right != None:
pnode(node.right)
pnode(self.root)
def getopts():
import optparse, locale
parser = optparse.OptionParser()
parser.add_option("-i", "--input", dest="input", help=u"help name", metavar="INPUT")
(options, args) = parser.parse_args()
#print options.input
return (options.input)
if __name__ == '__main__':
al = [23, 45, 67, 12, 78,90, 11, 33, 55, 66, 89, 88 ,5,6,7,8,9,0,1,2,678]
bt = BTree()
for x in al :
bt.insert(Node(x))
bt.delete(12)
bt.tranverse()
n = bt.find(12)
if n != None:
print "find valud:",n.value
⑶ python字典怎麼表現二叉樹
用python構造一個n層的完全二叉樹的代碼如下： typedef struct {int weight;int parent, lchild, rchild; } HTNode ,*HuffmanTree; // 動態分配數組存儲huffman樹 演算法設計void createHuffmantree(){ ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode.
⑷ python中有哪些簡單的演算法
你好：
跟你詳細說一下python的常用8大演算法：
1、插入排序
插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入演算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最後一個元素除外(讓數組多一個空間才有插入的位置)，而第二部分就只包含這一個元素(即待插入元素)。在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分中。
2、希爾排序
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。該方法因DL．Shell於1959年提出而得名。 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
3、冒泡排序
它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。
4、快速排序
通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
5、直接選擇排序
基本思想：第1趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；第2趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；以此類推，第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢。
6、堆排序
堆排序(Heapsort)是指利用堆積樹(堆)這種數據結構所設計的一種排序演算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值，即A[PARENT[i]] >= A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
7、歸並排序
歸並排序是建立在歸並操作上的一種有效的排序演算法,該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。
歸並過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]復制到r[k]中，並令i和k分別加上1；否則將第二個有序表中的元素a[j]復制到r[k]中，並令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然後再將另一個有序表中剩餘的元素復制到r中從下標k到下標t的單元。歸並排序的演算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸並操作合並成有序的區間[s,t]。
8、基數排序
基數排序(radix sort)屬於「分配式排序」(distribution sort)，又稱「桶子法」(bucket sort)或bin sort，顧名思義，它是透過鍵值的部分資訊，將要排序的元素分配至某些「桶」中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所採取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的穩定性排序法。
⑸ python演算法有哪些
演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。
一個演算法應該具有以下七個重要的特徵：
①有窮性（Finiteness）：演算法的有窮性是指演算法必須能在執行有限個步驟之後終止；
②確切性(Definiteness)：演算法的每一步驟必須有確切的定義；
③輸入項(Input)：一個演算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸 入是指演算法本身定出了初始條件；
④輸出項(Output)：一個演算法有一個或多個輸出，以反映對輸入數據加工後的結果。沒 有輸出的演算法是毫無意義的；
⑤可行性(Effectiveness)：演算法中執行的任何計算步驟都是可以被分解為基本的可執行 的操作步，即每個計算步都可以在有限時間內完成（也稱之為有效性）；
⑥高效性(High efficiency)：執行速度快，佔用資源少；
⑦健壯性(Robustness)：對數據響應正確。
相關推薦：《Python基礎教程》
五種常見的Python演算法：
1、選擇排序
2、快速排序
3、二分查找
4、廣度優先搜索
5、貪婪演算法
⑹ 如何編制Python函數運用二叉樹定價模型進行投資決策
1、首先，將編制Python函數從左到右生成二叉樹。
2、其次，根據生成的二叉樹，從右向左計算期權價值。
3、最後，計算完成後，即可進行投資決策。
⑺ 如何用python構造一個n層的完全二叉樹
用python構造一個n層的完全二叉樹的代碼如下：
typedefstruct{
intweight;
intparent,lchild,rchild;
}HTNode,*HuffmanTree;//動態分配數組存儲huffman樹
演算法設計
voidcreateHuffmantree(){
ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);//動態分配數組存儲huffman樹,0號單元未用
//m:huffman樹中的結點數（m=2*n-1）
for(i=1;i<=m;++i)
ht[i].parent=ht[i]->lch=ht[i]->rch=0;
for(i=1;i<=n;++i)
ht[i].weight=w[i];//初始化，w[i]：n個葉子的權值
for(i=n+1;i<=m,++i)｛//建哈夫曼樹
select(i-1),s1,s2);//在ht[k](1<=k<=i-1)中選擇兩個雙親域為零而權值取最小的結點:s1和s2
ht[s1].parent=ht[s2].parent=i;
ht[i].lch=s1;
ht[i].rch=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
};
}
⑻ python二叉樹求深度的一個問題，有代碼，求解釋
這是遞歸演算法
我們可以先假設函數功能已經實現，left從左子樹拿到一個深度值，right從右子樹拿到一個深度值，最後，本層的深度為left和right的最大值加1，也就是最大深度值再算上自己這一層。
也可以從停止條件開始思考，什麼時候不再遞歸呢？當root為空時，並返回深度值為0。調用這一層的函數得到返回值就是0，我們假設這是左子樹left得到的值，同時假設右子樹也為空，所以right也為0。那麼返回給上一層的值就是left和right最大值加1，就是1，表示這個節點深度為1。同理，可以得到整棵樹深度。
⑼ python 二叉樹實現四則運算
#!/usr/bin/python#* encoding=utf-8s = "20-5*(0+1)*5^(6-2^2)" c = 0top = [0,s[c],0]op = [["0","1","2","3","4","5","6","7","8","9"],["+","-"],["*","/"],["^"]] def getLev(ch): for c1 in range(0, len(op)): for c2 in range(0, len(op[c1])): if (op[c1][c2]==ch): return c1 elif (len(ch)>1): match = 0 for c3 in range(0, len(ch)): if (getLev(ch[c3])>=0): match+=1 if (match==len(ch)):return c1 return -1
⑽ python 如何將一段字元串用二叉樹的後序遍歷列印出來
# -*- coding:utf-8 -*-def fromFMtoL( mid ): global las #全局後序遍歷 global fir #先序遍歷 root = fir[0] #取出當前樹根 fir = fir[1:] #取出樹根後 先序遍歷把根拿出來 下面一個元素做樹根 root_po = mid.find( root ) #在中序遍歷當中樹根的位置 left = mid[0:root_po] #左子樹 right = mid[root_po+1:len(mid)] #右子樹 ''' 後序遍歷： 左 右 根 先左子樹 再右子樹 最後跟 ''' #有左子樹的時候 if len(left) > 0: fromFMtoL( left ) #有右子樹的時候 if len(right) > 0: fromFMtoL( right ) #樹根寫進結果 las += rootif __name__ == "__main__" : # fir = input("請輸入先序遍歷：") #前序遍歷的結果 # mid = input("請輸入中序遍歷：") #中序遍歷的結果 fir = "DBACEGF" mid = "ABCDEFG" # fir = "ABC" # mid = "BAC" las = "" fromFMtoL( mid ) print(las)