实验三二叉树

1、南昌大学实验报告 -（3）二叉树学生姓名： 罗明 学 号： 6100411055 专业班级： 计算机111班 实验类型： 验证 综合 设计 创新 实验日期：2013/5/2 实验成绩： 一、实验目的1熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题2掌握二叉树的基本的存储结构，以及各种操作的算法实现（如建立、遍历）以及应用3注意递归算法和非递归算法的设计以及赫夫曼树的应用二、实验内容1按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树2按先序、中序、后序顺序分别遍历这棵二叉树。注意，用递归的方法实现先序遍历，用非递归的方法实现中序和后序遍历3编写一个求二叉树叶子结点

2、数和二叉树的深度的算法。4实现二叉树的线索化5构建赫夫曼树，实现赫夫曼编码三、实验要求实现二叉树的初始化，并设计出基本操作的算法四、实验环境PC微机 Windows 操作系统 Visual C+6.0程序集成环境五、程序代码1二叉树的存储结构及遍历二叉树/-函数结果状态代码-/common.h#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;/-二叉树的二叉链表存储结构-/BiTree.

3、htypedef struct BiTNodeTElemType data;struct BiTNode *lchild; /左孩子指针struct BiTNode *rchild; /右孩子指针BiTNode,*BiTree;/-栈的链式存储结构-/LinkStack.h#define STACK_INIT_SIZE 20 /存储空间初始分配量#define STACKINCREMENT 2 /存储空间分配增量typedef struct nodeSElemType data;struct node *next;LinkStack; /链式栈的结构体定义/-基本操作的函数原型说明-/关于树的

