Python 데이터 구조의 하프 만 트 리 정의 와 사용 방법 예시
HaffMan.py
#coding=utf-8
# haff ,
class TreeNode:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
self.parent=None
class HaffTree:
def __init__(self):
self.root=None
def set_root(self,rootNode):
self.root=rootNode
def run(self,lis):
i=0
lis=[[lis[j][0],lis[j][1],TreeNode(lis[j][1])]for j in range(len(lis))]
while len(lis)>1:
i+=1
lis=sorted(lis)
name='N'+str(i)
temp=TreeNode(name)
# lis[0][2]=lis[1][2]
# parent /
temp.left=lis[0][2]
temp.right=lis[1][2]
lis[0][2].parent=temp
lis[1][2].parent=temp
#print lis[0][0],lis[1][0],len(lis)
value=lis[0][0]+lis[1][0]
lis=lis[1:]
lis[0]=[value,name,temp]
#print temp.data,temp.left.data,temp.right.data
self.set_root(temp)
def code(self,lis):
self.codeList=[]
stack=[]
Node=self.root
stack.append(Node)
res=[]
while(stack):
node=stack.pop()
res.append(node)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
for li in lis:
codeL=[]
for re in res:
if re.data==li[1]:
parent=re
print '
',parent.data,
codeL.append(parent)
while parent.parent:
parent=parent.parent
print parent.data,
codeL.append(parent)
codeLL=[int(codeL[len(codeL)-2-i]==codeL[len(codeL)-1-i].right) for i in range(len(codeL)-1)]
self.codeList.append([li[1],codeLL])
return self.codeList
def list_all(self,method):
lis=[]
res=[]
if method=='before':
Node=self.root
lis.append(Node)
while(lis):
node=lis[-1]
lis=lis[:-1]
if node:
res.append(node.data)
if node.right:
lis.append(node.right)
if node.left:
lis.append(node.left)
elif method=='mid':
node = self.root
while lis or node:
while node:
lis.append(node)
node = node.left
if len(lis)>0:
node = lis[-1]
lis=lis[:-1]
if node:
res.append(node.data)
node= node.right
else:
pass
return res
HaffMantest.py
#coding=utf-8
from HaffMan import HaffTree
tree=HaffTree()
lis=[
[5,'A'],
[15,'B'],
[40,'C'],
[30,'D'],
[10,'E'],
]
print lis[2:]
print sorted(lis)
tree.run(lis)
print tree.list_all('before')
# HaffMan , , ( ), 。:
tree=HaffTree()
lis2=[
[27,'A'],
[8,'B'],
[15,'C'],
[15,'D'],
[30,'E'],
[5,'F'],
]
tree.run(lis2)
print tree.code(lis2)
실행 결과:Python 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Python의 None과 NULL의 차이점 상세 정보그래서 대상 = 속성 + 방법 (사실 방법도 하나의 속성, 데이터 속성과 구별되는 호출 가능한 속성 같은 속성과 방법을 가진 대상을 클래스, 즉 Classl로 분류할 수 있다.클래스는 하나의 청사진과 같아서 하나의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.