中北大学 算法与数据结构实验报告(7)

2、顺序栈和链栈在实现时的区别

3、在增加了中括号大括号和方幂运算后的程序如何规定运算优先级表

30

实验三 链表的应用（三）哈夫曼树和哈夫曼编码

【实验内容】

1、实现二叉树的抽象数据类型 2、实现二叉树的遍历运算 3、实现二叉树的建立的运算 4、实现创建哈夫曼树的算法

5、给出测试字符表，并对表中字符进行哈夫曼编码 6、对字符表中的字符构成的信息源进行哈夫曼编码和译码 【实验方法与步骤】

1、先序遍历二叉树的递归算法

# include # include # include

# define OK 1 # define ERROR 0

typedef char TElemType;

typedef struct BiTNode //define structure BiTree { TElemType data;

struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;

int CreateBiTree(BiTree &T) //创建一个二叉树 { TElemType ch;

cout<<\请输入数据(/ for NULL node!) : \ cin>>ch;

if(ch=='/') T=NULL; else

{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { cout<<\//no alloction return (0); } //if end T->data=ch;

CreateBiTree(T->lchild); //构造左孩子 CreateBiTree(T->rchild); //构造右孩子 } //else end return (OK);

31

} //CreateBiTree() end

int PreOrderTraverse(BiTree T) {//先序遍历二叉树 if(T)

{ cout<data<<\ //visite T if (PreOrderTraverse(T->lchild)) //访问左孩子 if (PreOrderTraverse(T->rchild)) //访问右孩子 return (OK); return (ERROR); } //if end else

return (OK);

} //PreOrderTraverse() end

void main() //main() function { BiTree T;

cout<

cout<

cout<

2、中序遍历二叉树的递归算法

# include # include

32

# include

# define OK 1 # define ERROR 0

typedef char TElemType;

typedef struct BiTNode //define structureBiTree { TElemType data;

struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;

int CreateBiTree(BiTree &T) {//创建一个二叉树 TElemType ch;

cout<<\ cin>>ch; //输入数据 if(ch=='/') T=NULL; else

{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { cout<<\//no alloction return (ERROR); }

T->data=ch;

CreateBiTree(T->lchild); //创建左孩子 CreateBiTree(T->rchild); //创建右孩子 }

return (OK);

} //CreateBiTree() end

int InOrderTraverse(BiTree T) {//中序遍历二叉树 if(T)

{ if (InOrderTraverse(T->lchild)) //访问左孩子 { cout<data<<\ //访问根 if(InOrderTraverse(T->rchild)) //访问右孩子 return (OK); } return (ERROR); } //if end else

return (OK);

} //InOrderTraverse() end

void main() //main() function

33

{ BiTree T;

cout<

cout<

cout<

cout<

3、后序遍历二叉树的递归算法

# include # include # include

# define OK 1 # define ERROR 0

typedef char TElemType;

typedef struct BiTNode //定义二叉树结点 { TElemType data;

struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;

int CreateBiTree(BiTree &T) //构造二叉树 { TElemType ch;

cout<<\请输入数据 (/ for NULL node!) : \ cin>>ch;

if(ch=='/') T=NULL;

34