二叉樹的類型定義及創(chuàng)建 七

1、.二叉樹的類型定義及創(chuàng)建 七 #include<stdlib.h>#include<stdio.h>#include<malloc.h>/函數(shù)狀態(tài)碼定義#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INFEASIBLE -2#define NULL 0typedef int Status;/以下為二叉樹的類型定義及創(chuàng)建、銷毀、遍歷、求樹深、求結(jié)點(diǎn)數(shù)、葉結(jié)點(diǎn)數(shù)、復(fù)制、左右互換、查找、定位雙親、刪除、凹式輸出等操作實(shí)現(xiàn)/樹中元素類型定義與二叉鏈

2、表存儲(chǔ)結(jié)構(gòu)定義typedef char TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild, *rchild; BiTNode, *BiTree;Status CreateBiTree(BiTree &T)/先序創(chuàng)建二叉樹各結(jié)點(diǎn)，注意輸入時(shí)空指針不要丟TElemType e;scanf("%c",&e);if(e= )T=NULL;elseT=(BiTree)malloc(sizeof(BiTNode);if(!T)exit(OVERFLOW);T->data=e;

3、CreateBiTree(T->lchild);CreateBiTree(T->rchild);return OK; int TreeDepth(BiTree T)/遞歸法求樹的深度/思路：如果樹為空樹則深度為0，否則，先遞歸計(jì)算出左子樹的深度，再計(jì)算出右子樹的深度，最后，樹的深度為兩子樹深度的最大值加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 LeafCount

4、(BiTree T)/遞歸法統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)/思路：如果樹為空樹則葉子結(jié)點(diǎn)的個(gè)數(shù)0，如果樹為一個(gè)結(jié)點(diǎn)樹則葉子結(jié)點(diǎn)的個(gè)數(shù)1，否則，先遞歸計(jì)算出左子樹的葉子結(jié)點(diǎn)的個(gè)數(shù)，/再計(jì)算出右子樹的葉子結(jié)點(diǎn)的個(gè)數(shù)，最后，樹的葉子結(jié)點(diǎn)的個(gè)數(shù)為兩子樹葉子結(jié)點(diǎn)的個(gè)數(shù)和加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)/遞歸法統(tǒng)計(jì)所有結(jié)點(diǎn)的個(gè)

5、數(shù)/思路：如果樹為空樹則葉子結(jié)點(diǎn)的個(gè)數(shù)0，否則，先遞歸計(jì)算出左子樹的葉子結(jié)點(diǎn)的個(gè)數(shù)，再計(jì)算出右子樹的葉子結(jié)點(diǎn)的個(gè)數(shù)，/最后，樹的葉子結(jié)點(diǎn)的個(gè)數(shù)為兩子樹葉子結(jié)點(diǎn)的個(gè)數(shù)和加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)(TElemType)/算法思路

