C語言近萬字為你講透樹與二叉樹
一、樹概念及結(jié)構(gòu)
1.1 樹的概念
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu),它是由n(n>=0)個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因 為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。


·有一個特殊的結(jié)點,稱為根結(jié)點,根節(jié)點沒有前驅(qū)結(jié)點
·除根節(jié)點外,其余結(jié)點被分成M(M>0)個互不相交的集合T1、T2、……、Tm,其中每一個集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。
·每棵子樹的根結(jié)點有且只有一個前驅(qū),可以有0個或多個后繼 因此,樹是遞歸定義的。
注意:樹形結(jié)構(gòu)中,子樹之間不能有交集,否則就不是樹形結(jié)構(gòu)

1.2 樹的相關(guān)概念

節(jié)點的度:一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度; 如上圖:A的為6
葉節(jié)點或終端節(jié)點:度為0的節(jié)點稱為葉節(jié)點; 如上圖:B、C、H、I...等節(jié)點為葉節(jié)點
非終端節(jié)點或分支節(jié)點:度不為0的節(jié)點; 如上圖:D、E、F、G...等節(jié)點為分支節(jié)點
雙親節(jié)點或父節(jié)點:若一個節(jié)點含有子節(jié)點,則這個節(jié)點稱為其子節(jié)點的父節(jié)點; 如上圖:A是B的父節(jié)點
孩子節(jié)點或子節(jié)點:一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點; 如上圖:B是A的孩子節(jié)點
兄弟節(jié)點:具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點; 如上圖:B、C是兄弟節(jié)點
樹的度:一棵樹中,最大的節(jié)點的度稱為樹的度; 如上圖:樹的度為6
節(jié)點的層次:從根開始定義起,根為第1層,根的子節(jié)點為第2層,以此類推;
樹的高度或深度:樹中節(jié)點的最大層次; 如上圖:樹的高度為4
堂兄弟節(jié)點:雙親在同一層的節(jié)點互為堂兄弟;如上圖:H、I互為兄弟節(jié)點
節(jié)點的祖先:從根到該節(jié)點所經(jīng)分支上的所有節(jié)點;如上圖:A是所有節(jié)點的祖先
子孫:以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。如上圖:所有節(jié)點都是A的子孫
森林:由m(m>0)棵互不相交的樹的集合稱為森林;
1.3 樹的表示
樹結(jié)構(gòu)相對線性表就比較復(fù)雜了,要存儲表示起來就比較麻煩了,既然保存值域,也要保存結(jié)點和結(jié)點之間 的關(guān)系,實際中樹有很多種表示方式如:雙親表示法,孩子表示法、孩子雙親表示法以及孩子兄弟表示法 等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。
如下圖所示:

二、二叉樹概念及結(jié)構(gòu)
2.1 概念
什么是二叉樹?簡言之一棵二叉樹是結(jié)點的一個有限集合,該集合:
1. 或者為空
2. 由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉樹組成
如下圖示

從上圖我們可以看出二叉樹的兩個特點
1. 二叉樹不存在度大于2的結(jié)點
2. 二叉樹的子樹有左右之分,次序不能顛倒,因此二叉樹是有序樹
注意:對于任意的二叉樹都是由以下幾種情況復(fù)合而成的:
2.2 特殊的二叉樹:
1. 滿二叉樹:一個二叉樹,如果每一個層的結(jié)點數(shù)都達(dá)到最大值,則這個二叉樹就是滿二叉樹。也就是 說,如果一個二叉樹的層數(shù)為K,且結(jié)點總數(shù)是 ,則它就是滿二叉樹。
2. 完全二叉樹:完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu),完全二叉樹是由滿二叉樹而引出來的。對于深度為K 的,有n個結(jié)點的二叉樹,當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對 應(yīng)時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
2.3 二叉樹的性質(zhì)
1. 若規(guī)定根節(jié)點的層數(shù)為1,則一棵非空二叉樹的第i層上最多有 2^(i - 1)個結(jié)點.
2. 若規(guī)定根節(jié)點的層數(shù)為1,則深度為h的二叉樹的最大結(jié)點數(shù)是2^h - 1.
3. 對任何一棵二叉樹, 如果度為0其葉結(jié)點個數(shù)為n0 , 度為2的分支結(jié)點個數(shù)為n1 ,則有n0 =n2 +1.
4. 若規(guī)定根節(jié)點的層數(shù)為1,具有n個結(jié)點的滿二叉樹的深度,h=log2(n + 1) (是log以2 為底,n+1為對數(shù))
5. 對于具有n個結(jié)點的完全二叉樹,如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點從0開始編號,則對 于序號為i的結(jié)點有:
1. 若i>0,i位置節(jié)點的雙親序號:(i-1)/2;i=0,i為根節(jié)點編號,無雙親節(jié)點.
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ù)組只適合表示完全二叉樹,因為不是完全二叉樹會有空 間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲,關(guān)于堆我們后面的章節(jié)會專門講解。二叉樹順 序存儲在物理上是一個數(shù)組,在邏輯上是一顆二叉樹。

2. 鏈?zhǔn)酱鎯?/h4>
二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指,用鏈表來表示一棵二叉樹,即用鏈來指示元素的邏輯關(guān)系。 通常的方法是 鏈表中每個結(jié)點由三個域組成,數(shù)據(jù)域和左右指針域,左右指針分別用來給出該結(jié)點左孩子和右孩子所 在的鏈結(jié)點的存儲地址 。鏈?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é)點最大的堆叫做最大堆或大根堆,根節(jié)點最小的堆叫做最小堆或小根堆。
堆的性質(zhì): 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值;
堆總是一棵完全二叉樹。

3.2 實現(xià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[child] <a[parent],大堆a[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[child] <a[parent],大堆a[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)//滿了,需要擴容
{
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強、富豪榜、游戲中前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ù),然后讓電腦隨機生成數(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é)點
//建小堆
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à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)文章
C++?數(shù)據(jù)結(jié)構(gòu)超詳細(xì)講解單鏈表
這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)之單鏈表,鏈表是由一個個結(jié)點鏈結(jié)成的。結(jié)點包括數(shù)據(jù)域和指針域兩部分,數(shù)據(jù)域用來存儲數(shù)據(jù)元素的信息,指針域用來存儲下一個結(jié)點的地址,更詳細(xì)內(nèi)容請需要的小伙伴參考下面文章內(nèi)容2022-03-03
C語言實現(xiàn)五子棋對戰(zhàn)系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)五子棋對戰(zhàn)系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-05-05

