【樹的概念及其堆的實現】

樹的概念及其堆的實現

  • 1.樹的概念
  • 2.樹的相關概念
  • 3.二叉樹的概念
  • 4. 滿二叉樹和完全二叉樹
  • 5.二叉樹的存儲結構
  • 6.二叉樹順序結構的實現的
  • 7.堆的結構及其實現

1.樹的概念

??樹是一種非線性的數據結構,它是由n(n>=0)個有限結點組成一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。
有一個特殊的結點,稱為根結點,根節點沒有前驅結點除根節點外,其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm,其中每一個集合Ti(1<= i <= m)又是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅,可以有0個或多個后繼,因此,樹是遞歸定義的。
注意:樹形結構中,子樹之間不能有交集,否則就不是樹形結構.

Alt

2.樹的相關概念

Alt
??*節點的度:一個節點含有子樹的個數稱為該節點的度。如上圖:A的為6

??*葉節點或終端節點:度為0的節點稱為葉節點; 如上圖:B、C、H、I…等節點為葉節點

??* 非終端節點或分支節點:度不為0的節點; 如上圖:D、E、F、G…等節點為分支節點

??*孩子節點或子節點:一個節點含有的子樹的根節點稱為該節點的子節點; 如上圖:B是A的孩子節點

??* 兄弟節點:具有相同父節點的節點互稱為兄弟節點; 如上圖:B、C是兄弟節點

??* 樹的度:一棵樹中,最大的節點的度稱為樹的度; 如上圖:樹的度為6

??* 節點的層次:從根開始定義起,根為第1層,根的子節點為第2層,以此類推;

??* 樹的高度或深度:樹中節點的最大層次; 如上圖:樹的高度為4

??* 堂兄弟節點:雙親在同一層的節點互為堂兄弟;如上圖:H、I互為兄弟節點

?? * 節點的祖先:從根到該節點所經分支上的所有節點;如上圖:A是所有節點的祖先

?? * 子孫:以某節點為根的子樹中任一節點都稱為該節點的子孫。如上圖:所有節點都是A的子孫

3.二叉樹的概念

?一棵二叉樹是結點的一個有限集合,該集合:
?1.或者為空
?2. 由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成.

Alt
從上圖可以看出:
1. 二叉樹不存在度大于2的結點
2. 二叉樹的子樹有左右之分,次序不能顛倒,因此二叉樹是有序樹.

?注意:對于任意的二叉樹都是由以下幾種情況復合而成的:
Alt

4. 滿二叉樹和完全二叉樹

?1. 滿二叉樹:一個二叉樹,如果每一個層的結點數都達到最大值,則這個二叉樹就是滿二叉樹。也就是說,如果一個二叉樹的層數為K,且結點總數是2^k-1,則它就是滿二叉樹。
?2.完全二叉樹:完全二叉樹是效率很高的數據結構,完全二叉樹是由滿二叉而引出來的。對于深度為K的,有n個結點的二叉樹,當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的的結點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。

Alt

5.二叉樹的存儲結構

1. 順序存儲
?順序結構存儲就是使用數組來存儲,一般使用數組只適合表示完全二叉樹,因為不是完全二叉樹會有空間的浪費。而現實中使用中只有堆才會使用數組來存儲。二叉樹順序存儲在物理上是一個數組,在邏輯上是一顆二叉樹。

Alt

2. 鏈式存儲
?二叉樹的鏈式存儲結構是指,用鏈表來表示一棵二叉樹,即用鏈來指示元素的邏輯關系。 通常的方法是鏈表中每個結點由三個域組成,數據域和左右指針域,左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址 。鏈式結構又分為二叉鏈和三叉鏈,當前我們學習中一般都是二叉鏈。

Alt

6.二叉樹順序結構的實現的

?普通的二叉樹是不適合用數組來存儲的,因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。現實中我們通常把堆(一種二叉樹)使用順序結構的數組來存儲,需要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩回事,一個是數據結構,一個是操作系統中管理內存的一塊區域分段。

7.堆的結構及其實現

Alt
Alt

?堆是一個完全二叉樹,用數據來實現,結構和實現的接口如下:

#define HeapDataType int
typedef struct Heap {
HeapDataType* a;
int size;
int capacity;
}Heap;
void HeapInit(Heap* php);
void HeapDestory(Heap* php);
void HeapPush(Heap* php, HeapDataType x);
HeapDataType HeapTop(Heap* php);
void HeapPop(Heap* php);
bool HeapEmpty(Heap* php);



堆初始化和堆銷毀接口如下

void HeapInit(Heap* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}void HeapDestory(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}

?HeapPush接口的實現,先插入數據,再用向上調整算法,調成堆,以調成小堆為列,介紹向上調整算法。
Alt
??以滿二叉樹,插入10為例,進行調整,10是孩子,先找到父親,由于是滿二叉樹,孩子與父親的關系為:
?LeftChild = (Parent2)+1;
?RightChild = (Parent
2)+2;
?Parent = (child - 1)/2;