4、int PreCreateBiTree(BiTree &T);Status VISIT(TElemType e);Status PreOrderTraverse(BiTree T,Status (*visit)(TElemType e);Status InOrderTraverse(BiTree T,Status (*visit)(TElemType e);void MidVisit(BiTree &T);void PostOrderTraverse(BiTree T,Status (*visit)(TElemType e);void PostOrder(BiTNode *T,

5、Status (*visit)(TElemType e);Status CountLeaf(BiTree T);int deep(BiTree T);/关于栈的Status InitStack(LinkStack *S);Status Push(LinkStack *S,SElemType x);Status Pop(LinkStack *S,SElemType &e);Status StackEmpty(LinkStack *S);Status GetTop(LinkStack *S,SElemType &e);/-基本操作的实现-/bitree.cpp#include<

6、;stdio.h>#include<malloc.h>#include<stdlib.h>#include"common.h"typedef char TElemType;#include"BiTree.h"typedef BiTree SElemType;#include"LinkStack.h"int n=0;/构造而二叉链表表示的二叉树/插入元素，按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树int PreCreateBiTree(BiTree &T) /递归先序建立 char

7、 e;scanf("%c",&e);if(e=' ')T=NULL;return 1;T=(BiTree)malloc(sizeof(BiTNode);if(!T) exit(OVERFLOW);T->data=e; /生成根结点PreCreateBiTree(T->lchild); /构造左子树 PreCreateBiTree(T->rchild); /构造右子树return OK;/访问树中元素Status VISIT(TElemType e)printf("%c ",e);return OK;/采用递归先序

8、遍历二叉树Status PreOrderTraverse(BiTree T,Status (*visit)(TElemType e)if(T)if(*visit)(T->data)if(PreOrderTraverse(T->lchild,VISIT)if(PreOrderTraverse(T->rchild,VISIT)return OK;return ERROR;elsereturn OK;/采用中序非递归遍历二叉树Status InOrderTraverse(BiTree T,Status (*visit)(TElemType e)LinkStack *S;BiTree

9、 p;InitStack(&S);Push(S,T); /根指针进栈while(!StackEmpty(S)while(GetTop(S,p)&&p)Push(S,p->lchild); /向左走到尽头Pop(S,p);if(!StackEmpty(S)/访问节点，向右一步Pop(S,p);if(!VISIT(p->data)return ERROR;Push(S,p->rchild);return OK;/网上查的void MidVisit(BiTree &T) /递归中序遍历if(!T)return;MidVisit(T->lchil

10、d); printf("%c ",T->data); MidVisit(T->rchild);/采用递归后序遍历二叉树(网上查的)void PostOrderTraverse(BiTree T,Status (*visit)(TElemType e)if(T)PostOrderTraverse(T->lchild,VISIT);PostOrderTraverse(T->rchild,VISIT);VISIT(T->data);/采用非递归后序遍历二叉树(网上查的)void PostOrder(BiTNode *T,Status (*visit)

11、(TElemType e)BiTNode *p=T;BiTNode *stack30;int num=0;BiTNode *have_visited=NULL;while(NULL!=p|num>0)while(NULL!=p)stacknum+=p;p=p->lchild;p=stacknum-1;if(NULL=p->rchild|have_visited=p->rchild)VISIT(p->data);num-;have_visited=p;p=NULL;elsep=p->rchild;/统计二叉树的叶子数Status CountLeaf(BiTre

12、e T)if(T)if(!(T->lchild)&&!(T->rchild)n+;CountLeaf(T->lchild);CountLeaf(T->rchild);return n;/统计二叉树的深度int deep(BiTree T)int ld,rd;if(T)ld=deep(T->lchild);rd=deep(T->rchild);return (ld+1)>(rd+1)?(ld+1):(rd+1);elsereturn ERROR;/-基本操作的实现-/linkstack.cpp#include<stdio.h>

13、#include<stdlib.h>#include<malloc.h>#include"common.h"typedef char TElemType;#include"BiTree.h"typedef BiTree SElemType;#include"LinkStack.h"/初始化一个带头结点的空栈Status InitStack(LinkStack *S)*S=(LinkStack *)malloc(sizeof(LinkStack);if(*S=NULL)exit(OVERFLOW);(*S)-&g

14、t;next=NULL;return OK;/入栈操作，将x的数据元素插入栈s中，使x成为新的栈顶元素Status Push(LinkStack *S,SElemType x)LinkStack *p,*q;q=S;p=(LinkStack *)malloc(sizeof(LinkStack);if(!p)exit(OVERFLOW);p->data=x;p->next=NULL;while(q->next)q=q->next;q->next=p;return OK; /出栈操作,先将栈s的栈顶结点的值送到e所指向的内存单元，然后删除栈顶结点Status Pop(

15、LinkStack *S,SElemType &e)LinkStack *p,*q;p=S;if(S->next=NULL)return ERROR;while(p->next)q=p;p=p->next;q->next=NULL;e=p->data;free(p);return OK;/判断栈是否为空Status StackEmpty(LinkStack *S)if(S->next=NULL)return TRUE;else return FALSE;/取栈顶元素Status GetTop(LinkStack *S,SElemType &e

16、)LinkStack *p,*q;p=S;if(S->next=NULL)return ERROR;while(p->next)q=p;p=p->next;e=p->data;return OK;/-主程序-/main.cpp#include<stdio.h>#include<malloc.h>#include"common.h"typedef char TElemType;#include"BiTree.h"typedef BiTree SElemType;#include"LinkStack.

17、h"void main()BiTree T;int Height,Num;/树的深度和叶子个数printf("按先序次序输入二叉树中结点的值，空格表示空树。请输入：n");PreCreateBiTree(T);printf("先序遍历得到的序列为：");PreOrderTraverse(T,VISIT);printf("n");printf("中序遍历得到的序列为：");/MidVisit(T); /递归中序遍历/printf("n");InOrderTraverse(T,VISIT)

18、;printf("n"); printf("后序遍历得到的序列为：");PostOrder(T,VISIT);printf("n");/PostOrderTraverse(T,VISIT); /递归后序遍历/printf("n");Num=CountLeaf(T);Height=deep(T);printf("此树的深度和叶子个数分别为：%d %dn",Height,Num);2线索二叉树/-函数结果状态代码-/common.h#define TRUE 1#define FALSE 0#defi

19、ne OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;/-二叉树的二叉线索存储表示-/BiThrTree.htypedef enumLink,Thread PointerTag; /Link0,表示指针;Thread1,表示线索typedef struct BiThrNodeTElemType data;struct BiThrNode *lchild,*rchild; /左右孩子指针PointerTag LTag,RTag; /左右标志BiThrNode, *BiThrTree;/-基

20、本操作的函数原型说明-BiThrTree PreCreateBiTree();void InThreading(BiThrTree p);BiThrTree InOrderThreading(BiThrTree &t, BiThrTree T);BiThrTree InOrderThrTree(BiThrTree T);void InThrTravel(BiThrTree Thre);/-基本操作的实现-/bithrtree.cpp#include<stdio.h>#include<malloc.h>#include<stdlib.h>#includ

21、e"common.h"typedef char TElemType;#include"BiThrTree.h"BiThrTree pre;/构造而二叉链表表示的二叉树/插入元素，按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树BiThrTree PreCreateBiTree( ) /递归先序建立 BiThrTree T; char e;scanf("%c",&e);if(e=' ')T=NULL;elseT=(BiThrTree)malloc(sizeof(BiThrNode);T->dat

22、a=e; T->LTag=Link; /*初始化时指针标志均为Link*/ T->RTag=Link; T->lchild=PreCreateBiTree( );T->rchild=PreCreateBiTree( ); return T; void InThreading(BiThrTree p)if(p)InThreading(p->lchild); /左子树线索化if(!p->lchild)/前驱线索p->LTag=Thread;p->lchild=pre; if(!pre->rchild)/后继线索pre->RTag=Thre

23、ad;pre->rchild=p;pre=p; /保持pre指向p的前驱InThreading(p->rchild); /右子树线索化/中序遍历二叉树T，并将其中序线索化，Thrt指向头结点 BiThrTree InOrderThreading(BiThrTree &t, BiThrTree T)t=(BiThrTree)malloc(sizeof(BiThrNode);if(!t)exit(OVERFLOW);t->LTag=Link;t->RTag=Thread; /建头结点t->rchild=t; /右指针回指if(!T)t->lchild=t

24、;elset->lchild=T;pre=t;InThreading(T); /中序遍历进行中序线索化pre->rchild=t; pre->RTag=Thread; /最后一个结点线索化t->rchild=pre;return t;/网上找的BiThrTree InOrderThrTree(BiThrTree T) /*中序线索化二叉树*/ BiThrTree Thre; /*Thre为头结点的指针*/ Thre=(BiThrTree)malloc(sizeof(BiThrNode);Thre->lchild=T; Thre->rchild=Thre; p

25、re=Thre; InThreading(T); pre->RTag=Thread; pre->rchild=Thre;Thre->rchild=pre; return Thre; /网上找的/*中序遍历二叉树*/void InThrTravel(BiThrTree Thre) BiThrTree p; p=Thre->lchild;while(p!=Thre) /*指针回指向头结点时结束*/ while(p->LTag=Link) p=p->lchild; printf("%c ",p->data); while(p->RT

26、ag=Thread&&p->rchild!=Thre)p=p->rchild; printf("%c ",p->data); p=p->rchild; /-主程序-/main.cpp#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include"common.h"typedef char TElemType;#include"BiThrTree.h"void main()BiThrTree T,Thr

27、e,t; printf("先序初始化二叉树:n"); T=PreCreateBiTree();Thre=InOrderThreading(t, T);/Thre=InOrderThrTree(T); /网上找的 printf("中序遍历线索化后的二叉树:n"); InThrTravel(Thre); printf("n");3赫夫曼树和赫夫曼编码/-函数结果状态代码-/common.h#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -

28、1#define OVERFLOW -2typedef int Status;/-赫夫曼树和赫夫曼编码的存储表示-/HuffmanTree.htypedef structunsigned int weight; /权unsigned int parent, lchild, rchild;HTNode, *HuffmanTree; /动态分配数组存储赫夫曼树typedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表/-基本操作的函数原型说明-int MIN(HuffmanTree t,int i);void Select(HuffmanTree t,int n,int

29、&s1,int &s2);void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int*w,int n);/-基本操作的实现-/huffmantree.cpp#include <malloc.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include "common.h"#include "HuffmanTree.h"/返回i个结点中权值最小的树的根结点序

30、号int MIN(HuffmanTree t,int i)int j,flag;unsigned int k=65535; /* 取k为无符号整型最大值*/for(j=1;j<=i;j+)if(tj.weight<k&&tj.parent=0) /* tj是树的根结点 */k=tj.weight;flag=j;tflag.parent=1; /* 给选中的根结点的双亲赋1，避免第2次查找该结点 */return flag; /在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个 void Select(HuffmanTree t,int n,int

31、&s1,int &s2) int j; s1=MIN(t,n); s2=MIN(t,n); if(s1>s2) j=s1; s1=s2; s2=j; /w存放n个字符权值，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HCvoid HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)int i, m, s1, s2;HuffmanTree p;if(n<1)return;m=2*n-1;HT = (HuffmanTree) malloc (m+1) * sizeof (HTNode);

32、/0号单元未用for(p=HT+1,i=1;i<=n;+i,+p,+w)(*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;/后n-1的元素先清空for(;i<=m;+i,+p)(*p).weight=0;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;for (i=n+1;i<=m;+i) /建赫夫曼树/在HT1,.,i-1中选择parent为0，且weight值最小的两个结点，其序号为s1和s2Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/从叶子到根逆向求每个字符的赫夫曼编码char *cd; /分配求编码的工作空间int start;unsigned c,f;HC=(HuffmanCode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*siz