本博客將以代碼的形式詳細講解二叉樹的所有算法，包括創建二叉樹，二叉樹的三種遍歷方式，二叉樹的各種屬性算法，如：求高度，求葉子節點數，求節點數，以及二叉樹最常見的應用哈夫曼樹，代碼如下：

# include<stdio.h> # include<string.h> # include<conio.h> # include<stdlib.h> # define N 1 # define M 2*N-1 typedef char * HC[N+1]; typedef struct bt {char x;struct bt *lchild;struct bt *rchild; }bt,*pbt; typedef struct {int parent;int weight, lchild, rchild; }HT[M+1]; void creatbt(pbt *root) {char ch=getchar();if(ch==' ')*root=NULL;else{*root=(pbt)malloc(sizeof(bt));(*root)->x=ch;creatbt(&((*root)->lchild));creatbt(&((*root)->rchild));} } void preorder(pbt root) {if(root!=NULL){printf("%c",root->x);preorder(root->lchild);preorder(root->rchild);} } void inorder(pbt root) {if(root!=NULL){inorder(root->lchild);printf("%c",root->x);inorder(root->rchild);} } void postorder(pbt root) {if(root!=NULL){postorder(root->lchild);postorder(root->rchild);printf("%c",root->x);} } int btdepth(pbt root,int h) {static int depth=0;if(root!=NULL){if(h>depth) depth=h;btdepth(root->lchild,h+1);btdepth(root->rchild,h+1);}return depth; } int nodenum(pbt root) {static int n=0;if(root!=NULL){ n++;nodenum(root->lchild);nodenum(root->rchild);}return n; } int leafnum(pbt root) {static int n=0;if(root!=NULL){leafnum(root->lchild);leafnum(root->rchild);if((root->lchild==NULL)&&(root->rchild==NULL))n++;}return n; } void select(HT ht,int n,int *x,int *y) {int i,min1=100,min2=200;for(i=1;i<=n;i++){if(ht[i].parent==0&&ht[i].weight<min1){min1=ht[i].weight;*x=i;}}for(i=1;i<=n;i++){if(ht[i].parent==0&&ht[i].weight<min2&&i!=*x){min2=ht[i].weight;*y=i;}}} void hafuman(HT ht,int w[],int n) {int i,k,m,x,y;for(i=1;i<=n;i++){ht[i].weight=w[i];ht[i].parent=ht[i].lchild=ht[i].rchild=0;}m=2*n-1;for(i=n+1;i<=m;i++){ht[i].parent=ht[i].lchild=ht[i].rchild=0;}for(i=n+1;i<=m;i++){select(ht,i-1,&x,&y);//選擇parent為0且權值最小的結點ht[i].weight=ht[x].weight+ht[y].weight;ht[i].lchild=x;ht[i].rchild=y;ht[x].parent=ht[y].parent=i;} } void hafumancode(HT ht,HC hc,int n) {int i,c,p,start;char * cd=(char *)malloc(n*sizeof(char));cd[n-1]='\0';//此處的cd用來存儲當前哈夫曼碼，可供循環利用，相當于一個暫存器for(i=1;i<=n;i++)//求n個葉子結點的哈夫曼碼{start=n-1;c=i;//因為下面會循環更新孩子結點，所以不能用i（否則第一次for循環后i可能就不再是1），可將i的值提前賦給cp=ht[i].parent;while(p!=0)//只要p不是根結點{start--;//此語句用來循環更新存儲下標if(ht[p].lchild==c)//cd[i]='0';//錯誤。注意應從葉子結點開始向上推cd[start]='0';else//cd[i]='1';cd[start]='1';c=p;//此語句用來循環更新孩子結點p=ht[p].parent;}hc[i]=(char *)malloc((n-start)*sizeof(char));strcpy(hc[i],&cd[start]);}free(cd);for(i=1;i<=n;i++){//printf("%d的哈夫曼碼為%s\n",ht[i],hc[i]);錯誤，ht[i]為結構數組，應寫其成員printf("%d的哈夫曼碼為%s\n",ht[i].weight,hc[i]);}} void main() {int n;pbt root;printf("\t\t-----------------------------------------\n");printf("\t\t1.創建二叉樹 2.遍歷二叉樹\n");printf("\t\t3.二叉樹的屬性 4.哈夫曼樹\n");printf("\t\t5.退出\n");printf("\t\t-----------------------------------------\n");while(1){printf("請選擇功能模塊(1-5)\n");scanf("%d",&n);//char ch=getche();getchar();switch(n){case 1:{printf("請以先序擴展創建二叉樹（空結點用空格代替）\n");creatbt(&root);}break;case 2:{printf("遍歷二叉樹\n");printf("\t\t[1]先序遍歷\n");printf("\t\t[2]中序遍歷\n");printf("\t\t[3]后序遍歷\n");printf("\t\t[4]返回主菜單\n");while(1){int n;printf("請選擇(1-4)：\n");scanf("%d",&n);if(1==n)preorder(root);if(2==n)inorder(root);if(3==n)postorder(root);//else//不能這樣寫，因為這個else只能與上一個if配對，所以當n!=3時break都會執行if(n==4)break;}}break;case 3:{int h=1,n;printf("二叉樹屬性\n");printf("\t\t[1]二叉樹高度\n");printf("\t\t[2]二叉樹結點數\n");printf("\t\t[3]二叉樹葉子結點\n");printf("\t\t[4]返回主菜單\n");while(1){printf("請選擇：(1-4)\n");scanf("%d",&n);if(1==n)printf("該二叉樹的高度為%d\n",btdepth(root,h));if(2==n)printf("該二叉樹的結點數為%d\n",nodenum(root));if(3==n)printf("該二叉樹的葉子結點數為%d\n",leafnum(root));if(n==4)break;}}break;case 4:{HT ht;HC hc;int n,i;printf("請輸入葉子結點的個數\n");scanf("%d",&n);int * w=(int *)malloc((n+1)*sizeof(int));//此語句必須位于scanf的下面for(i=1;i<=n;i++){printf("請輸入第%d個葉子結點的權值\n",i);scanf("%d",&w[i]);}hafuman(ht,w,n);hafumancode(ht,hc,n);}break;case 5:exit(1);}}}
程序運行結果如下：

注意對于同一個二叉樹，哈夫曼碼的結果不唯一，上述輸出只是一種情況。

轉載于:https://www.cnblogs.com/hainange/p/6334054.html

總結

以上是生活随笔為你收集整理的【二叉树系列】二叉树课程大作业的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。