然后,如果孩子比父親小,則交換,孩子比父親大,則成立。這兒再說一下循環怎么寫,寫循環結構就兩件事,1.寫循環體 2.寫循環條件,一定要先寫循環體,根據循環體寫循環條件,例如上面向上調整算法.
?循環體是什么?
?已經知道最后一個孩子的位置,則通過孩子算出父親位置,然后孩子與父親的大小比較,進行交換。若成立,則退出循環。盡管做這樣一件事情,那什么時候結束,孩子走到頭,父親沒有了,就結束,很自然就找到循環條件。

?具體代碼如下:

void Swap(HeapDataType* px, HeapDataType* py)
{HeapDataType tmp = *px;*px = *py;*py = tmp;
}void AdjustUp(HeapDataType* a, int child)
{int parent = (child - 1) / 2;while (child>0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void HeapPush(Heap* php, HeapDataType x)
{assert(php);if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);if (tmp == NULL){perror("realloc fail!");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

?寫接口獲得堆頂數據,堆的刪除。
?堆的刪除,首先堆頭和堆位進行交換,然后向下調整,調整成堆。

Alt

?首先,把10和28交換,交換之后,把堆頂元素10刪除,把在0位置的28這個元素,向下調整成堆,具體就是找孩子中兩個較小的一個跟父親比較,進行交換,父親走到頭,循環結束,這是孩子已經越界,用孩子來寫循環條件。
?代碼如下。

void AdjustDown(HeapDataType* a, int parent, int n)
{int child = (parent * 2) + 1;if (a[child] > a[child + 1] && child+1<n){child += 1;}while (child<n){if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;if (a[child] > a[child + 1] && child + 1 < n){child += 1;}}else{break;}}
}void HeapPop(Heap* php)
{assert(php);assert(php->a);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, 0, php->size);
}

?判空很簡單

bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}

?完結!

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/86269.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/86269.shtml
英文地址,請注明出處:http://en.pswp.cn/web/86269.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

鴻蒙系統(HarmonyOS)經典紅色風格登錄頁布局

預覽 簡介 基于鴻蒙系統&#xff08;HarmonyOS&#xff09;開發的現代化登錄界面&#xff0c;采用了科技感十足的紅色主題設計。該界面結合了流暢的動畫效果、精心設計的視覺元素和人性化的交互體驗&#xff0c;為用戶提供了一個安全、美觀且易用的登錄入口。 &#x1f3a8; …

C++虛函數多態

