存档

文章标签 ‘二叉树’

实验七  哈夫曼树的建立与应用

2008年11月7日 没有评论 420 views

Haffman.h

struct BTreeNode{
ElemType data;
BTreeNode* left;
BTreeNode* right;
};

BTreeNode* CreateHuffman(ElemType a[],int n)
{
BTreeNode **b,*q;
b=new BTreeNode*[n];
int i,j;
for(i=0;i b[i]=new BTreeNode;
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1;i int k1=-1,k2;
for(j=0;j if(b[j]!=NULL&&k1==-1){
k1=j;
continue;
}
if(b[j]!=NULL){
k2=j;
break;
}
}
for(j=k2;j if(b[j]!=NULL){
if(b[j]->datadata){
k2=k1;
k1=j;
}
else if(b[j]->data
data)
k2=j;
}
}
q=new BTreeNode;
q->data=b[k1]->data+b[k2]->data;
q->left=b[k1];
q->right=b[k2];
b[k1]=q;
b[k2]=NULL;
}
delete []b;
return q;
}

void PrintBTree(BTreeNode *BT)
{
if(BT!=NULL){
cout< data;
if(BT->left!=NULL||BT->right!=NULL){
cout< <'(';
PrintBTree(BT->left);
if(BT->right!=NULL)
cout< <',';
PrintBTree(BT->right);
cout< <')';
}
}
}

void HuffManCoding(BTreeNode *BT, int len)
{
static int a[10];
if(BT!=NULL){
if(BT->left==NULL&&BT->right==NULL){
cout< <"结点权值为"<data< <"的编码:";
for(int i=0;i cout< cout< }
else{
a[len]=0;
HuffManCoding(BT->left,len+1);
a[len]=1;
HuffManCoding(BT->right,len+1);
}
}
}

阅读全文…

分类: Sentiment 标签: , ,

二叉树的遍历问题

2008年6月12日 没有评论 495 views

    以前参加NOI时自己摸索出来的方法。
已知序列画树:

已知后序与中序排前序:

    由后序最后一位得知根节点,然后以此元素为基准将序列分为左、右子树,其中左子树的中序为上一层中序的左半部分,其后序为中序中的元素以上一层后序的顺序排列;右子树的中序为上一层中序的右半部分,其后序为中序中的元素以上一层后序的顺序排列。接着再根据此方法分别对每个子树中的中、后序继续分解,最后即可依次写出整棵二叉树的图,再通过描点法写出前序。

已知中序与前序排后序:

    由前序第一位得知根节点,然后以此元素为基准将序列分为左、右子树,其中左子树的中序为上一层中序的左半部分,其前序为中序中的元素以上一层前序的顺序排列;右子树的中序为上一层中序的右半部分,其前序为中序中的元素以上一层前序的顺序排列。接着再根据此方法分别对每个子树中的中、前序继续分解,最后即可依次写出整棵二叉树的图,再通过描点法写出后序。

分类: Code 标签: ,