C語言近萬字為你講透樹與二叉樹
一、樹概念及結(jié)構(gòu)
1.1 樹的概念
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點(diǎn)組成一個具有層次關(guān)系的集合。把它叫做樹是因 為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
·有一個特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)
·除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。
·每棵子樹的根結(jié)點(diǎn)有且只有一個前驅(qū)，可以有0個或多個后繼 因此，樹是遞歸定義的。
注意：樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)
1.2 樹的相關(guān)概念
節(jié)點(diǎn)的度：一個節(jié)點(diǎn)含有的子樹的個數(shù)稱為該節(jié)點(diǎn)的度； 如上圖：A的為6
葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)； 如上圖：B、C、H、I...等節(jié)點(diǎn)為葉節(jié)點(diǎn)
非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)； 如上圖：D、E、F、G...等節(jié)點(diǎn)為分支節(jié)點(diǎn)
雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)
孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)； 如上圖：B是A的孩子節(jié)點(diǎn)
兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)； 如上圖：B、C是兄弟節(jié)點(diǎn)
樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度； 如上圖：樹的度為6
節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
樹的高度或深度：樹中節(jié)點(diǎn)的最大層次； 如上圖：樹的高度為4
堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為兄弟節(jié)點(diǎn)
節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先
子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫
森林：由m（m>0）棵互不相交的樹的集合稱為森林；
1.3 樹的表示
樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要存儲表示起來就比較麻煩了，既然保存值域，也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之間 的關(guān)系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法 等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。
如下圖所示：
二、二叉樹概念及結(jié)構(gòu)
2.1 概念
什么是二叉樹？簡言之一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合:
1. 或者為空
2. 由一個根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成
如下圖示
從上圖我們可以看出二叉樹的兩個特點(diǎn)
1. 二叉樹不存在度大于2的結(jié)點(diǎn)
2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
注意：對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：
2.2 特殊的二叉樹：
1. 滿二叉樹：一個二叉樹，如果每一個層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉樹。也就是 說，如果一個二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是 ，則它就是滿二叉樹。
2. 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K 的，有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為K的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對 應(yīng)時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
2.3 二叉樹的性質(zhì)
1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有 2^(i - 1)個結(jié)點(diǎn).
2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是2^h - 1.
3. 對任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個數(shù)為n0 , 度為2的分支結(jié)點(diǎn)個數(shù)為n1 ,則有n0 ＝n2 ＋1.
4. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個結(jié)點(diǎn)的滿二叉樹的深度，h=log2(n + 1) (是log以2 為底，n+1為對數(shù))
5. 對于具有n個結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開始編號，則對 于序號為i的結(jié)點(diǎn)有：
1. 若i>0，i位置節(jié)點(diǎn)的雙親序號：(i-1)/2；i=0，i為根節(jié)點(diǎn)編號，無雙親節(jié)點(diǎn).
2.若2i+1<n, 左孩子序號；如果2i + 1 >=n 無左孩子
3. 若2i+2<n, 右孩子序號；如果2i + 1 >=n 無右孩子
解釋：二叉樹存儲下標(biāo)從0開始就會出現(xiàn)這種結(jié)果
2.4 二叉樹的存儲結(jié)構(gòu)
1. 順序存儲
順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空 間的浪費(fèi)。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲，關(guān)于堆我們后面的章節(jié)會專門講解。二叉樹順 序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。
2. 鏈?zhǔn)酱鎯?/h4>
二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是 鏈表中每個結(jié)點(diǎn)由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所 在的鏈結(jié)點(diǎn)的存儲地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中一般都是二叉鏈，后面課程 學(xué)到高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹等會用到三叉鏈。
三、實現(xiàn)完全二叉樹堆并實現(xiàn)堆排序
3.1 堆的概念和結(jié)構(gòu)
如果有一個關(guān)鍵碼的集合K = { ， ， ，…， }，把它的所有元素按完全二叉樹的順序存儲方式存儲 在一個一維數(shù)組中，并滿足： = 且 >= ) i = 0，1， 2…，則稱為小堆(或大堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。
堆的性質(zhì)： 堆中某個節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
堆總是一棵完全二叉樹。
3.2 實現(xiàn)堆的難點(diǎn)
向上調(diào)整算法和向下調(diào)整算法
由于堆是一種非線性存儲結(jié)構(gòu)，因此我們在執(zhí)行堆的刪除時會比較復(fù)雜，涉及到向下調(diào)整算法。
原先我們在棧和隊列那講中的挪動數(shù)據(jù)覆蓋根的位置的數(shù)據(jù)刪除會導(dǎo)致堆的結(jié)構(gòu)被破壞了，父子間的結(jié)構(gòu)全亂了。
向下調(diào)整算法的思路：
1、第一個數(shù)（根位置）和最后一個位置進(jìn)行交換。
2、刪除最后一個數(shù)據(jù)。
3、找出左右孩子中小的那個和父親比較，如果比父親小，交換，再從交換的孩子位置繼續(xù)往下調(diào)整。
過程如下圖所示：
向下調(diào)整算法
void* AdjustDown(HPDataType* a, size_t size, size_t root)
{
size_t parent = root;
size_t child = parent * 2 + 1;//默認(rèn)是左孩子
while (child < size)
{
//1、選出左右孩子中小的那個，而且保證不會越界訪問
if (child + 1 < size && a[child + 1] < a[child])
{
child++;//左孩子變?yōu)橛液⒆?
}
if (a[child]< a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;//繼續(xù)計算
child = parent * 2 + 1;//默認(rèn)還是計算左孩子
}
else
{
break;
}
}
}為了保持堆的結(jié)構(gòu)，我們還要引入向上調(diào)整算法，由于兩種算法原理差不多而且向上調(diào)整比較簡單易懂，我直接上代碼了。
void Adjustup(HPDataType* a, size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
//小堆a(bǔ)[child] <a[parent],大堆a(bǔ)[child] > a[parent]時交換
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);//因為是指針傳參，所以要&
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}3.3 小堆的實現(xiàn)
頭文件：
#pragma once
// 小堆
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
size_t size;
size_t capacity;
}HP;
void PrintTopk(int* a, int n, int k);
void HeapInit(HP* php);//堆的初始化
void HeapDestory(HP* php);//堆的銷毀
void Swap(HPDataType* pa, HPDataType* pb);//交換
void HeapPrint(HP* php);
void AdjustDown(HPDataType* a, size_t size, size_t root);//堆的向下調(diào)整算法
//插入x以后，依舊保持堆
void HeapPush(HP* php, HPDataType x);
void Adjustup(HPDataType* a, size_t child);//堆的向上調(diào)整算法
//刪除堆頂?shù)臄?shù)據(jù)，（最小/最?。?
void HeapPop(HP* php);
bool HeapEmpty(HP* php);
size_t HeapSize(HP* php);
HPDataType HeapTop(HP* php);源文件：
#include"Heap.h"
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
void HeapDestory(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
void Swap(HPDataType* pa, HPDataType* pb)
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
void HeapPrint(HP* php)
{
assert(php);
for (size_t i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
//涉及堆排序
void Adjustup(HPDataType* a, size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
//小堆a(bǔ)[child] <a[parent],大堆a(bǔ)[child] > a[parent]時交換
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);//因為是指針傳參，所以要&
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
size_t parent = root;
size_t child = parent * 2 + 1;//默認(rèn)是左孩子
while (child < size)
{
//1、選出左右孩子中小的那個，而且保證不會越界訪問
if (child + 1 < size && a[child + 1] < a[child])//建大堆時< 改 >
{
++child;//左孩子變?yōu)橛液⒆?
}
if (a[child] < a[parent])//建大堆時< 改 >
{
Swap(&a[child], &a[parent]);
parent = child;//繼續(xù)計算
child = parent * 2 + 1;//默認(rèn)還是計算左孩子
}
else
{
break;
}
}
}
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)//滿了，需要擴(kuò)容
{
size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
//翻譯：新定義一個無符號的newCapacity = 原來的capacity，如果原來的capacity = 0, 就賦值為4，4不夠就再*二倍
HPDataType* tmp = realloc(php->a, sizeof(HPDataType)* newCapacity);
if (tmp == NULL)
{
printf("reallpc failed\n");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
//尾插
php->a[php->size] = x;
++php->size;
//向上調(diào)整保持是一個小堆
Adjustup(php->a, php->size - 1);
}
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
--php->size;
AdjustDown(php->a, php->size, 0);
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
size_t HeapSize(HP* php)
{
return php->size;
}
HPDataType HeapTop(HP* php)
{
return php->a[0];
}3.4 堆的應(yīng)用-堆排序
堆排序即利用堆的思想來進(jìn)行排序，總共分為兩個步驟：
1. 建堆
升序：建大堆
降序：建小堆
2. 利用堆刪除思想來進(jìn)行排序 建堆和堆刪除中都用到了向下調(diào)整，因此掌握了向下調(diào)整，就可以完成堆排序。
代碼示例：
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
size_t parent = root;
size_t child = parent * 2 + 1;//默認(rèn)是左孩子
while (child < size)
{
//1、選出左右孩子中小的那個，而且保證不會越界訪問
if (child + 1 < size && a[child + 1] <a[child])//建大堆時< 改 >
{
++child;//左孩子變?yōu)橛液⒆?
}
if (a[child] < a[parent])//建大堆時< 改 >
{
Swap(&a[child], &a[parent]);
parent = child;//繼續(xù)計算
child = parent * 2 + 1;//默認(rèn)還是計算左孩子
}
else
{
break;
}
}
}
void HeapSort2(int* a, int n)
{
//向上調(diào)整--建堆
//for (int i = 1; i < n; ++i)
//{
// AdjustUp(a, i);
//}
//向下調(diào)整--建堆O（N）
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);//為什么向下調(diào)整要多傳一個參數(shù)，因為當(dāng)child>=size 時說明已經(jīng)到了邊界
}
size_t end = n - 1;//n - 1是最后一個數(shù)據(jù)的下標(biāo)
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
//次大的數(shù)到了倒數(shù)第二個位置
--end;
}
}
int main()
{
// TestHeap();
int a[] = { 4 , 2, 7, 8, 5, 1, 0, 6 };
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
四.Top-k問題
TOP-K問題：即求數(shù)據(jù)結(jié)合中前K個最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。
比如：專業(yè)前10名、世界500強(qiáng)、富豪榜、游戲中前100的活躍玩家等。
對于Top-K問題，能想到的最簡單直接的方式就是排序，但是：如果數(shù)據(jù)量非常大，排序就不太可取了(可能 數(shù)據(jù)都不能一下子全部加載到內(nèi)存中)。
最佳的方式就是用堆來解決，基本思路如下：
1. 用數(shù)據(jù)集合中前K個元素來建堆 前k個最大的元素，則建小堆 前k個最小的元素，則建大堆 2. 用剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素。
將剩余N-K個元素依次與堆頂元素比完之后，堆中剩余的K個元素就是所求的前K個最小或者最大的元素。
因為N非常大，k非常小，所以復(fù)雜度相當(dāng)于0（N）
設(shè)置10個比100萬大的數(shù)，然后讓電腦隨機(jī)生成數(shù)，找出大于100萬的10個數(shù)。
void PrintTopk(int* a, int n, int k)
{
//1、建堆-- 用a中前k個元素建堆
int* kminHeap = (int*)malloc(sizeof(int)* k);
assert(kminHeap);
//2、將剩余n-k元素依次與堆頂元素交換，不滿則替換
for (int i = 0; i < k; i++)
{
kminHeap[i] = a[i];//將前k個數(shù)給給它
}
//第k-1個是最后一位數(shù)的下標(biāo)，(k - 1 -1) / 2是倒數(shù)第一個非葉子結(jié)點(diǎn)
//建小堆
for (int j = (k - 1 - 1) / 2; j >= 0; --j)
{
AdjustDown(kminHeap, k, j);
}
//2、將剩余n - k元素依次與堆頂元素交換，不滿則替換
for (int i = k; i < n; ++i)
{
if (a[i] > kminHeap[0])
{
kminHeap[0] = a[i];
AdjustDown(kminHeap, k, 0);//從根這個點(diǎn)向下調(diào)
}
}
for (int j = 0; j < k; j++)
{
printf("%d ", kminHeap[j]);
}
printf("\n");
free(kminHeap);
}
void TestTopk()
{
int n = 10000;
int* a = (int*)malloc(sizeof(int)* n);
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
a[i] = rand() % 1000000;
}
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[115] = 1000000 + 5;
a[2305] = 1000000 + 6;
a[99] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[0] = 1000000 + 1000;
PrintTopk(a, n, 10);
}
int main()
{
TestTopk();
return 0;
}總結(jié)
本文近7500字，主要從樹以及二叉樹的概念和結(jié)構(gòu)展開詳講，再詳細(xì)介紹了堆（特殊的二叉樹）這種數(shù)據(jù)結(jié)構(gòu)的概念、原理以及實現(xiàn)，還有堆的重要應(yīng)用：堆排序以及TOPK問題等，希望大家讀后能夠有所收獲。
到此這篇關(guān)于C語言近萬字為你講透樹與二叉樹的文章就介紹到這了,更多相關(guān)C語言樹與二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
下面小編就為大家?guī)硪黄猚++圖像處理:24位真彩圖顏色變換實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
C語言修煉之路數(shù)據(jù)類型悟正法?解析存儲定風(fēng)魔上篇
使用編程語言進(jìn)行編程時，需要用到各種變量來存儲各種信息。變量保留的是它所存儲的值的內(nèi)存位置。這意味著，當(dāng)您創(chuàng)建一個變量時，就會在內(nèi)存中保留一些空間。您可能需要存儲各種數(shù)據(jù)類型的信息，操作系統(tǒng)會根據(jù)變量的數(shù)據(jù)類型，來分配內(nèi)存和決定在保留內(nèi)存中存儲什么2022-02-02
C語言函數(shù)聲明以及函數(shù)原型超詳細(xì)講解示例
這篇文章主要介紹了C語言函數(shù)聲明以及函數(shù)原型超詳細(xì)講解，C語言代碼由上到下依次執(zhí)行，原則上函數(shù)定義要出現(xiàn)在函數(shù)調(diào)用之前，否則就會報錯。但在實際開發(fā)中，經(jīng)常會在函數(shù)定義之前使用它們，這個時候就需要提前聲明2023-02-02
本篇文章是對結(jié)構(gòu)體的定義以及使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
掃雷游戲是在一個指定的二維空間里，隨機(jī)布置雷，把不是雷的位置都找出來，在你點(diǎn)一個位置的時候它會顯示它周圍全部雷的個數(shù)，根據(jù)這個線索去找 ，會更容易贏。本文將用C語言實現(xiàn)這一經(jīng)典游戲，感興趣的可以嘗試一下2022-11-11
C語言中的時間函數(shù)clock()和time()你都了解嗎
這篇文章主要為大家詳細(xì)介紹了C語言中的時間函數(shù)clock()和time()，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
朋友們好,這篇播客我們繼續(xù)C++的初階學(xué)習(xí)，現(xiàn)在對我們對C++的友元，內(nèi)部類知識點(diǎn)做出總結(jié)，整理出來一篇博客供我們一起復(fù)習(xí)和學(xué)習(xí),如果文章中有理解不當(dāng)?shù)牡胤?還希望朋友們在評論區(qū)指出,我們相互學(xué)習(xí),共同進(jìn)步2022-06-06
本文主要介紹了QT6中添加串口模塊SerialPort的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-09-09
C語言中求字符串長度的函數(shù)的幾種實現(xiàn)方法
這篇文章主要介紹了C語言中求字符串長度的函數(shù)的幾種實現(xiàn)方法,需要的朋友可以參考下2018-08-08
本文主要介紹了qt中sokect斷開的幾種情況,文中介紹了很多情況,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-12-12