实验三++二叉树.doc

南昌大学实验报告---(3)二叉树学生姓名:罗明 学  号:6100411055   专业班级: 计算机111班实验类型:■验证□综合□设计□创新 实验日期:2013/5/2实验成绩:      一、,,以及各种操作的算法实现(如建立、遍历)、,、中序、后序顺序分别遍历这棵二叉树。注意,用递归的方法实现先序遍历,。,实现赫夫曼编码三、实验要求实现二叉树的初始化,并设计出基本操作的算法四、实验环境PC微机   Windows 操作系统 VisualC++、//-------函数结果状态代码----------//#RUE    1#defineFALSE    0#defineOK     1#defineERROR    0#defineINFEASIBLE -1#defineOVERFLOW  -2typedefintStatus;//-------二叉树的二叉链表存储结构---------//{TElemTypedata;structBiTNode*lchild; //左孩子指针structBiTNode*rchild; //右孩子指针}BiTNode,*BiTree;//-------栈的链式存储结构---------//#defineSTACK_INIT_SIZE20 //存储空间初始分配量#defineSTACKINCREMENT2 //存储空间分配增量typedefstructnode{SElemTypedata;structnode*next;}LinkStack;      //链式栈的结构体定义//-------基本操作的函数原型说明--------//关于树的intPreCreateBiTree(BiTree&T);StatusVISIT(TElemTypee);StatusPreOrderTraverse(BiTreeT,Status(*visit)(TElemTypee));StatusInOrderTraverse(BiTreeT,Status(*visit)(TElemTypee));voidMidVisit(BiTree&T);voidPostOrderTraverse(BiTreeT,Status(*visit)(TElemTypee));voidPostOrder(BiTNode*T,Status(*visit)(TElemTypee));StatusCountLeaf(BiTreeT);intdeep(BiTreeT);//关于栈的StatusInitStack(LinkStack**S);StatusPush(LinkStack*S,SElemTypex);StatusPop(LinkStack*S,SElemType&e);StatusStackEmpty(LinkStack*S);StatusGetTop(LinkStack*S,SElemType&e);//--------基本操作的实现-----------//#include<>#include<>#include<>#"typedefcharTElemType;#include""typedefBiTreeSElemType;#include""intn=0;//构造而二叉链表表示的二叉树//插入元素,按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树intPreCreateBiTree(BiTree&T)//递归先序建立{chare;scanf("%c",&e);if(e==''){T=NULL;return1;}T=(BiTree)malloc(sizeof(BiTNode));if(!T)exit(OVERFLOW);T->data=e; //生成根结点PreCreateBiTree(T->lchild); //构造左子树 PreCreateBiTree(T->rchild); //构造右子树returnOK;}//访问树中元素StatusVISIT(TElemTypee){printf(