#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 '\n',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

#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)