#!/usr/bin/python

 #coding=utf-8

 #哈夫曼树创建

 class Node():

     def __init__(self,value,left=None,right=None):

         self.value=value

         self.left=left

         self.right=right

 class Halfman():

     def init(self,k):

         k.sort()

        # key=Node(k[0])

         self.root=Node(k[0])

         if len(k)==len(set(k)):  #无重复项判定

             for i in range(1,len(k)):

                 node=Node(k[i])

                 if i==1:

                     max=k[i]*(len(k)-i)+self.root.value*(len(k)-1)

                 else:

                     max=k[i]*(len(k)-i)+self.root.value

                 root=Node(max,self.root,node)

                 self.root=root

             return self.root

     def pre(self,root):

         if root==None:return

         print root.value

         self.pre(root.left)

         self.pre(root.right)

 k=[2,8,5,6,4,7,9,1,3]

 tree=Halfman()

 a=tree.init([2,8,5,6,4,7,9,1,3])

 tree.pre(a)

 print '*'*40

 print a.value

 print a.left.value

 print a.right.value