.二叉树的类型定义及创建 七 includestdlib.hincludestdio.hincludemalloc.h//函数状态码定义define TRUE 1define FALSE 0define OK 1define ERROR 0define OVERFLOW -1define INFEASIBLE -2define NULL 0typedef int Status;//以下为二叉树的类型定义及创建、销毁、遍历、求树深、求结点数、叶结点数、复制、左右互换、查找、定位双亲、删除、凹式输出等操作实现//树中元素类型定义与二叉链表存储结构定义typedef char TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;Status CreateBiTreeBiTree T//先序创建二叉树各结点，注意输入时空指针不要丢TElemType e;scanfc,e;ife TNULL;elseTBiTreemallocsizeofBiTNode;ifTexitOVERFLOW;T-datae;CreateBiTreeT-lchild;CreateBiTreeT-rchild;return OK; int TreeDepthBiTree T//递归法求树的深度//思路如果树为空树则深度为0，否则，先递归计算出左子树的深度，再计算出右子树的深度，最后，树的深度为两子树深度的最大值加1int d;int d1,d2;ifTNULLd0;elsed1TreeDepthT-lchild;d2TreeDepthT-rchild;ifd1d2dd11;else dd21;return d;int LeafCountBiTree T//递归法统计叶子结点的个数//思路如果树为空树则叶子结点的个数0，如果树为一个结点树则叶子结点的个数1，否则，先递归计算出左子树的叶子结点的个数，//再计算出右子树的叶子结点的个数，最后，树的叶子结点的个数为两子树叶子结点的个数和加int d;ifTNULLd0;else ifT-lchildNULLT-rchildNULLd1;elsedLeafCountT-lchildLeafCountT-rchild;return d;int NodeCountBiTree T//递归法统计所有结点的个数//思路如果树为空树则叶子结点的个数0，否则，先递归计算出左子树的叶子结点的个数，再计算出右子树的叶子结点的个数，//最后，树的叶子结点的个数为两子树叶子结点的个数和加1int n;ifTNULLn0;else n1NodeCountT-lchildNodeCountT-rchild;return n; Status PrintTElemTElemType eprintfc,e;return OK;Status PreOrderTraverseBiTree T,Status*visitTElemType//算法思路定义输出函数PrintElem，调用树的先序遍历函数,并将其传递给先序遍历函数中的参数visit即可,假设元素为字符型ifTif *visitT-data //s1if PreOrderTraverseT-lchild,*visit //s2if PreOrderTraverseT-rchild,*visit //s3return OK;return ERROR; //只要有一次访问失败则必执行此语句else return OK; //树空时返回OK Status InOrderTraverseBiTree T,Status*visitTElemType //算法思路定义输出函数PrintElem，调用树的中序遍历函数,并将其传递给中序遍历函数中的参数visit即可,假设元素为字符型ifTif InOrderTraverseT-lchild,*visit //s1if *visitT-data //s2if InOrderTraverseT-rchild,*visit //s3return OK;return ERROR; //只要有一次访问失败则必执行此语句else return OK; //树空时返回OK Status PostOrderTraverseBiTree T,Status*visitTElemTypeifTif InOrderTraverseT-lchild,*visit //s1if InOrderTraverseT-rchild,*visit //s2if *visitT-data //s3return OK;return ERROR; //只要有一次访问失败则必执行此语句else return OK; //树空时返回OKStatus ExchangeBiTreeBiTree T//二叉树用二叉链表存储,左右互换BiTNode *temp;ifTNULLreturn OK;elsetempT-lchild;T-lchildT-rchild;T-rchildtemp;ExchangeBiTreeT-lchild;ExchangeBiTreeT-rchild; return OK;void main BiTree BiT;CreateBiTreeBiT;printf二叉树BiT的先序输出序列为;PreOrderTraverseBiT,PrintTElem;printfn;printf二叉树BiT的中序输出序列为;InOrderTraverseBiT,PrintTElem;printfn;printf二叉树BiT的后序输出序列为;PostOrderTraverseBiT,PrintTElem;printfn;printf二叉树BiT树深dn,TreeDepthBiT;printf二叉树BiT结点总数dn,NodeCountBiT;printf递归求得二叉树BiT叶子结点数为dn,LeafCountBiT;ExchangeBiTreeBiT;printf二叉树BiT的先序输出序列为;PreOrderTraverseBiT,PrintTElem;printfn;printf二叉树BiT的中序输出序列为;InOrderTraverseBiT,PrintTElem;printfn;printf二叉树BiT的后序输出序列为;PostOrderTraverseBiT,PrintTElem;printfn;60设计算法统计孩子兄弟表示的树或森林的叶子结点数提示用递归,仿照求 森林的 深度。叶子意味着firstchild为空,注意第一棵树的叶子数如何求作业求哈夫曼编码，A-H出现频率 7，19，2，6，32，3，21，10includestdio.hincludestdlib.hincludestring.hdefine N 100// 赫夫曼树和赫夫曼编码的存储表示typedef structchar ch;unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char * *HuffmanCode;int minHuffmanTree HT,int i // 函数void select调用 int j,flag; int k65535; forj1;ji;j ifHTj.weightkHTj.parent0 kHTj.weight,flagj; HTflag.parent1; return flag; void SelectHuffmanTree HT,int i,int s1,int s2s1minHT,i ; s2minHT,i; //构造赫夫曼树 HT ,并求出 n 个字符的赫夫曼编码 HCvoid HuffmanCodingHuffmanTree HT,HuffmanCode HC,int *w,char *cha,int nchar c;int f,i,start,m,s1,s2;HTNode *p;ifn1 return ;m2*n-1;HTHuffmanTreemallocm1*sizeofHTNode;forpHT,p,i1;in;i,p p-chchai;p-weightwi;p-parent0;p-lchild0;p-rchild0;for;im;i,pp-weight0;p-parent0;p-lchild0;p-rchild0;forin1;im;i SelectHT,i-1,s1,s2;HTs1.parenti;HTs2.parenti;HTi.lchilds1; HTi.rchilds2;HTi.weightHTs1.weightHTs2.weight;HCHuffmanCodemallocn1*sizeofchar *;char *cdchar *mallocn*sizeofchar;cdn-10;fori1;in;istartn-1;forci,fHTi.parent;f0;cf,fHTf.parentifHTf.lchild c cd--start0;else cd--start1;HCichar *mallocn-start*sizeofchar;strcpyHCi,cdstart;printf字符为c,HTi.ch;printf的编码是sn ,HCi;freecd;// 赫夫曼译码函数void DeCodingHuffmanTree HT,HuffmanCode HC,int nchar fN;printf请输入一串字符串n;getchar;getsf;int i;int m,k0;whilefk0fori1;in;i mstrlenHCi;ifstrncmpHCi,fk,m0 kkm;printf输出s的字符是,HCi;printfcn,HTi.ch;void displayHTHuffmanTree HT,int n,int m int i;printf打印赫夫曼HC存储结构n;printf编号 字符 权重 双亲 左孩子 右孩子n;fori1;in;iprintfdtctdtdtdtdn,i,HTi.ch,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild;forin1;im;iprintfdt tdtdtdtdn,i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild;main HuffmanTree HT;HuffmanCode HC;int n,i;printf*********建赫夫曼树,编码和译码程序*************;printfn输入建赫夫曼树元素的个数;scanfd,n;int m2*n-1;char cha9;int w9;fori1;in;iprintf第d个元素字母和权重n,i;getchar;scanfc d,chai,wi;HuffmanCodingHT,HC,w,cha,n;displayHTHT,n,m;DeCodingHT,HC,n;return 0; ；.