C語言二叉樹與堆的概念與實現
引言—樹的故事
在自然界中有很多樹 它們是這樣的
但是在我們的眼中 他是這樣的
顯而易見 樹的特點就是一對多 ，我們利用這個一對多的特點，可以讓我們更好的解決編程中的問題，在樹中 ，最基礎的二叉樹是我們的重點研究對象。
在看一眼神奇的堆排序的動態(tài)圖
做事情，先求對，在求巧，一步一步才可有所成就，所以讓我們從基礎開始吧！
樹的基本性質和描述
樹是一個一對多的特殊數據類型，樹的根在上 葉子在上 。有種一生二，二生三，三生萬物的感覺。
樹的基本特點
樹有且只有一個根，且根沒有后繼結點。
樹是互不相交的
ps： 圖可知 不構成閉合回路則不相交。
每一個結點可在分為一個子樹。
樹的定義是一個遞歸定義，即樹在定義時又會用到樹的概念，他道出了樹的固有特性。
樹的關鍵字解析
樹有一大段關鍵字很讓人頭疼
結點的分類：
ps：
結點的度： 結點擁有的子樹數稱為結點的度。度為0的點成為葉節(jié)點或終端結點，度不為0的節(jié)點稱為非終端結點。樹的度是樹內各個結點的最大值。此圖 D為最大的結點，
結點的層次：從根開始為第一層，依次遞增
簡單對比 樹形結構與線性結構：
樹的表示方法
雙親表示法
typedef struct
{
int data;
int parent; // 雙親位置
}PtNode;
typedef struct
{
PtNode nodes[10];
int root ;
int n;
}PTree;
此圖數字表示父親的結點
通過“父親的下標”即可找到父親的位置
注：
找雙親時間復雜度 O(1);找結點兒子需要遍歷樹
數據的增刪查改。
左孩子右兄弟
typedef struct CSNode
{
int data;
struct CSNode* firstchild, * rightsib;
};
左孩子右兄弟的方式就是 多一個指針 一個指針指向自己最左側的孩子 另一個指針指向自己右側兄弟
這種表示法是我們常用的表示法。
二叉樹的概念結構
二叉樹
二叉樹是一種特殊的樹，他的特點是一個根節(jié)點兩個子節(jié)點，這兩個子節(jié)點又分別叫做左子樹和右子樹。
注意
二叉樹的度不超過二二叉樹左右子樹不可顛倒二叉樹有且只有一個子樹時，也需要區(qū)分左右。
特殊二叉樹
滿二叉樹
一個二叉樹每一層都是滿的，那么這個二叉樹就是滿二叉樹。如果一個二叉樹的層數為k，且結點總數是（2^k）-1
完全二叉樹
一個完全二叉樹的前k層都是滿的第k層可以不滿 ，但是必須連續(xù)，及滿足先左后右。
注意
滿二叉樹一定是完全二叉樹，反之就不對。完全二叉樹一定是先左后右，如下圖則不對
完全二叉樹葉子的結點都在最后兩層，左側集中最后第k層的葉子，右側集中第k-1層的葉子
二叉樹的性質
在二叉樹的第i層上至多有2^(i-1)的結點i>0
深度為k的二叉樹至多有2^k-1個結點
對任何一個二叉樹T，如果其終端結點樹為n0，度為2的結點樹為n2則no=n2+1；
具有n個結點的完全二叉樹的深度為log2(n)+1
對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的順序從0開始編號，則對與序號為i的結點有：
1. 若i>0,i位置結點的雙親序號為(i-1)/2；
2. 若2i+1<n,左孩子序號：2i+1,2i+1>=n則無左孩子
3. 若2i+2<n,右孩子序號；2i+2,2i+2>=n則無有孩子
假設父親的結點序號為parent，左孩子為leftchild，右孩子為ringhtchild。
有： leftchild=parent*2+1
rightchild=parent*2+2
e~g
在具有2n個結點的完全二叉樹中，葉子的結點個數為
解 在完全二叉樹中有且只有3種情況
度為0
度為0，即只有根結點 葉子的結點個數也為n
有且只有一個度為1的結點
設 x等于讀為2的結點數 ，y等于葉子節(jié)點數 x+y+1=2n 又由葉子數等于度為2的加1得 y=x+1
得 y=n
沒有度為1的結點
由圖可知 顯然不能構成偶數個結點 故舍棄。
綜上所述：葉子節(jié)點個數為n
一個具有完全二叉樹的節(jié)點數為531個，那么這棵樹的高度是
解： 直接帶公式得 10；
一個具有767個結點的完全二叉樹，其葉子節(jié)點個數為。
解 由前面的結論可知 此二叉樹必定是
所以 設雙結點為x 葉子為y y=x+1 且 y+y-1=767 解得 y=384
一顆度為2的樹和二叉樹有什么區(qū)別
解：
度為2的樹是無序樹 不區(qū)分左右 ，而二叉樹必須先左后右。度為2的樹 一定有一個結點度為2，二叉樹可以沒有
證明 一個滿k叉樹上的葉子結點數n0和非葉子結點數n1瞞住*n0=(k-1)n1+1
首先，我們知道了滿二叉樹 ，滿k叉樹就是第n層以上的所有個結點的度都為k
總分支結點數=k倍的n1
總結點數=n0+n1
總分支結點數+1=總結點數
kn1+1=no+n1
二叉樹的存儲結構
二叉樹的存儲是按照自上而下，從左往右的排序的
如果將該二叉樹存入數組中 就會得到
二叉樹與堆
堆是一種特殊的數，即是完全二叉樹。
觀察這個樹 他的父結點都小于子結點，我們稱之為最小堆，反之如果所有的父結點都比子結點大，這樣的完全二叉樹就被成為最大堆
注意：
堆是一顆完全二叉樹堆只有大堆和小堆兩種每個子樹都是堆
堆的實現
有如下數組
int arr[] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
如何將其調整成最小堆呢？
由圖可知，最小堆的特點就是父親小于兒子 ，而此樹圈起來的地方兒子大于父親，所以我們需要把最小的兒子換上去。
換下來后 我們發(fā)現還是不滿足 所以還得交換
畫圈處該二叉樹任然不滿足 只需要在交換一次，便是最小堆了
此時二叉樹滿足了最小堆。
此過程的算法，我們稱之為向下調整算法，如果我們將一顆二叉樹分區(qū) 即
向下調整的本質就是先滿足上面的，在滿足下面的
注意：
向下調整算法，被調整元素的左右字樹都必須是最小堆。向下調整算法，調整到葉子結點時，即可停止如果小的孩子比父親打，則不需要處理，整個樹已經是最小堆。
附上代碼
#include<stdio.h>
void AdjustDown(int a[], int n, int parent)
{
int child = 2 * parent + 1;//套用公式可得
while (child < n)
{
if (child+1<n&&a[child] > a[child + 1])
{
child++;
}
if (a[parent] > a[child])
{
int tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
int main()
{
int arr[14] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
int n = 14;
AdjustDown(arr, n, 0);
return 0;
}
代碼解讀
那么更一般的情況 左右子樹都不是小堆的情況 ，怎么調整呢？
我們只需自下而上，由小的堆樹變成大的堆樹
即是 先滿足下面在滿足上面
先滿足下面的堆 在滿足上面 那么 只需要給函數依次傳進去所有的父親結點即可
#include<stdio.h>
void AdjustDown(int a[], int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)
{
if (child+1<=n && a[child] >a[child + 1])
{
child++;
}
if (a[parent] < a[child])
{
int tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
int main()
{
int arr[14] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
int n = 14;
int tmp = 0;
int i = (n - 1 - 1) / 2;
for (i; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
return 0;
}
堆排序
以升序為例 ，我們首先會想到小堆 但是 小堆不適合。我們看
我們知道 堆頂元素一定是最小的 那么我們只需要依次拿走堆頂
當我們拿走2 后 7成了堆頂 之后
當去掉堆頂后 下一個元素補上 小堆蕩然無存，順序全亂了 。所以，小堆不適合排升序。
大堆排升序又該怎么辦呢？
此時 ，我們只需要把10和80互換，不把80考慮在堆內
那么代碼實現又當如何呢？
附上整體代碼
#include<stdio.h>
void AdjustDown(int a[], int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)
{
if (child+1<n && a[child] <a[child + 1])
{
child++;
}
if (a[parent] < a[child])
{
int tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
int main()
{
int arr[14] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
int n =14 ;
int tmp = 0;
int i = (n - 1 - 1) / 2;
for (i; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
int end = n - 1;
while (end > 0)
{
int tmp = arr[0];
arr[0] = arr[end];
arr[end] = tmp;
AdjustDown(arr, end, 0);
end--;
}
return 0;
}
堆排序是一種高效的排序
堆的總結：
- 物理結構是一個數組
- 邏輯結構是完全二叉樹
- 大堆與小堆關系
- 堆排序
- 插入元素
- 快速找出最大或最小
堆的功能實現
堆的插入
的插入，要求插入之后還是堆。 這里我們引入堆的向上調整
那么代碼如何實現呢？ 和向下排序類似
附上代碼
void AdjustUp(int* a, int n, int child)
{
int parent = (child - 1) / 2;
while (child>0)
{
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
插入元素后經過一次向上排序即可。
也可以使用向下排序 但麻煩許多。
TOPK問題
TopK問題的本質就是取小堆取頂操作 建堆 ，然后取頂，甚至你可以說就是一個排順序。把前四個放進別的數組。但是排序就意味著時間復雜度的加重 ， 請讀者使用建堆知識，取堆頂數據的方式，拿到最小數據， 這里給出題目和答案
* Note: The returned array must be malloced, assume caller calls free().
*/
/* 交換 */
void swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
/* 從堆下層向上交換元素，使得堆為大根堆 */
void swim(int* nums, int k) {
while (k > 1 && nums[k] > nums[k / 2]) {
swap(&nums[k], &nums[k / 2]);
k /= 2;
}
}
/* 從堆上層向下層交換元素，使得堆為大根堆 */
void sink(int* nums, int k, int numsSize) {
while (2 * k < numsSize) {
int child = 2 * k;
if (child < numsSize && nums[child] < nums[child + 1]) {
child++;
}
if (nums[k] > nums[child]) {
break;
}
swap(&nums[k], &nums[child]);
k = child;
}
}
/* 定義堆的結構體 */
typedef struct Heap {
int* data;
int szie;
int capacity;
}T_Heap, *PT_Heap;
/* 初始化一個堆 */
PT_Heap createHeap(int k) {
PT_Heap obj = (PT_Heap)malloc(sizeof(T_Heap));
obj->data = (int*)malloc(sizeof(int) * (k + 1));
obj->szie = 0;
obj->capacity = k + 1;
return obj;
}
/* 判斷堆是否為空 */
bool isEmpty(PT_Heap obj) {
return obj->szie == 0;
}
/* 獲得堆的當前大小 */
int getHeapSize(PT_Heap obj) {
return obj->szie;
}
/* 將元素入堆 */
void pushHeap(PT_Heap obj, int elem) {
/* 新加入的元素放入堆的最后 */
obj->data[++obj->szie] = elem;
/* 對當前堆進行排序,使其成為一個大根堆 */
swim(obj->data, obj->szie);
}
/* 獲得堆頂元素 */
int getHeapTop(PT_Heap obj) {
return obj->data[1];
}
/* 將堆頂元素出堆 */
int popHeap(PT_Heap obj) {
/* 保存堆頂元素 */
int top = obj->data[1];
/* 將堆頂元素和堆底元素交換,同時堆長度減一 */
swap(&obj->data[1], &obj->data[obj->szie--]);
/* 將原先的堆底元素賦值為INT_MIN */
obj->data[obj->szie + 1] = INT_MIN;
/* 從堆頂開始重新堆化 */
sink(obj->data, 1, obj->szie);
return top;
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
/* 若數組為空、或k為0，返回NULL */
if (arrSize == 0 || k == 0) {
*returnSize = 0;
return NULL;
} else {
*returnSize = k;
}
/* 返回數組長度為k */
int* ret = (int*)calloc(k, sizeof(int));
/* 初始化一個大小為k的堆 */
PT_Heap heap = createHeap(k);
/* 將輸入數組前k個元素堆化 */
for (int i = 0; i < k; i++) {
pushHeap(heap, arr[i]);
}
/* 將輸入數組剩下的元素依次插入堆，得出最小的k個數 */
for (int i = k; i < arrSize; i++) {
if (arr[i] < getHeapTop(heap)) {
popHeap(heap);
pushHeap(heap, arr[i]);
}
}
/* 將堆中元素傳入返回數組 */
for (int i = 0; i < k; i++) {
ret[i] = popHeap(heap);
}
return ret;
}
二叉樹的結構以及實現
二叉樹的遍歷
1、先序遍歷
若二叉樹為空，則空操作；否則
訪問根節(jié)點；
先序遍歷左子樹
先序遍歷右子樹；
2、中序遍歷
若二叉樹為空，則空操作；否則
中序遍歷左子樹
訪問根節(jié)點；
中序遍歷右子樹；
3、后序遍歷
后序遍歷左子樹
后序遍歷右子樹；
訪問根節(jié)點；
代碼實現
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf(" NULL ");
return;
}
printf(" %c ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL");
return;
}
InOrder(root->left);
printf(" %c ", root->data);
InOrder(root->right);
}
void PostOrder(BTNode* root)
{
const BTNode* a = root;
if (root == NULL)
{
printf(" NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf(" %c ", root->data);
}
程序實現方法 以及遞歸小技巧 遞歸先確定你要遞歸的函數的功能 比如：他返回什么，他傳入什么，他干了什么分情況討論 盡可能分清楚。設計好函數出口
以本題為例
只要這三行代碼 順序變化 那么遍歷方式也變化，這是為什么呢。
首先 函數的出口為root為空 而PostOrder(root->left);則是一直往左子樹方向走，走到什么時候進行下一句呢？ 走到底，走到底之后 就如圖
此時根據函數出口，return ； 回回到上一層 如圖
此時進入 PostOrder(root->right); 如圖
此時又滿足了 函數出口 返回上一層 回到 19 往下走 打印 如此往復 我們得出結論，遍歷只需要換即可。
總結
到此這篇關于C語言二叉樹與堆的文章就介紹到這了,更多相關C語言二叉樹與堆內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了C++的輸入和輸出流，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
趁空閑時間，小編決定把C++的排序算法分析并總結下，以便溫故知新。也方便需要的朋友可以參考學習。2016-07-07
大家好，本篇文章主要講的是關于C++中二分法詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-02-02
std::stack?是?C++?標準模板庫（STL）中的容器適配器,它提供了棧（stack）的功能,基于其他序列容器實現,下面給大家介紹std::stack?的用法總結,感興趣的朋友一起看看吧2024-01-01
這篇文章主要介紹了C++中的內存分區(qū)介紹,C++的內存劃分為棧區(qū)、堆區(qū)、全局區(qū)/靜態(tài)區(qū)、字符串常量和代碼區(qū),本文分別對他們一一說明,需要的朋友可以參考下2015-07-07
這篇文章主要為大家介紹了C語言使用setjmp和longjmp實現一個簡單的協程過程詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-12-12
本文主要介紹了C語言#define預處理宏定義，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
本文主要介紹C語言 位運算的基礎知識，這里整理了相關資料及示例代碼，有興趣的小伙伴可以參考下2016-08-08
這篇文章主要介紹了C語言之沒有main函數的helloworld示例,本文分解了帶main函數的helloworld示例,從而分析出不需要main函數的helloworld示例,需要的朋友可以參考下2015-03-03
C++?Stack（堆棧）?是一個容器類的改編，為程序員提供了堆棧的全部功能，也就是說實現了一個先進后出（FILO）的數據結構，許多程序都使用了?queue?容器。queue?容器可以用來表示超市的結賬隊列或服務器上等待執(zhí)行的數據庫事務隊列2022-03-03