一.堆的應用
1.堆排序
void test01()
{int arr[] = { 17,20,10,13,19,15 };int n = sizeof(arr) / sizeof(arr[0]);HP p;HPInit(&p);for (int i = 0; i < n; i++){HPPush(&p, arr[i]);}int i = 0;while (!HPEmpty(&p)){arr[i++] = HPTop(&p);HPPop(&p);}for (int i = 0; i < n; i++){printf("%d ", arr[i]);}HPDesTroy(&p);
}
但是真正的堆排序不是我們上面這種寫法，堆排序是借助堆的算法思想，而不能夠直接使用堆的數據結構來輔助實現，這個時候我們來看一看怎么來實現堆的排序。
首先先將這三個我之前寫的算法放到我們頭文件里，可以用來直接使用。
void Swap(int* x, int* y);
void AdjustUp(HPDataType* arr, int child);
void AdjustDown(HPDataType* arr, int parent, int n);
(1)向下調整算法建堆的堆排序
我們建的是小堆
void HeapSort(int* arr, int n)
{//向下調整算法建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}int end = n - 1;while (end){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}測試
建的是小堆，排的是降序的數組。所以排升序建大堆，排降序建小堆。
向下調整算法的最差的時間復雜度為O(logn)。
所以向下調整算法建堆的時間復雜度為：O(n×log n)。
總的來說，向下調整堆排序的時間復雜度就為：O(nlogn)。
(2)向上調整算法建堆的堆排序
我們這次來建一個大堆
//向上調整算法建堆for (int i = 0; i < n; i++){AdjustUp(arr, i);}int end = n - 1;while (end){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
測試
向上調整算法最差的時間復雜度為：O(log n)。
向上調整算法建堆的時間復雜度：O(nlogn)
向上調整堆排序的時間復雜度：O(nlogn)。
我們通過總結得：向下調整算法建堆的時間復雜度比較好，越向下，結點個數逐漸增多，向下調整次數逐漸減少。向上調整算法建堆剛好相反。
二.實現鏈式結構二叉樹
用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。 通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址，其二叉樹結點結構的定義如下：
1.二叉樹結點結構的定義
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
代碼實現
構造一棵二叉樹，將數據類型轉化成char。
2.獲取一個新結點
BTNode* buyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("molloc fail!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}3.手動構造一棵二叉樹
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;}4.前序遍歷
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);}
測試
5.中序遍歷
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);}
測試
6.后序遍歷
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}
測試
7.二叉樹結點個數
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
8.二叉樹葉子結點個數
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeaft(root->left) + BinaryTreeLeaft(root->right);
}
9.二叉樹第k層結點個數
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right,k-1);
}
10.二叉樹的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rihgtDep = BinaryTreeDepth(root->right);return 1 + (leftDep > rihgtDep ? leftDep : rihgtDep) ;
}
11.二叉樹查找值為x的結點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left,x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right,x);if (rightFind){return rightFind;}return NULL;
}
12.二叉樹銷毀
void BinaryTreeDestroy(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestroy(&((*root)->left));BinaryTreeDestroy(&((*root)->right));free(*root);*root = NULL;
}
)
