python樹結構

Ⅰ python 二叉樹的創建和遍歷、重建

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

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

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

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

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

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

Root =None

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

vals =list(strs)

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

print(Roots)

inorderSearch = inOrderTraverse2(Roots)

print(inorderSearch)

Ⅱ 如何用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編寫歐式二叉樹的問題

所以我就遇到了一下幾個問題：
1、該怎麼把二叉樹各個節點連起來？
2、怎麼定義內部數據成員？
3、如何實例化左右孩子？

在網上也沒找到比較簡單比較通用的Python二叉樹類實現，所以我花了點時間自己寫一個。
[python] view plain 在CODE上查看代碼片派生到我的代碼片
class Tree:
def __init__(self, val = '#', left = None, right = None):
self.val = val
self.left = left
self.right = right

#前序構建二叉樹
def FrontBuildTree(self):
temp = input('Please Input: ')
node = Tree(temp)
if(temp != '#'):
node.left = self.FrontBuildTree()
node.right = self.FrontBuildTree()
return node#因為沒有引用也沒有指針，所以就把新的節點給返回回去

#前序遍歷二叉樹
def VisitNode(self):
print(self.val)
if(self.val != '#'):
self.left.VisitNode()
self.right.VisitNode()

if __name__ == '__main__':
root = Tree()
root = root.FrontBuildTree()
root.VisitNode()

Ⅳ python中用字典寫出樹形數據結構並在控制台中列印樹形數據結構

#!/usr/bin/python
importos,sys,string
classXXTree:
	def__init__(self):
		pass
	
	defprintHelp(self,cmd):
		print'Pleaseusethefollowingcmd:'
		print''+cmd+'dir'
		print'e.g.'
		print''+cmd+'/home/fkong/tmp'

	defgetTree(self,dir,op):
		list=self.getList(dir,0,op)
		treelist=[]
		
		foriinrange(0,len(list)):
			fullpath=list[i]
			parpath=os.path.dirname(list[i])
			filename=os.path.basename(list[i])
			if(fullpath==dir):
				treelist.append(fullpath)
				continue
				
			path=fullpath.replace(dir,"")
			names=path.split("/")
			name="`---"+names[len(names)-1]
			forjinrange(1,len(names)-1):
				name=""+name
			treelist.append(name)
			
			pos=name.index("`")
			j=i-1
			whilej>0:
				name=treelist[j]
				if(name[pos]=='`'orname[pos]==''):
					name=name[0:pos]+"|"+name[pos+1:len(name)]
					treelist[j]=name
				else:
					break
				j=j-1
		
		foriinrange(0,len(treelist)):
			printtreelist[i]
		
	defgetList(self,dir,layer,op):
		list=[]
		iflayer==0:list.append(dir)
		files=os.listdir(dir)
		forfileinfiles:
			file=os.path.join(dir,file)
			ifos.path.isdir(file):
				list.append(file)
				list+=self.getList(file,layer+1,op)
			elifop=='-d':
				pass
			else:
				list.append(file)
		returnlist

iflen(sys.argv)<2:
	t=XXTree()
	t.printHelp(sys.argv[0])
else:
	t=XXTree()

	dir=None
	iflen(sys.argv)==2:
		dir=sys.argv[1]

	op=None
	iflen(sys.argv)==3:
		op=sys.argv[1]
		dir=sys.argv[2]

	t.getTree(dir,op)

Ⅳ 決策樹之ID3演算法及其Python實現

決策樹之ID3演算法及其Python實現

