哈夫曼樹
#include <stdio.h>
#include <stdlib.h>
#define MAXLEN 100typedef struct {int weight;int lchild, rchild, parent;
} HTNode;typedef HTNode HT[MAXLEN];
int n;void CreatHFMT(HT T);
void InitHFMT(HT T);
void InputWeight(HT T);
void SelectMin(HT T, int i, int *p1, int *p2);
void PrintHFMT(HT T);
void hfnode(HT T, int i, int j);
void haffmannode(HT T);int main() {HT HT;CreatHFMT(HT);PrintHFMT(HT);haffmannode(HT);return 0;
}void CreatHFMT(HT T) {int i, p1, p2;InitHFMT(T);InputWeight(T);for (i = n; i < 2 * n - 1; i++) {SelectMin(T, i - 1, &p1, &p2);T[p1].parent = T[p2].parent = i;T[i].lchild = p1;T[i].rchild = p2;T[i].weight = T[p1].weight + T[p2].weight;}
}void InitHFMT(HT T) {int i;printf("\n請輸入共有多少個權值(小于100)：");scanf("%d", &n);for (i = 0; i < 2 * n - 1; i++) {T[i].weight = 0;T[i].lchild = -1;T[i].rchild = -1;T[i].parent = -1;}
}void InputWeight(HT T) {int w, i;for (i = 0; i < n; i++) {printf("輸入第%d個權值:", i + 1);scanf("%d", &w);getchar();T[i].weight = w;}
}void SelectMin(HT T, int i, int *p1, int *p2) {long min1 = 888888, min2 = 888888;int j;for (j = 0; j <= i; j++) {if (T[j].parent == -1) {if (min1 > T[j].weight) {min1 = T[j].weight;*p1 = j;}}}for (j = 0; j <= i; j++) {if (T[j].parent == -1) {if (min2 > T[j].weight && j != (*p1)) {min2 = T[j].weight;*p2 = j;}}}
}void PrintHFMT(HT T) {int i;printf("哈夫曼樹的各邊顯示:\n");for (i = 0; i < 2 * n - 1; i++) {if (T[i].lchild != -1) {printf("(%d,%d),(%d,%d)\n", T[i].weight, T[T[i].lchild].weight, T[i].weight, T[T[i].rchild].weight);}}
}void hfnode(HT T, int i, int j) {j = T[i].parent;if (T[j].rchild == i) {printf("1");} else {printf("0");}if (T[j].parent != -1) {hfnode(T, j, i);}
}void haffmannode(HT T) {int i, j;printf("\n輸入權值的對應哈夫曼編碼:\n");for (i = 0; i < n; i++) {printf("%d的編碼為: ", T[i].weight);hfnode(T, i, -1); // -1 表示遞歸的初始狀態printf("\n");}printf("\n ");
}
運行結果
二叉樹
#include <stdio.h>
#include <malloc.h>
#define MAX 100
int count = 0; /*定義計算結點個數的變量*/
typedef struct tnode
{char data;struct tnode* lchild, * rchild;
}BT;BT* CreateBTree()
{BT* t;char ch;scanf("%c", &ch);getchar();if (ch == '0')t = NULL;else{t = (BT*)malloc(sizeof(BT));t->data = ch;printf("請輸入%c結點的左孩子結點：", t->data);t->lchild = CreateBTree();printf("請輸入%c結點的右孩子結點：", t->data);t->rchild = CreateBTree();}return t;
}void ShowBTree(BT* T) /*用廣義表表示法顯示二叉樹*/
{if (T != NULL) /*當二叉樹非空時*/{printf("%c", T->data); /*輸入該結點數據域*/if (T->lchild != NULL) /*若其左子樹非空*/{printf("("); /*輸入左括號*/ShowBTree(T->lchild); /*遞歸調用該函數輸出其左子樹各結點*/if (T->rchild != NULL) /*若其右子樹非空*/{printf(","); /*輸出逗號*/ShowBTree(T->rchild); /*遞歸調用該函數輸出其右子樹各結點*/}printf(")");}elseif (T->rchild != NULL) /*二叉樹左子樹為空，右子樹不為空時*/{printf("("); /*輸入左括號*/ShowBTree(T->lchild); /*遞歸調用該函數輸出其左子樹各結點*/if (T->rchild != NULL) /*若其右子樹非空*/{printf(","); /*輸出逗號*/ShowBTree(T->rchild); /*遞歸調用該函數輸出其右子樹各結點*/}printf(")");}}
}void PreOrder(BT* T) /* 先序遍歷二叉樹T*/
{if (T == NULL) return; /* 遞歸調用的結束條件*/else{printf("%c", T->data); /* 輸出結點的數據域*/PreOrder(T->lchild); /* 先序遞歸遍歷左子樹*/PreOrder(T->rchild); /* 先序遞歸遍歷右子樹*/}
}void InOrder(BT* T) /* 中序遍歷二叉樹T*/
{if (T == NULL) return; /* 遞歸調用的結束條件*/else{InOrder(T->lchild); /* 中序遞歸遍歷左子樹*/printf("%c", T->data); /* 輸出結點的數據域*/InOrder(T->rchild); /* 中序遞歸遍歷右子樹*/}
}void PostOrder(BT* T) /* 后序遍歷二叉樹T*/
{if (T == NULL) return; /* 遞歸調用的結束條件*/else{PostOrder(T->lchild); /* 后序遞歸遍歷左子樹*/PostOrder(T->rchild); /* 后序遞歸遍歷右子樹*/printf("%c", T->data); /* 輸出結點的數據域*/}
}void LevelOrder(BT* T) /*按層次遍歷二叉樹T*/
{int f, r; /*定義隊頭隊尾指針*/BT* p, * q[MAX]; /*定義循環隊列，存放結點指針*/p = T;if (p != NULL) /*若二叉樹非空，則根結點地址入隊*/{f = 1; q[f] = p; r = 2;}while (f != r) /*隊列不空時*/{p = q[f];printf("%c", p->data); /*訪問隊首結點的數據域*/if (p->lchild != NULL) /*將隊首結點的左孩子入隊*/{q[r] = p->lchild; r = (r + 1) % MAX;}if (p->rchild != NULL) /*將隊首結點的右孩子入隊*/{q[r] = p->rchild; r = (r + 1) % MAX;}f = (f + 1) % MAX;}
}void Leafnum(BT* T) /*求二叉樹葉子結點數*/
{if (T) /*若樹不為空*/{if (T->lchild == NULL && T->rchild == NULL)count++; /*全局變量count為計數值，其初值為0*/Leafnum(T->lchild); /*遞歸統計T的左子樹葉子結點數*/Leafnum(T->rchild); /*遞歸統計T的右子樹葉子結點數*/}
}void Nodenum(BT* T)
{if (T) /*若樹不為空*/{count++; /*全局變量count為計數值，其初值為0*/Nodenum(T->lchild); /*遞歸統計T的左子樹結點數*/Nodenum(T->rchild); /*遞歸統計T的右子樹結點數*/}
}int TreeDepth(BT* T) /*求二叉樹深度*/
{int ldep = 0, rdep = 0; /*定義兩個整型變量，用以存放左、右子樹的深度*/if (T == NULL)return 0;else{ldep = TreeDepth(T->lchild); /*遞歸統計T的左子樹深度*/rdep = TreeDepth(T->rchild); /*遞歸統計T的右子樹深度*/if (ldep > rdep)return ldep + 1;elsereturn rdep + 1;}
}void MenuTree() /*顯示菜單子函數*/
{printf("\n 二叉樹子系統");printf("\n =================================================");printf("\n| 1——建立一個新二叉樹 |");printf("\n| 2——廣義表表示法顯示 |");printf("\n| 3——先序遍歷 |");printf("\n| 4——中序遍歷 |");printf("\n| 5——后序遍歷 |");printf("\n| 6——層次遍歷 |");printf("\n| 7——求葉子結點數目 |");printf("\n| 8——求二叉樹總結點數目 |");printf("\n| 9——求樹深度 |");printf("\n| 0——返回 |");printf("\n ================================================");printf("\n請輸入菜單號（0-9）:");
}main()
{BT* T = NULL;char ch1, ch2, a;ch1 = 'y';while (ch1 == 'y' || ch1 == 'Y'){MenuTree();scanf("%c", &ch2);getchar();switch (ch2){case '1':printf("請按先序序列輸入二叉樹的結點：\n");printf("說明：輸入結點后按回車（'0'表示后繼結點為空）：\n");printf("請輸入根結點：");T = CreateBTree();printf("二叉樹成功建立！"); break;case '2':printf("二叉樹廣義表表示法如下：");ShowBTree(T); break;case '3':printf("二叉樹的先序遍歷序列為：");PreOrder(T); break;case '4':printf("二叉樹的中序遍歷序列為：");InOrder(T); break;case '5':printf("二叉樹的后序遍歷序列為：");PostOrder(T); break;case '6':printf("二叉樹的層次遍歷序列為：");LevelOrder(T); break;case '7':count = 0; Leafnum(T);printf("該二叉樹有%d個葉子。", count); break;case '8':count = 0; Nodenum(T);printf("該二叉樹共有%d個結點。", count); break;case '9':printf("該二叉樹的深度是%d。", TreeDepth(T)); break;case '0':ch1 = 'n'; break;default:printf("輸入有誤，請輸入0-9進行選擇！");}if (ch2 != '0'){printf("\n按回車鍵繼續，按任意鍵返回主菜單！\n");a = getchar();if (a != '\xA'){getchar(); ch1 = 'n';}}}
}
?運行結果
?
