提示：文章寫完后，目錄可以自動生成，如何生成可參考右邊的幫助文檔
文章目錄
前言
1.樹概念及結構
1.1樹的概念
1.2 樹的相關概念?
1.3 樹的表示
1.4 樹在實際中的運用（表示文件系統(tǒng)的目錄樹結構）
2.二叉樹概念及結構
2.1概念
2.2?特殊的二叉樹：
2.3?二叉樹的存儲結構
3.二叉樹的順序結構及實現(xiàn)
3.1 二叉樹的順序結構
3.2 堆的分類、性質(zhì)與結構
4.堆的實現(xiàn)
4.1頭文件的實現(xiàn)——（Heap.h）
4.2源文件的實現(xiàn)——（Heap.c）
4.3測試文件的實現(xiàn)——（test.c）
5.實際數(shù)據(jù)測試展示
5.1小堆輸出結果
5.2大堆輸出結果
總結
前言
世上有兩種耀眼的光芒，一種是正在升起的太陽，一種是正在努力學習編程的你!一個愛學編程的人。各位看官，我衷心的希望這篇博客能對你們有所幫助，同時也希望各位看官能對我的文章給與點評，希望我們能夠攜手共同促進進步，在編程的道路上越走越遠！
提示：以下是本篇文章正文內(nèi)容，下面案例可供參考
1.樹概念及結構
1.1樹的概念
樹是一種非線性的數(shù)據(jù)結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
有一個特殊的結點，稱為根結點，根節(jié)點沒有前驅(qū)結點。
除根節(jié)點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i?<= m)又是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅(qū)，可以有0個或多個后繼。因此，樹是遞歸定義的。
注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構。
1.2 樹的相關概念 ?
1.3 樹的表示
樹結構相對線性表就比較復雜了，要存儲表示起來就比較麻煩了，既然保存值域，也要保存結點和結點之間的關系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡單的了解其中最常用的左孩子右兄弟表示法。
1.4 樹在實際中的運用（表示文件系統(tǒng)的目錄樹結構）
2.二叉樹概念及結構
2.1概念
一棵二叉樹是結點的一個有限集合，該集合:
1. 或者為空。
2. 由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉樹組成。二叉樹是一個特殊的樹，度最大為2。
從上圖可以看出：
1. 二叉樹不存在度大于2的結點
2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
注意：對于任意的二叉樹都是由以下幾種情況復合而成的：
2.2?特殊的二叉樹：
1. 滿二叉樹：一個二叉樹，如果每一個層的結點數(shù)都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為h，且結點總數(shù)是2^h-1 ，則它就是滿二叉樹。
每一層都是滿的。
2. 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為h的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為h的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
前h-1層是滿的，最后一層不一定滿，但是從左到右必須連續(xù)。
2.3?二叉樹的存儲結構
二叉樹一般可以使用兩種結構存儲，一種順序結構，一種鏈式結構。
1. 順序存儲
順序結構存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲，關于堆我們后面的章節(jié)會專門講解。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。
2. 鏈式存儲
這個我們下篇文章再講！
3.二叉樹的順序結構及實現(xiàn)
3.1 二叉樹的順序結構
普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。現(xiàn)實中我們通常把堆(一種二叉樹)使用順序結構的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進程地址空間中的堆是兩回事，一個是數(shù)據(jù)結構，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。
3.2 堆的分類、性質(zhì)與結構
堆的性質(zhì)：
堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；
堆總是一棵完全二叉樹。
堆的分類：
大堆：任意一個父親節(jié)點 >= 孩子節(jié)點。
小堆：任意一個父親節(jié)點 <= 孩子節(jié)點。
堆不一定是有序的。
二叉搜索樹，左子樹的值要比根要小，右子樹的值要比根要大。我們用來查找數(shù)據(jù)，最多查找高度次。
堆永遠只考慮父親和孩子的關系，而不考慮兄弟和叔侄之間的關系。
4.堆的實現(xiàn)
4.1頭文件的實現(xiàn)——（Heap.h）
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>
//這個代碼是針對小堆的
typedef int HPDataType;
//底層看上去是順序表，但其實不是，因為從邏輯上，我們把它看成是二叉樹，并且把它調(diào)整成大堆或小堆的順序
//順序表中進來的值沒有要求，但是堆是對值有順序要求的
typedef struct Heap
{
HPDataType* a;
int size;//數(shù)組有效的元素個數(shù) == 數(shù)組最后一個元素的下一個位置的下標
int capacity;
}HP;
//初始化
void HeapInit(HP* php);
//銷毀
void HeapDestroy(HP* php);
//插入數(shù)據(jù)
void HeapPush(HP* php, HPDataType x);
//規(guī)定刪除的是堆頂（根節(jié)點）
void HeapPop(HP* php);
//獲取堆頂元素
HPDataType HeapTop(HP* php);
//堆中的元素個數(shù)
size_t HeapSize(HP* php);
//判空
bool HeapEmpty(HP* php);
//向上調(diào)整法：
void AdjustUp(HPDataType* a, int child);
//向下調(diào)整法：
void AdjustDown(int* a, int size, int parent);
void Swap(HPDataType* p1, HPDataType* p2);
4.2源文件的實現(xiàn)——（Heap.c）
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
//初始化
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
//銷毀
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
//free()的是空，也沒有任何問題，free會對空進行檢查的
php->a = NULL;
php->capacity = php->size = 0;
}
//交換數(shù)組中的數(shù)據(jù)
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向上調(diào)整算法：
//為什么沒有把向上/下調(diào)整算法的第一個參數(shù)寫成結構體的地址形式呢？
//因為我們要把它寫成一個公共的，結構體可以用，數(shù)組也可以直接用
void AdjustUp(HPDataType*a,int child)
{
//第一個參數(shù)：數(shù)組的地址；第二個參數(shù)：最后一個元素的下標(孩子的下標)
int parent = (child - 1) / 2;//找孩子的父親節(jié)點下標
while (child > 0)
{
//小堆：任意一個父親都<=孩子
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//如果孩子的值比父親小，那父親的下標給給孩子，父親繼續(xù)往上比較，重新找父親的下標
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//插入一個數(shù)據(jù)的前提是：整棵樹本身是堆的形式。
//插入一個數(shù)據(jù)之后，還要保持堆的形式：
//1、相當于順序表的尾插；2、然后我們需要把插入的數(shù)據(jù)向上調(diào)整（調(diào)整數(shù)據(jù)可以用遞歸、也可以用循環(huán)）
void HeapPush(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, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
//向上調(diào)整算法：
AdjustUp(php->a, php->size - 1);
//第一個參數(shù)：首元素的下標；第二個參數(shù)：最后一個元素的下標
}
//向下調(diào)整算法：
//(左右子樹依舊是小堆，但是新的首部可能要比它的子樹值要大，我們可以把左右子樹最小的值與新的首進行比較，
//如果子樹值比新的首值要小，就交換；交換了值的子樹，要繼續(xù)跟它的左右子樹值進行比較，往復循環(huán)，直到葉節(jié)點為止)
void AdjustDown(int*a,int size,int parent)
{
int child = parent * 2 + 1;
//如何判斷葉節(jié)點呢？
//最后一個數(shù)據(jù)的下一個位置下標就是size，想判斷一個節(jié)點是否是葉節(jié)點，就看這個節(jié)點有沒有左孩子節(jié)點，
//這個節(jié)點的下標乘2加1，看有沒有超出size的范圍
while (child < size)
{
//小堆：任意一個父親的值都要<=孩子節(jié)點的值
//假設左孩子小，讓左孩子與右孩子比較，若右孩子更小，那就孩子下標+1
//但是有的子樹有左孩子，但是不一定有右孩子，那么當比較右孩子時，訪問右孩子的下標會造成越界訪問
if (child+1 <size && a[child + 1] < a[child])
{
child++;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//規(guī)定刪除的是堆頂（根節(jié)點）
//我們之前對順序表(底層結構是數(shù)組)中傳統(tǒng)的刪除數(shù)據(jù)的方式：挪動數(shù)據(jù)覆蓋，刪除根（O(N)）,
//(這樣會造成整棵樹的父子關系全亂了，大小關系亂了)
//我們使用另一種方式刪除數(shù)據(jù)：1、首尾交換；2、尾刪
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;//并不一定是真的刪除，只要不在數(shù)組的作用范圍內(nèi)就算刪除
//向下調(diào)整算法：
AdjustDown(php->a, php->size, 0);
//第一個參數(shù)：數(shù)組的地址；第二個參數(shù)：數(shù)組有效的元素個數(shù)；第三個參數(shù)：父親節(jié)點的下標
}
//獲取堆頂元素
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
//堆中的元素個數(shù)
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
//判空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
4.3測試文件的實現(xiàn)——（test.c）
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
//邏輯結構：想象出來的
//物理結構：內(nèi)存中實際存在的結構
//樹的高度或深度：我們從1開始計算，因為空樹時，為0，只有根節(jié)點時，高度為1；
//如果從0開始計算，那空樹時，為-1，只有根節(jié)點時，高度為0.
//堆不一定是有序的。
//不是完全二叉樹和滿二叉樹的話，適合用鏈式結構存儲
//完全二叉樹或滿二叉樹會演化出一個堆；堆有兩個含義：1、堆排序；2、top k問題
//普通的二叉樹沒有必要用堆進行存儲，沒有意義
//二叉搜索樹，左子樹的值要比根要小，右子樹的值要比根要大。我們用來查找數(shù)據(jù)，最多查找高度次
//堆永遠只考慮父親和孩子的關系，而不考慮兄弟和叔侄之間的關系。
//size：是最后一個有效數(shù)據(jù)的下一個位置，因為數(shù)組的下標是從0開始的
//向上和向下調(diào)整的時間復雜度最多是高度次，是O(logN)
//數(shù)據(jù)結構的第一要務：在內(nèi)存當中管理數(shù)據(jù)
int main()
{
int a[] = { 5,4,7,4,9,1,0,3 };
HP hp;
HeapInit(&hp);
//我們在這個地方?jīng)]有排序，排序的本質(zhì)，是要在數(shù)組這個地方排序
//我們只是把數(shù)組里的值插入到堆里面去，然后有序的從堆里走出來（小堆或大堆）
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
HeapPush(&hp, a[i]);
}
/*int k = 3;
while (k--)
{
printf("%d\n", HeapTop(&hp));
HeapPop(&hp);
}*/
while (!HeapEmpty(&hp))
{
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
printf("\n");
//實現(xiàn)數(shù)組的排序：我們可以用數(shù)據(jù)結構，把堆里面的值一個個的放回數(shù)組里（前提是有實現(xiàn)好的堆）
return 0;
}
5.實際數(shù)據(jù)測試展示
5.1小堆輸出結果
5.2大堆輸出結果
文章來源：http://www.zghlxwxcb.cn/news/detail-776750.html
總結
好了，本篇博客到這里就結束了，如果有更好的觀點，請及時留言，我會認真觀看并學習。
不積硅步，無以至千里；不積小流，無以成江海。文章來源地址http://www.zghlxwxcb.cn/news/detail-776750.html
到了這里，關于【數(shù)據(jù)結構—二叉樹的基礎知識介紹和堆的實現(xiàn)（順序表）】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