1. 決策樹背景知識
??決策樹是數據挖掘中最重要且最常用的方法之一，主要應用於數據挖掘中的分類和預測。決策樹是知識的一種呈現方式，決策樹中從頂點到每個結點的路徑都是一條分類規則。決策樹演算法最先基於資訊理論發展起來，經過幾十年發展，目前常用的演算法有：ID3、C4.5、CART演算法等。
2. 決策樹一般構建過程
??構建決策樹是一個自頂向下的過程。樹的生長過程是一個不斷把數據進行切分細分的過程，每一次切分都會產生一個數據子集對應的節點。從包含所有數據的根節點開始，根據選取分裂屬性的屬性值把訓練集劃分成不同的數據子集，生成由每個訓練數據子集對應新的非葉子節點。對生成的非葉子節點再重復以上過程，直到滿足特定的終止條件，停止對數據子集劃分，生成數據子集對應的葉子節點，即所需類別。測試集在決策樹構建完成後檢驗其性能。如果性能不達標，我們需要對決策樹演算法進行改善，直到達到預期的性能指標。
??註：分裂屬性的選取是決策樹生產過程中的關鍵，它決定了生成的決策樹的性能、結構。分裂屬性選擇的評判標準是決策樹演算法之間的根本區別。
3. ID3演算法分裂屬性的選擇——信息增益
??屬性的選擇是決策樹演算法中的核心。是對決策樹的結構、性能起到決定性的作用。ID3演算法基於信息增益的分裂屬性選擇。基於信息增益的屬性選擇是指以信息熵的下降速度作為選擇屬性的方法。它以的資訊理論為基礎，選擇具有最高信息增益的屬性作為當前節點的分裂屬性。選擇該屬性作為分裂屬性後，使得分裂後的樣本的信息量最大，不確定性最小，即熵最小。
??信息增益的定義為變化前後熵的差值，而熵的定義為信息的期望值，因此在了解熵和信息增益之前，我們需要了解信息的定義。
??信息：分類標簽xi 在樣本集 S 中出現的頻率記為 p(xi)，則 xi 的信息定義為：?log2p(xi) 。
??分裂之前樣本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 為分類標簽的個數。
??通過屬性A分裂之後樣本集的熵：EA(S)=?∑mj=1|Sj||S|E(Sj)，其中 m 代表原始樣本集通過屬性A的屬性值劃分為 m 個子樣本集，|Sj| 表示第j個子樣本集中樣本數量，|S| 表示分裂之前數據集中樣本總數量。
??通過屬性A分裂之後樣本集的信息增益：InfoGain(S,A)=E(S)?EA(S)
??註：分裂屬性的選擇標准為：分裂前後信息增益越大越好，即分裂後的熵越小越好。
4. ID3演算法
??ID3演算法是一種基於信息增益屬性選擇的決策樹學習方法。核心思想是：通過計算屬性的信息增益來選擇決策樹各級節點上的分裂屬性，使得在每一個非葉子節點進行測試時，獲得關於被測試樣本最大的類別信息。基本方法是：計算所有的屬性，選擇信息增益最大的屬性分裂產生決策樹節點，基於該屬性的不同屬性值建立各分支，再對各分支的子集遞歸調用該方法建立子節點的分支，直到所有子集僅包括同一類別或沒有可分裂的屬性為止。由此得到一棵決策樹，可用來對新樣本數據進行分類。
ID3演算法流程：
(1) 創建一個初始節點。如果該節點中的樣本都在同一類別，則演算法終止，把該節點標記為葉節點，並用該類別標記。
(2) 否則，依據演算法選取信息增益最大的屬性，該屬性作為該節點的分裂屬性。
(3) 對該分裂屬性中的每一個值，延伸相應的一個分支，並依據屬性值劃分樣本。
(4) 使用同樣的過程，自頂向下的遞歸，直到滿足下面三個條件中的一個時就停止遞歸。
??A、待分裂節點的所有樣本同屬於一類。
??B、訓練樣本集中所有樣本均完成分類。
??C、所有屬性均被作為分裂屬性執行一次。若此時，葉子結點中仍有屬於不同類別的樣本時，選取葉子結點中包含樣本最多的類別，作為該葉子結點的分類。
ID3演算法優缺點分析
優點：構建決策樹的速度比較快，演算法實現簡單，生成的規則容易理解。
缺點：在屬性選擇時，傾向於選擇那些擁有多個屬性值的屬性作為分裂屬性，而這些屬性不一定是最佳分裂屬性；不能處理屬性值連續的屬性；無修剪過程，無法對決策樹進行優化，生成的決策樹可能存在過度擬合的情況。