class C{ public:void x1(){};void x2(){};};C c; cout << sizeof(c) <<"\n";1字節 class D{ public:void x1(){};void x2(){};virtual void x3(){};//void *vptr看不見的虛函數表指針 }; D d; cout << sizeof(d) <<"\n";8字節類A…

新編輯器編寫指南--給自己的備忘

歡迎使用Markdown編輯器 你好&#xff01; 這是你第一次使用 Markdown編輯器 所展示的歡迎頁。如果你想學習如何使用Markdown編輯器, 可以仔細閱讀這篇文章&#xff0c;了解一下Markdown的基本語法知識。 新的改變 我們對Markdown編輯器進行了一些功能拓展與語法支持&#x…

目標檢測neck算法之MPCA和FSA的源碼實現

目標檢測neck算法之MPCA和FSA的源碼實現 使用BIBM2024 Spatial-Frequency Dual Domain Attention Network For Medical Image Segmentation的Frequency-Spatial Attention和Multi-scale Progressive Channel Attention改進neck. 接下來&#xff0c;我將講解它的源碼操作的實現…

MyBatis-Plus的3.5.7和PageHelper的那個版本對應

MyBatis-Plus的3.5.7和PageHelper的那個版本對應 根據你的知識庫中提到的信息&#xff1a; MyBatis-Plus 3.5.7 使用的是 JSqlParser 4.6 版本。PageHelper 若使用了不同版本的 JSqlParser&#xff08;如 4.7&#xff09;&#xff0c;會導致沖突。 ? 推薦對應關系 為了保證…

Apifox 6 月產品更新|支持 AI 能力、交互優化、在線文檔新增 SEO 設置、gRPC 項目支持前/后置操作

在 2025 年的 API 開發領域&#xff0c;Apifox 作為一款集 API 設計、調試、Mock 和測試于一體的協作平臺&#xff0c;已成為開發者的“得力助手”。然而&#xff0c;隨著業務需求的不斷增長&#xff0c;開發者對工具的效率和功能提出了更高的要求。6 月份&#xff0c;Apifox 推…

Acrobat JavaScript 從瀏覽器到 PDF 環境的轉換

目錄 什么是 JavaScript?JavaScript 核心語言與 Acrobat 特定 API學習 JavaScript 核心語言的挑戰瀏覽器與 Acrobat JavaScript 的關鍵差異在 Acrobat 中運行 JavaScript 代碼替代瀏覽器特定函數的方法后續學習建議什么是 JavaScript? JavaScript 最初于 1995 年作為 Netsca…

OpenCV CUDA模塊設備層-----指數運算函數exp()

操作系統&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 編程語言&#xff1a;C11 算法描述 OpenCV 的 CUDA 設備端數學函數 中的一個內聯函數&#xff0c;用于在 GPU 上對 uchar1 類型&#xff08;單通道圖像像素&#xff09;執行指數運算…

C++面向對象5——C++關鍵字、構造函數與拷貝構造函數

this關鍵字 C關鍵字this的深度解析 1. this指針的本質 在C中&#xff0c;this是一個特殊的隱式指針&#xff0c;它存在于每個非靜態成員函數內部&#xff0c;指向調用該函數的當前對象。其類型為&#xff1a; 對于非const成員函數&#xff1a;ClassName* const&#xff08;…

人工智能專業:探索未來的智慧前沿

親戚家的小孩剛高考完&#xff0c;問我人工智能專業是學什么、做什么的。趁機就寫一篇吧&#xff01; 人工智能專業&#xff1a;探索未來的智慧前沿 人工智能&#xff08;Artificial Intelligence&#xff0c;簡稱AI&#xff09;無疑是當今最熱門、最具顛覆性的技術之一。它正…

618風控戰升級,瑞數信息“動態安全+AI”利劍出鞘

每年的618電商促銷季&#xff0c;都是各大電商平臺和商家的兵家必爭之地。數以億計的消費者涌入線上平臺&#xff0c;期待已久的優惠券、秒殺商品如潮水般涌現&#xff0c;海量交易在瞬間達成&#xff0c;無疑是一場商業狂歡。 然而&#xff0c;在這場狂歡背后&#xff0c;自動…

神經網絡的架構

神經網絡中的基本術語 以上圖為例&#xff0c;相關的術語描述如下&#xff1a; 最左邊的稱為輸?層&#xff0c;其中的神經元稱為輸?神經元&#xff1b;最右邊的&#xff0c;即輸出層包含有輸出神經元&#xff1b;本例中的輸出神經元只有一個&#xff1b;中間層&#xff0c;既…

安全生產監測預警系統:構筑智能化的安全防線

安全生產監測預警系統是工業安全管理的核心工具&#xff0c;它利用物聯網、大數據、人工智能等技術&#xff0c;實現對生產環境、設備運行和人員行為的全方位監測&#xff0c;確保風險早發現、早預警、早處置。其核心功能涵蓋實時監測、智能預警、應急處置、數據分析與優化等多…

Java練習題精選6-10

Java練習題精選6-10 一、第六題二、第七題第八題第九題第十題 一、第六題 如何將兩個變量的值進行交換&#xff1f;假設變量a1&#xff0c;b2。 public class Main {public static void main(String[] args) {int a 1;int b 2;int tmp;System.out.println("交換前a&qu…

【GESP】C++四級考試大綱知識點梳理, (2) 結構體和二維數組

GESP C四級官方考試大綱中&#xff0c;共有11條考點&#xff0c;本文針對第2條考點進行分析介紹。 &#xff08;2&#xff09;掌握 C結構體、二維及多維數組的基本概念及使用 四級其他考點回顧&#xff1a; 【GESP】C四級考試大綱知識點梳理, (1) 指針 全文詳見&#xff1a;【G…

自動化測試--App自動化之項目實戰腳本編寫及封裝流程

1.App測試范圍 app自動化測試主要核心測試手機程序 測試方面&#xff1a; 功能測試 安裝卸載測試 升級測試 兼容性測試 網絡切換&#xff0c;中斷測試 橫豎屏切換 健壯性 2.測試環境的搭建 需要配置的環境 java jdk Java的環境 Android sdk 安卓環境 python環境…

【Unity】什么是前向渲染、延遲渲染、單通道渲染、多通道渲染?

好的&#xff0c;我們來深入剖析這些核心渲染概念&#xff0c;理解它們的原理、優缺點以及在Unity&#xff08;特別是URP&#xff09;中的應用。 核心概念&#xff1a;渲染路徑 (Rendering Path) 渲染路徑決定了光照和著色在場景中是如何計算和應用的。它定義了物體被繪制到屏…

OpenCV CUDA模塊設備層-----GPU上執行線程安全的 “原子取最大值” 操作函數

操作系統&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 編程語言&#xff1a;C11 算法描述 這是一個 OpenCV 的 CUDA 模塊&#xff08;cv::cudev&#xff09; 中封裝的原子操作函數&#xff0c;用于在 GPU 上執行線程安全的 “原子取最大…

【nRF52832】【環境搭建 1】【ubuntu下搭建nRF52832開發環境】

本文講述如何在 ubuntu 22.04 下開發 nRF52832. host 環境說明: $ uname -a Linux leo 6.8.0-60-generic #63~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Tue Apr 22 19:00:15 UTC 2 x86_64 x86_64 x86_64 GNU/Linux1. 安裝軟件 sudo apt install gcc-arm-none-eabisudo apt-get i…

【Nginx】403 Forbidden錯誤

當 Nginx 代理配置出現 403 Forbidden 錯誤時&#xff0c;通常是由于權限或配置問題導致。以下是常見原因和解決方案&#xff1a; 常見原因及解決方法 1. 后端服務器拒絕訪問 原因&#xff1a;后端 HTTPS 服務配置了 IP 白名單或訪問控制解決&#xff1a; 檢查后端服務器&…