1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
|
#include <stdio.h> #include <stdlib.h> typedef struct TreeNode { int weight; int parent; int lchild; int rchild; }TreeNode;
typedef struct HFTree { TreeNode* data; int length; }HFTree;
HFTree* initTree(int* weight, int length) { HFTree* T = (HFTree*)malloc(sizeof(HFTree)); T -> data = (TreeNode*)malloc(sizeof(TreeNode) * (2 * length - 1)); T -> length = length; for (int i = 0; i < length; i++) { T -> data[i].weight = weight[i]; T -> data[i].parent = 0; T -> data[i].lchild = -1; T -> data[i].rchild = -1; } return T; }
int* selectMin(HFTree* T) { int min = 10000; int secondMin = 10000; int minIndex; int secondIndex; for (int i = 0; i < T -> length; i++) { if (T -> data[i].parent == 0) { if (T -> data[i].weight < min) { min = T -> data[i].weight; minIndex = i; } } } for (int i = 0; i < T -> length; i++) { if (T -> data[i].parent == 0 && i != minIndex) { if (T -> data[i].weight < secondMin) { secondMin = T -> data[i].weight; secondIndex = i; } } } int* res = (int*)malloc(sizeof(int)* 2); res[0] = minIndex; res[1] = secondIndex; return res; }
void createHFTree(HFTree* T) { int* res; int min; int secondMin; int length = T -> length * 2 - 1; for (int i = T -> length; i < length; i++) { res = selectMin(T); min = res[0]; secondMin = res[1]; T -> data[i].weight = T -> data[min].weight + T -> data[secondMin].weight; T -> data[i].lchild = min; T -> data[i].rchild = secondMin; T -> data[i].parent = 0; T -> data[min].parent = i; T -> data[secondMin].parent = i; T -> length ++; } }
void preOrder(HFTree* T, int index) { if (index != -1) { printf("%d ", T -> data[index].weight); preOrder(T, T -> data[index].lchild); preOrder(T, T -> data[index].rchild); } }
int main() { int weight[7] = {5,1,3,6,11,2,4}; HFTree* T = initTree(weight, 7); createHFTree(T); preOrder(T, T -> length - 1); printf("\n"); return 0; }
|