我们做一个放二叉树的结构体数组，数组里面读入的时候，我们只读入值，然后将二叉树的左右子树置为空。
然后构造最优二叉树的过程就是，每次从二叉树数组中选取权值最小的二叉树，然后将这两个二叉树作为左子树和右子树，构造一个新的二叉树，双亲结点的权值就是它俩的权值之和。
我们递归执行这一过程，当二叉树数组里面只剩下一颗二叉树的时候，递归结束，此时最优二叉树已经构建完毕，这时的父节点就是根节点。
我们因为是在函数里面建树，所以我们直接给每个子树重新分配一个空间，最重要的就是初始化，不初始化的话后果很严重，结果是乱码。
我们重载树结构的运算符，使它可以快速排序，因为每次排序的花销都是n logn的，所以即使每次都做排序，我们也勉强可以接受。
这样每次在数组前面的就是最小权值的树了，我们分配，更改值，连接树，新树装入数组，最后删除其中的一棵树，就是直接将它的value设为无穷，这样排序的时候，就被排到后面去了。
我们每次排序的长度是我们树数组的长度，这样可以最大限度地节约开销。
我们遍历数的时候，因为叶子节点上才是我们输入的值，所以我们遍历的时候只输出叶子节点的值就可以了。
#include#include #define INF 0x3f3f3f3fusing namespace std;typedef int Elemtype;struct BiTree { int value; BiTree *Lchild; BiTree *Rchild; bool operator < (const BiTree &b)const { return value < b.value; } BiTree & operator = (BiTree &b) { value = b.value; Lchild = b.Lchild; Rchild = b.Rchild; return *this; }};BiTree TreeNode[1000];BiTree *Root;int T,total;void CreateHuffTree(int i){ if (i==1) { Root = &TreeNode[0]; return; } //重新分配 BiTree *root = new BiTree; BiTree *lchild = new BiTree; BiTree *rchild = new BiTree; //get value *lchild = TreeNode[0]; *rchild = TreeNode[1]; //correct value root->value=0; root->value += lchild->value; root->value += rchild->value; //point root->Lchild = lchild; root->Rchild = rchild; //load TreeNode[0] = *root; //delete TreeNode[1].value = INF; sort(TreeNode, TreeNode + i); CreateHuffTree(i-1);}void PreOrderTraverse(BiTree *T,int level){ if (T==NULL) { return ; } if (T->Lchild==NULL&&T->Rchild==NULL) { cout< value<<" "; total+=level*T->value; } PreOrderTraverse(T->Lchild,level+1); PreOrderTraverse(T->Rchild,level+1);}int main(){ Elemtype num; cin >> T; for (int i = 0; i < T;i++) { scanf("%d", &num); TreeNode[i].value = num; TreeNode[i].Lchild = TreeNode[i].Rchild = NULL; } sort(TreeNode, TreeNode + T); CreateHuffTree(T); total=0; PreOrderTraverse(Root,0); cout< < <