《二叉树的类型定义及创建 七》由会员分享，可在线阅读，更多相关《二叉树的类型定义及创建 七（15页珍藏版）》请在金锄头文库上搜索。
1、二叉树的类型定义及创建 七 #include<stdlib.h>#include<stdio.h>#include<malloc.h>/函数状态码定义#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INFEASIBLE -2#define NULL 0typedef int Status;/以下为二叉树的类型定义及创建、销毁、遍历、求树深、求结点数、叶结点数、复制、左右互换、查找、定位双亲、删除、凹式输出等操作实现/树中元素类型定义与二叉链表
2、存储结构定义typedef char TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild, *rchild; BiTNode, *BiTree;Status CreateBiTree(BiTree &T)/先序创建二叉树各结点，注意输入时空指针不要丢TElemType e;scanf("%c",&e);if(e=' ')T=NULL;elseT=(BiTree)malloc(sizeof(BiTNode);if(!T)exit(OVERFLOW);T-&g
3、t;data=e;CreateBiTree(T->lchild);CreateBiTree(T->rchild);return OK; int TreeDepth(BiTree T)/递归法求树的深度/思路：如果树为空树则深度为0，否则，先递归计算出左子树的深度，再计算出右子树的深度，最后，树的深度为两子树深度的最大值加1int d;int d1,d2;if(T=NULL)d=0;elsed1=TreeDepth(T->lchild);d2=TreeDepth(T->rchild);if(d1>d2)d=d1+1;else d=d2+1;return d;int
4、LeafCount(BiTree T)/递归法统计叶子结点的个数/思路：如果树为空树则叶子结点的个数0，如果树为一个结点树则叶子结点的个数1，否则，先递归计算出左子树的叶子结点的个数，/再计算出右子树的叶子结点的个数，最后，树的叶子结点的个数为两子树叶子结点的个数和加int d;if(T=NULL)d=0;else if(T->lchild=NULL&&T->rchild=NULL)d=1;elsed=LeafCount(T->lchild)+LeafCount(T->rchild);return d;int NodeCount(BiTree T)/递归
5、法统计所有结点的个数/思路：如果树为空树则叶子结点的个数0，否则，先递归计算出左子树的叶子结点的个数，再计算出右子树的叶子结点的个数，/最后，树的叶子结点的个数为两子树叶子结点的个数和加1int n;if(T=NULL)n=0;else n=1+NodeCount(T->lchild)+NodeCount(T->rchild);return n; Status PrintTElem(TElemType e)printf("%c",e);return OK;Status PreOrderTraverse(BiTree T,Status(*visit)(TElemT
6、ype)/算法思路:定义输出函数PrintElem，调用树的先序遍历函数,并将其传递给先序遍历函数中的参数visit即可,假设元素为字符型if(T)if( (*visit)(T->data) ) /s1if( PreOrderTraverse(T->lchild,(*visit) /s2if( PreOrderTraverse(T->rchild,(*visit) /s3return OK;return ERROR; /只要有一次访问失败则必执行此语句else return OK; /树空时返回OK Status InOrderTraverse(BiTree T,Status
7、(*visit)(TElemType) /算法思路:定义输出函数PrintElem，调用树的中序遍历函数,并将其传递给中序遍历函数中的参数visit即可,假设元素为字符型if(T)if( InOrderTraverse(T->lchild,(*visit) /s1if( (*visit)(T->data) ) /s2if( InOrderTraverse(T->rchild,(*visit) /s3return OK;return ERROR; /只要有一次访问失败则必执行此语句else return OK; /树空时返回OK Status PostOrderTraverse
8、(BiTree T,Status(*visit)(TElemType)if(T)if( InOrderTraverse(T->lchild,(*visit) /s1if( InOrderTraverse(T->rchild,(*visit) /s2if( (*visit)(T->data) ) /s3return OK;return ERROR; /只要有一次访问失败则必执行此语句else return OK; /树空时返回OKStatus ExchangeBiTree(BiTree &T)/二叉树用二叉链表存储,左右互换BiTNode *temp;if(T=NULL
9、)return OK;elsetemp=T->lchild;T->lchild=T->rchild;T->rchild=temp;ExchangeBiTree(T->lchild);ExchangeBiTree(T->rchild); return OK;void main() BiTree BiT;CreateBiTree(BiT);printf("二叉树BiT的先序输出序列为：");PreOrderTraverse(BiT,PrintTElem);printf("n");printf("二叉树BiT的中序
10、输出序列为：");InOrderTraverse(BiT,PrintTElem);printf("n");printf("二叉树BiT的后序输出序列为：");PostOrderTraverse(BiT,PrintTElem);printf("n");printf("二叉树BiT树深：%dn",TreeDepth(BiT);printf("二叉树BiT结点总数：%dn", NodeCount(BiT);printf("递归求得二叉树BiT叶子结点数为：%dn",Lea
11、fCount(BiT);ExchangeBiTree(BiT);printf("二叉树BiT的先序输出序列为：");PreOrderTraverse(BiT,PrintTElem);printf("n");printf("二叉树BiT的中序输出序列为：");InOrderTraverse(BiT,PrintTElem);printf("n");printf("二叉树BiT的后序输出序列为：");PostOrderTraverse(BiT,PrintTElem);printf("n&qu
12、ot;);60设计算法统计孩子兄弟表示的树或森林的叶子结点数(提示：用递归,仿照求 森林的 深度。叶子意味着firstchild为空,注意第一棵树的叶子数如何求)作业:求哈夫曼编码，A-H出现频率 (%) 7， 19，2，6，32，3，21，10#include<stdio.h>#include<stdlib.h>#include<string.h>#define N 100/ 赫夫曼树和赫夫曼编码的存储表示typedef structchar ch;unsigned int weight;unsigned int parent,lchild,rchild;
13、HTNode,*HuffmanTree;typedef char * *HuffmanCode;int min(HuffmanTree &HT,int i) / 函数void select()调用 int j,flag; int k=65535; for(j=1;j<=i;j+) if(HTj.weight<k&&HTj.parent=0) k=HTj.weight,flag=j; HTflag.parent=1; return flag; void Select(HuffmanTree &HT,int i,int &s1,int &s2)s1=min(HT,i) ; s2=min(HT,i); /构造赫夫曼树 HT , 并求出 n 个字符的赫夫曼编码 HCvoid HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w, char *cha,int n)char c;int f,i,start,m,s1,s2;HTNode *p;if(n<=1) return ;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT,+p,i=1;i<=n;+i,+p
