《数据结构》实验项目卡-6-二叉树的基本操作

实验6：二叉树的基本操作

一、实验目的

1.掌握二叉树的非线性和递归性特点

2.理解二叉树的存储结构

3.掌握二叉树遍历操作

二、实验内容

1.使用二叉链表，创建一个如图（a）的二叉树。可以用先序、中序和后序方式遍历二叉树并将

结点输出，.统计出一个二叉树叶子节点及树的深度。

#include<iostream>

#include<cstdio>

usingnamespacestd;

typedefcharDatatype;

intent;

structTNode

（

Datatypedata;

TNode*rchild;

TNode*Ichild;

voidCreatTree(TNode*&root)

(

charndata;

cin»ndata;

if(ndata==^#^)root=NULL;

else

(

root=newTNode;root->data=ndata;

CreatTree(root->lchild);

CreatTree(root->rchild);

}

)

voidpreOrderTraver(TNode*&root)//先

(

if(root!=NULL)

cout«root->data«nn;

preOrderTraver(root->lchild);

preOrderTraver(root->rchild);

)

)

voidInOrderTraver(TNode*&root)〃中

(

if(root!=NULL)

(

InOrderTraver(root->lchild);

cout«root->data«"

InOrderTraver(root->rchild);

)

)

voidposOrderTraver(TNode*&root)〃后

(

if(root!=NULL)

(

posOrderTraver(root->lchild);

posOrderTraver(root->rchild);

cout«root->data«"

)

)

intBTHeight(TNode*t)/〃二叉树的深度

(

intans=0;

if(t==NULL)return0;

elseif(t!=NULL)

ans+=max(ans,max(BTHeight(t->lchild),BTHeight(t->rchild))+1);

returnans;

)

intBTLeafNode(TNode*t)/〃二叉树的叶子节点数

(

if(t!=NULL)

(

if(t->lchild==NULL&&t->rchild==NULL)

(

printf("%c",t->data);

cnt++;

)

else

(

BTLeafNode(t->lchild);

BTLeafNode(t->rchild);

returnent;

}

intmain()

{

TNode*root=NULL;

coutvv”请输入该二叉树的先序遍历结果:\n"；

CreatTree(root);

coutvv”先序遍历结果"vvendl;

preOrderTraver(root);cout«endl;

cout<v”中序遍历结果:"<<endl;

InOrderTraver(root);cout«endl;

cout<<”后序遍历结果:n«endl;

posOrderTraver(root);cout«endl;

printf(”\n输出二叉树的深度：");

intsum=BTHeight(root);

cout«sum«endl;

printff输出二叉树的叶子结点：”)；

intans=BTLeafNode(root);

printf(”\n输出二叉树的叶子结点的个数：”)；

cout«ans«endl;

return0;

)

运行结果：

存在问题：无

2.对于给定的w={2,3,4,7,8,9}权值，试构造一棵哈夫曼树，并给出各个节点的huffman编码及huffman数

组的值。

#defineN50〃叶子结点数

#defineM2*N-1〃树中结点总数

typedefstruct

(

chardata[5];〃结点值

intweight;〃权重

intparent;〃双亲结点

intIchild;〃左孩子结点

intrchild;〃右孩子结点

}HTNode;

typedefstruct

charcd[N];〃存放哈夫曼码

intstart;

}HCode;

voidCreateHT(HTNodeht[],intn)

{

inti,k,Inode,mode;

doubleminl,min2;

for(i=0;i<2*n-l;i++)〃所有结点的相关域置初值-1

htfi].parent=ht[i].lchild=ht[i].rchild=-l;

for(i=n;i<2*n-l;i++)〃构造哈夫曼树

(

minl=min2=32767;//Inode和mode为最小权重的两个结点位置

lnode=rnode-1;

for(k=0;k<=i-l;k++)

if(ht[k].parent==-l)〃只在尚未构造二叉树的结点中查找

(

if(ht[k].weighKmin1)

(

min2=minl;rnode=lnode;

mini=ht[k].weight;lnode=k;

)

else

(

if(ht[k].weight<min2)

(

min2=ht[k].weight;

rnode=k;

ht[i].weight=ht[lnode].weight+ht[rnode].weight;

ht[il.lchild=lnode;ht[i].rchild=rnode;

ht[lnode].parent=i;ht[rnode].parent=i;

)

)

voidCreateHCode(HTNodeht[l,HCodehcd[],intn)

(

inti,f,c;

HCodehe;

for(i=0;i<n;i++)〃根据哈夫曼树求哈夫曼编码

(

f=ht[i],parent;

while(f!=-l)〃循序直到树根结点

(

if(htff].lchild==c)〃处理左孩子结点

else〃处理右孩子结点

c=f;f=ht[f].parent;

)

指向哈夫曼编码最开始字符

hcd[i]=hc;

)

)

voidDispHCode(HTNodeht[],HCodehcd[],intn)

(

inti,k;

intsum=0,m=0;

intj;

printf("输出哈夫曼数组的值及编码:\n");〃输出哈夫曼编码

for(i=0;i<n;i++)

(

j=0；

printf("%s:\t",ht[i].data);

for(k=hcdfi].start;k<=n;k++)

printf(0%cn,hcd[i].cd[k]);

j++;

)

m+=htfi].weight;

sum+=ht[i].weight*j;

printf("\nn);

)

printf("\n带权路径长度WPL=%d\n",sum);

)

intmain()

(

intn=6,i;〃11表示初始字符串的个数

char*str[]={"2","3","4","7","8","9"}；

intfnum[]={2,3,4,7,8,9};

HTNodeht[M];

HCodehcd[N];

for(i=0;i<n;i++)

(

strcpy(ht[i].data,str[i]);

ht[i].weight=fnum[i];

)

printf("\n");

CreateHT(ht,n);

CreateHCode(ht,hcd,n);

DispHCode(ht,hcd,n);

printf("\n");

)

测试数据：

运行结果：

存在问题：

二、本次实验问题分析及学习建议

备注：

1.每次实验完毕，各位学生可提交实验报告纸质（A