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、首先，将编制Python函数从左到右生成二叉树。
2、其次，根据生成的二叉树，从右向左计算期权价值。
3、最后，计算完成后，即可进行投资决策。

❹ 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算法优缺点分析
优点：构建决策树的速度比较快，算法实现简单，生成的规则容易理解。
缺点：在属性选择时，倾向于选择那些拥有多个属性值的属性作为分裂属性，而这些属性不一定是最佳分裂属性；不能处理属性值连续的属性；无修剪过程，无法对决策树进行优化，生成的决策树可能存在过度拟合的情况。

❻ 如何实现Python多叉树

classnode:

def__init__(self,data):
self._data=data
self._children=[]

defgetdata(self):
returnself._data

defgetchildren(self):
returnself._children

defadd(self,node):
##iffull
iflen(self._children)==4:
returnFalse
else:
self._children.append(node)

defgo(self,data):
forchildinself._children:
ifchild.getdata()==data:
returnchild
returnNone

classtree:

def__init__(self):
self._head=node('header')

deflinktohead(self,node):
self._head.add(node)

definsert(self,path,data):
cur=self._head
forstepinpath:
ifcur.go(step)==None:
returnFalse
else:
cur=cur.go(step)
cur.add(node(data))
returnTrue

defsearch(self,path):
cur=self._head
forstepinpath:
ifcur.go(step)==None:
returnNone
else:
cur=cur.go(step)
returncur


'''
definenode
'''
a=node('A')
b=node('B')
c=node('C')
d=node('D')
e=node('E')
f=node('F')
g=node('G')
h=node('H')
i=node('I')
j=node('J')
k=node('K')
l=node('L')
m=node('M')
n=node('N')
o=node('O')

'''
addingnodetobuildtrue
'''
a.add(b)
a.add(g)
a.add(h)
b.add(c)
b.add(e)
g.add(i)
g.add(j)
g.add(k)
g.add(l)
h.add(m)
h.add(n)
h.add(o)
c.add(d)
c.add(f)
i.add(node(29))
j.add(node(28))
k.add(node(27))
l.add(node(26))
m.add(node(25))
n.add(node(24))
o.add(node(23))
f.add(node(30))


tree=tree()
tree.linktohead(a)


#testcase
print'Node',tree.search("ABE").getdata()
print'Node',tree.search("ABC").getdata()
print'Node',tree.search("AHM").getdata()
tree.insert("ABCD",1)
foriind.getchildren():
print'valueafter',d.getdata(),'is',i.getdata()