二叉树构造#include<iostream>usingnamespacestd;typedefstructNode{intkey;intv;intlc;intrc;}Node;//定义一个节点结构typedefstruct{NodeH[100];intn;}HH;//定义堆intk;voidinsert(HH&h,Nodev)//插入堆{inti,j;Nodetemp;h.H[h.n]=v;i=h.n;j=i/2;while(h.H[i].key<h.H[j].key&&j>0){temp=h.H[i];h.H[i]=h.H[j];h.H[j]=temp;i=j;j/=2;}h.n++;}Nodedeletemin(HH&h)//取最小堆顶端，并重新排序{Nodetemp;inti=1,min;Nodex=h.H[1];h.H[1]=h.H[h.n-1];h.n--;min=(h.H[2*i].key<h.H[2*i+1].key)?(2*i):(2*i+1);while(h.H[i].key>h.H[min].key&&(2*i+1)<h.n){temp=h.H[i];h.H[i]=h.H[min];h.H[min]=temp;i=min;min=(h.H[2*i].key<h.H[2*i+1].key)?(2*i):(2*i+1);}if(2*i<h.n&&(2*i+1)>=h.n&&h.H[i].key>h.H[2*i].key){temp=h.H[i];h.H[i]=h.H[2*i];h.H[2*i]=temp;}returnx;}voidhuffman(NodeTree[],HH&h,intn){//构造哈弗曼树TreeNodev1,v2;intj;for(inti=1;i<n;i++)//构造非叶子节点{v1=deletemin(h);v2=deletemin(h);Tree[n+i].key=v1.key+v2.key;Tree[n+i].v=k++;insert(h,Tree[n+i]);for(j=n+i-1;j>0;j--){if(Tree[j].v==v1.v)Tree[n+i].lc=j;elseif(Tree[j].v==v2.v)Tree[n+i].rc=j;}}/*for(j=1;j<2*n;j++)cout<<Tree[j].v<<""<<Tree[j].key<<""<<Tree[j].lc<<""<<Tree[j].rc<<endl;*/}voidshow_tree_v(NodeTree[],Noderoot){//先序序列输出哈弗曼树的节点符号if(root.key==0)return;cout<<root.v<<"";show_tree_v(Tree,Tree[root.lc]);show_tree_v(Tree,Tree[root.rc]);}voidshow_tree_key(NodeTree[],Noderoot){//先序序列输出哈弗曼树的节点权值if(root.key==0)return;cout<<root.key<<"";show_tree_key(Tree,Tree[root.lc]);show_tree_key(Tree,Tree[root.rc]);}intmain(){NodeTree[100];//用线性结构来存储哈夫曼树HHh;inti,n;memset(&h,0,sizeof(HH));//下面初始化堆和哈弗曼树h.n=1;Tree[0].key=0;cout<<"输入节点数:";cin>>n;k=n+1;cout<<"依次输入每个节点的权值："<<endl;for(i=1;i<=n;i++){Tree[i].v=i;//节点编号Tree[i].lc=0;Tree[i].rc=0;cin>>Tree[i].key;insert(h,Tree[i]);//节点逐个插入堆}huffman(Tree,h,n);cout<<"哈弗曼树节点符号的先序输出："<<endl;show_tree_v(Tree,Tree[2*n-1]);cout<<endl;cout<<"哈弗曼树