Python 데이터 구조의 하프 만 트 리 정의 와 사용 방법 예시

본 고 는 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 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.

좋은 웹페이지 즐겨찾기