【數據結構】C++語言實現二叉樹的介紹及堆的實現(詳細解讀)

?c語言中的小小白-CSDN博客c語言中的小小白關注算法,c++,c語言,貪心算法,鏈表,mysql,動態規劃,后端,線性回歸,數據結構,排序算法領域.https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343

給大家分享一句我很喜歡我話：

知不足而奮進，望遠山而前行！！！

鐵鐵們，成功的路上必然是孤獨且艱難的，但是我們不可以放棄，遠山就在前方，但我們能力仍然不足，所有我們更要奮進前行！！！

今天我們更新了二叉樹內容，

🎉 歡迎大家關注🔍點贊👍收藏??留言📝

樹

首先我們為大家說一下樹的概念和結構，樹是一種非線性的數據結構，它是由n(n >= 0)個有限結點組成的一個具有層次關系的集合，把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

有一個特殊的結點，稱為根結點，根節點沒有前驅結點。
除跟根結點外，其余結點被分成M（M>0）個互不相交的集合T1、T2…Tm,其中每一個集合Ti(1<=i<=m)又是一棵結構與樹類似的子樹。每顆子樹的根節點有且只有一個前驅，可以有0個或多個后繼。
因此，樹是遞歸定義的。

有關樹的一些概念：

節點的度:一個節點含有的子樹的個數稱為該節點的度;如上圖:A的為6
葉節點或終端節點:度為0的節點稱為葉節點;如上圖:B、C、H、I…等節點為葉節點非終端節點或分支節點:度不為0的節點;如上圖:D、E、F、G…等節點為分支節點
兄弟節點:具有相同父節點的節點互稱為兄弟節點;如上圖:B、C是兄弟節點
樹的度:一棵樹中，最大的節點的度稱為樹的度;如上圖:樹的度為6
節點的層次:從根開始定義起，根為第1層，根的子節點為第2層，以此類推;
樹的高度或深度:樹中節點的最大層次;如上圖:樹的高度為4（有兩種說法-從0開始還是從1開始，空樹-1，空樹0）
節點的祖先:從根到該節點所經分支上的所有節點;如上圖:A是所有節點的祖先
子孫:以某節點為根的子樹中任一節點都稱為該節點的子孫。如上圖:所有節點都是A的子孫
森林:由m (m>0)棵互不相交的多顆樹的集合稱為森林;(數據結構中的學習并查集本質就是一個森林)——(日常很少碰到森林，并查集就是一個森林)

其中這些概念中第 4、6、7條較為重要，其余了解一下即可。

樹的要求：

子樹是不相交的
除了根結點之外，每個結點有且僅有一個父結點
一個N個結點的樹有N-1條邊

樹的表示

相對于線性表，樹的結構就復雜很多了。最常用的表示方法——孩子兄弟表示法。

二叉樹

與普通的樹最大的不同是它最多只有兩個子樹。

特殊的二叉樹

滿二叉樹：每一層都是滿的。

假設一棵滿二叉樹的高度是 h,那么它的總結點個數是：20+21+22+…2(h-1) =N。

推導公式:2^h-1 = N;h = log2N+1以2位底N的對數+1。
完全二叉樹

完全二叉樹是個效率很高的數據結構，完全二叉樹是由滿二叉樹引出來的。

假設樹的高度是h,前h-1層是滿的，最后一層不滿，但是最后一層從左往右都是連續的。

最后一層最少有一個結點。

結點個數為:2^h-1-X= N,高度近似為:h = log2N+1+X以二為底N的對數+1

圖有點難看不要介意

這些就是關于樹的一些基本概念，下面我們來介紹一下關于樹的實現。

堆的實現：

這里我們將會分為初始化、銷毀、建堆、堆的刪除、取出堆頂元素、判斷是否為空、向上調整和向下調整這幾步來完成。

頭文件及堆結構的定義：

#pragma once
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include<algorithm>
#include<cmath>
#include<utility>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

初始化：

//初始化
void HPInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size= 0;}

銷毀：

void HPDestroy(HP* php)
{assert(php);free(php);php->a = NULL;php->capacity = php->size = 0;}

向上調整：

//向上調整(小根堆)
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child>0){if (a[child] < a[parent])//小于就換就相當于建小堆//if (a[child] > a[parent])//大于就換就會變成大堆{std::swap(a[child], a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

建堆：

void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc failed!!!");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size++] = x;//向上調整AdjustUp(php->a, php->size - 1);
}

向下調整：

void AdjustDown(HPDataType* a, int n, int parent)
{//假設法//假設左孩子小int child = parent * 2 + 1;while(child<n){if (child + 1 < n &&a[child + 1] < a[child])//這里如果是左孩子大于右孩子，就要再加加child{++child;}if (a[child] < a[parent]){std::swap(a[child], a[parent]);parent = child;child = parent * 2 + 1;}else break;}}

刪除堆頂的數據：

HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

判空：

bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

總代碼：

TEST.c:

#include"Heap.h"void TestHeap1()
{int a[] = { 4,2,8,1,5,6,7,9 };HP hp;HPInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&hp, a[i]);}while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);}HPDestroy(&hp);
}void HeapSort(int* a, int n)
{//首先建堆//升序：建大堆//降序：建小堆for (int i=0;i<n;i++){AdjustUp(a, i);}int end = n - 1;///這里>0即可，因為=0時只剩下最后一個，就不再需要繼續進行了while (end>0)//思路就是：比如我們升序排序，那么我們就利用大根堆，每次都將最大的那個數放在最頂上，然后將它和最后一個交換，然后讓整體的大小--，那么最后一個就不再會受影響{std::swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}}void TestHeap2()
{int a[] = { 4,2,8,1,5,6,9,7,3,10,23,14,125 };HeapSort(a, sizeof(a) / sizeof(0));for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){std::cout << a[i] << " ";}
}int main()
{TestHeap2();return 0;
}

Heap.c:

#include"Heap.h"//初始化
void HPInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size= 0;}//銷毀
void HPDestroy(HP* php)
{assert(php);free(php);php->a = NULL;php->capacity = php->size = 0;}//向上調整(小根堆)
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child>0){if (a[child] < a[parent])//小于就換就相當于建小堆//if (a[child] > a[parent])//大于就換就會變成大堆{std::swap(a[child], a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//建堆
void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc failed!!!");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size++] = x;//向上調整AdjustUp(php->a, php->size - 1);
}//向下調整
void AdjustDown(HPDataType* a, int n, int parent)
{//假設法//假設左孩子小int child = parent * 2 + 1;while(child<n){if (child + 1 < n &&a[child + 1] < a[child])//這里如果是左孩子大于右孩子，就要再加加child{++child;}if (a[child] < a[parent]){std::swap(a[child], a[parent]);parent = child;child = parent * 2 + 1;}else break;}}//刪除堆頂的數據
void HPPop(HP* php)
{assert(php);assert(php->size > 0);std::swap(php->a[0], php->a[php->size - 1]);//就是將第一個與最后一個換掉，然后將他們向下調整，php->size--;//直接size--刪去最后一個元素AdjustDown(php->a, php->size, 0);
}//取出堆頂數據
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

Heap.h:

#pragma once
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include<algorithm>
#include<cmath>
#include<utility>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//初始化
void HPInit(HP* php);//銷毀
void HPDestroy(HP* php);//建堆
void HPPush(HP* php,HPDataType x);//堆的刪除
void HPPop(HP* php);//取出堆頂數據
HPDataType HPTop(HP* php);bool HPEmpty(HP* php);void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);