6、:定義輸出函數(shù)PrintElem，調(diào)用樹的先序遍歷函數(shù),并將其傳遞給先序遍歷函數(shù)中的參數(shù)visit即可,假設(shè)元素為字符型if(T)if( (*visit)(T->data) ) /s1if( PreOrderTraverse(T->lchild,(*visit) /s2if( PreOrderTraverse(T->rchild,(*visit) /s3return OK;return ERROR; /只要有一次訪問失敗則必執(zhí)行此語句else return OK; /樹空時(shí)返回OK Status InOrderTraverse(BiTree T,Status(*visit)(

7、TElemType) /算法思路:定義輸出函數(shù)PrintElem，調(diào)用樹的中序遍歷函數(shù),并將其傳遞給中序遍歷函數(shù)中的參數(shù)visit即可,假設(shè)元素為字符型if(T)if( InOrderTraverse(T->lchild,(*visit) /s1if( (*visit)(T->data) ) /s2if( InOrderTraverse(T->rchild,(*visit) /s3return OK;return ERROR; /只要有一次訪問失敗則必執(zhí)行此語句else return OK; /樹空時(shí)返回OK Status PostOrderTraverse(BiTree T

8、,Status(*visit)(TElemType)if(T)if( InOrderTraverse(T->lchild,(*visit) /s1if( InOrderTraverse(T->rchild,(*visit) /s2if( (*visit)(T->data) ) /s3return OK;return ERROR; /只要有一次訪問失敗則必執(zhí)行此語句else return OK; /樹空時(shí)返回OKStatus ExchangeBiTree(BiTree &T)/二叉樹用二叉鏈表存儲(chǔ),左右互換BiTNode *temp;if(T=NULL)return O

9、K;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的中序輸出序列為：&qu

10、ot;);InOrderTraverse(BiT,PrintTElem);printf("n");printf("二叉樹BiT的后序輸出序列為：");PostOrderTraverse(BiT,PrintTElem);printf("n");printf("二叉樹BiT樹深：%dn",TreeDepth(BiT);printf("二叉樹BiT結(jié)點(diǎn)總數(shù)：%dn", NodeCount(BiT);printf("遞歸求得二叉樹BiT葉子結(jié)點(diǎn)數(shù)為：%dn",LeafCount(Bi

11、T);ExchangeBiTree(BiT);printf("二叉樹BiT的先序輸出序列為：");PreOrderTraverse(BiT,PrintTElem);printf("n");printf("二叉樹BiT的中序輸出序列為：");InOrderTraverse(BiT,PrintTElem);printf("n");printf("二叉樹BiT的后序輸出序列為：");PostOrderTraverse(BiT,PrintTElem);printf("n");60設(shè)計(jì)

12、算法統(tǒng)計(jì)孩子兄弟表示的樹或森林的葉子結(jié)點(diǎn)數(shù)(提示：用遞歸,仿照求 森林的 深度。葉子意味著firstchild為空,注意第一棵樹的葉子數(shù)如何求)作業(yè):求哈夫曼編碼，A-H出現(xiàn)頻率 (%) 7， 19，2，6，32，3，21，10#include<stdio.h>#include<stdlib.h>#include<string.h>#define N 100/ 赫夫曼樹和赫夫曼編碼的存儲(chǔ)表示typedef structchar ch;unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*H

13、uffmanTree;typedef char * *HuffmanCode;int min(HuffmanTree &HT,int i) / 函數(shù)void select()調(diào)用 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

14、(HT,i) ; s2=min(HT,i); /構(gòu)造赫夫曼樹 HT , 并求出 n 個(gè)字符的赫夫曼編碼 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) p->ch=chai;p->we

15、ight=wi;p->parent=0;p->lchild=0;p->rchild=0;for(;i<=m;+i,+p)p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;for(i=n+1;i<=m;+i) Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeo

16、f(char *);char *cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i<=n;+i)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild = c) cd-start=0;else cd-start=1;HCi=(char *)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);printf("字符為%c",HTi.ch);printf("的編碼是%sn "

17、;,HCi);free(cd);/ 赫夫曼譯碼函數(shù)void DeCoding(HuffmanTree &HT,HuffmanCode &HC,int n)char fN;printf("請(qǐng)輸入一串字符串:n");getchar();gets(f);int i;int m,k=0;while(fk!=0)for(i=1;i<=n;i+) m=strlen(HCi);if(strncmp(HCi,f+k,m)=0) k=k+m;printf("輸出%s的字符是",HCi);printf("%cn",HTi.ch);v

18、oid displayHT(HuffmanTree &HT,int n,int m) int i;printf("打印赫夫曼HC存儲(chǔ)結(jié)構(gòu)n");printf("編號(hào) 字符 權(quán)重 雙親 左孩子 右孩子n");for(i=1;i<=n;i+)printf("%dt%ct%dt%dt%dt%dn",i,HTi.ch,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);for(i=n+1;i<=m;i+)printf("%dt t%dt%dt%dt%dn",i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);main() HuffmanTree HT;HuffmanCode HC;int n,i;printf("*建赫夫曼樹,編碼和譯碼程序*&