《嵌入式數據結構筆記（六）：二叉樹》

1. ??樹數據結構的基本定義和屬性??

樹是一種重要的非線性數據結構，用于表示層次關系。

  • ??基本定義??：樹是由 n（n ≥ 0）個結點組成的有限集合。當 n = 0 時，稱為空樹；當 n > 0 時，樹必須滿足兩個條件：
    • 有且僅有一個特定的根結點（root node）。
    • 當 n > 1 時，其余結點可劃分為 m（m > 0）個互不相交的子集 T1, T2, ..., Tm，每個子集本身又是一棵樹，稱為子樹（subtree）。
  • ??結點屬性??：
    • ??結點的度（degree）??：指一個結點擁有的子樹個數。例如，一個結點有 3 個子樹，則其度為 3。
    • ??葉結點（leaf node）??：度為 0 的結點，即沒有子樹的結點。
    • ??分支結點（branch node）??：度不為 0 的結點，即至少有一個子樹的結點。
  • ??樹的整體屬性??：
    • ??樹的度數??：指樹中所有結點的度的最大值。例如，如果所有結點度的最大值為 3，則樹的度數為 3。
    • ??樹的深度或高度??：從根結點開始計算，根所在層為第 1 層，其子結點為第 2 層，依此類推。深度反映了樹的層級結構。
  • ??樹的性質強調??：樹的結構強調“互不相交”的子集，確保每個結點只屬于一個父結點，避免循環或重復。

2. ??樹的存儲結構??

  • ??順序結構??：將樹結點存儲在連續的內存位置（如數組），通過索引表示父子關系。優點是訪問快速，但插入/刪除操作可能低效。
  • ??鏈式結構??：使用指針或引用來鏈接結點（如鏈表），每個結點包含數據域和指向子樹的指針。優點是靈活，適用于動態樹結構。

3. ??二叉樹的定義和類型??

二叉樹是樹的特例，具有嚴格的子樹順序規則。

  • ??基本定義??：二叉樹是 n 個結點的有限集合，它要么為空樹，要么由一個根結點和兩棵互不相交的左子樹與右子樹組成。關鍵特點包括：
    • 每個結點最多有兩個子樹（左子樹和右子樹）。
    • 左子樹和右子樹有固定順序，不能顛倒（例如，交換左右子樹會改變樹結構）。
    • 如果結點只有一個子樹，必須明確指定是左子樹或右子樹。
  • ??特殊二叉樹類型??：
    • ??斜樹（skewed tree）??：所有結點都只有左子樹（左斜樹）或只有右子樹（右斜樹）。結構類似線性鏈表。
    • ??滿二叉樹（full binary tree）??：所有分支結點都有左右子樹，且所有葉結點都在同一層上。結點總數達到最大值（2^k - 1，k 為深度）。
    • ??完全二叉樹（complete binary tree）??：對樹按層序編號（根為 1），每個結點的編號與同深度的滿二叉樹中對應結點位置相同。不完全二叉樹在編號上會有空缺。

4. ??二叉樹的數學特性和遍歷方法??

  • ??數學特性??：
    • 第 i 層（i ≥ 1）最多有 2^(i-1) 個結點。
    • 深度為 k 的二叉樹（k ≥ 1）最多有 2^k - 1 個結點。
    • 關鍵公式：對于任意二叉樹，葉子結點數（n0）和度為 2 的結點數（n2）滿足 n0 = n2 + 1。
    • 對于有 n 個結點的完全二叉樹，深度為 (log?(n)) + 1。
  • ??遍歷方法??：遍歷是訪問樹中所有結點的過程，三種主要順序：
    • ??前序遍歷（preorder traversal）??：順序為“根-左-右”。先訪問根結點，然后遞歸訪問左子樹，最后右子樹。
    • ??中序遍歷（inorder traversal）??：順序為“左-根-右”。從根開始但不先訪問根；先遞歸訪問左子樹，再訪問根，最后右子樹。常用于二叉搜索樹（BST）。
    • ??后序遍歷（postorder traversal）??：順序為“左-右-根”。從根開始但不先訪問根；先遞歸訪問左子樹，然后右子樹，最后根。
    • ??層序遍歷（level order traversal）??：按層從上到下、從左到右訪問結點。
      遍歷方法強調遞歸實現，適用于樹結構的遞歸特性。

5. ??GDB調試工具的常規使用步驟??

GDB（GNU Debugger）的實用指南，用于調試C/C++程序，特別是處理段錯誤和一般調試：

  • ??調試段錯誤（segmentation fault）??：
    1. 編譯時添加調試選項：使用 gcc -g *.c 生成帶調試信息的可執行文件。
    2. 啟動GDB：運行 gdb a.out。
    3. 運行程序：在GDB中輸入 r（run）命令執行程序。
    4. 重現錯誤：讓程序運行到崩潰點。
    5. 定位錯誤：輸入 where 或 bt 命令顯示調用棧，找出段錯誤發生的具體位置（如文件和行號）。
  • ??一般調試流程??：
    1. 設置斷點：使用 b 命令（break），例如 b fun.c:36 在文件 fun.c 的第 36 行設置斷點，或 b myfun 在函數 myfun 入口處設斷點。
    2. 運行程序：輸入 r 開始執行，程序會在斷點處暫停。
    3. 單步執行：
      • n（next）：步過，執行下一行代碼（如果遇到函數，不進入函數內部）。
      • s（step）：步入，執行下一行代碼（如果遇到函數，進入函數內部）。
    4. 查看變量：使用 p（print）命令，例如 p a 顯示變量 a 的值，或 p *ptr 顯示指針 ptr 指向的數據。display a 可持續顯示變量變化。
    5. 控制執行：
      • c（continue）：從當前斷點繼續運行，直到下一個斷點或程序結束。
      • return：強制從當前函數返回調用處。
    6. 輔助命令：set print elements 300 設置字符串顯示長度（避免截斷）。
  • ??關鍵優勢??：GDB 能通過 where 命令追蹤函數調用棧，幫助快速定位內存錯誤或邏輯問題。

6. ??希爾排序算法??

  • ??算法原理??：希爾排序通過分組比較和插入來優化排序。它使用一個“間隙”（gap）序列，初始 gap 為數組長度的一半，逐步減小 gap 至 1（此時等價于插入排序）。核心是減少逆序對，提升效率。
  • ??代碼實現??：
    void shell_sort(int a[], int len) 
{for (int gap = len / 2; gap > 0; gap /= 2) {  // gap 從 len/2 開始，每次減半for (int i = gap; i < len; ++i) // 從 gap 位置開始遍歷{         int temp = a[i];                      // 保存當前元素int j = i;while (j >= gap && a[j - gap] > temp) { // 比較并移動元素a[j] = a[j - gap];                // 將較大元素后移j -= gap;                         // 跳轉到前一個 gap 位置}a[j] = temp;                          // 插入 temp 到正確位置}}
}
  • ??關鍵步驟??：
    1. ??外層循環??：控制 gap 值（gap = len/2, gap/2, ..., 1）。
    2. ??內層循環??：對每個 gap 組進行插入排序。從索引 gap 開始，將元素與同組前驅比較，移動元素以保持有序。
    3. ??效率??：希爾排序平均時間復雜度為 O(n log n)，優于簡單插入排序 O(n2)，適用于中等規模數據。
  • ??應用場景??：常用于嵌入式系統或內存受限環境，因代碼簡潔高效。

代碼實現：

1.創建數

2.三種遍歷方法

3.以隊列形式遍歷

4..摧毀樹

頭文件

#ifndef _TREE_H_
#define TREE_H_typedef char DATATYPE;
typedef struct BiTNode /* 結點結構 */
{DATATYPE data;                   /* 結點數據 */struct BiTNode *lchild, *rchild; /* 左右孩子指針 */
} BiTNode;//定義隊列節點結構
typedef struct QueueNode 
{// 指向樹節點的指針BiTNode *treeNode;// 指向下一個隊列節點struct QueueNode *next;
} QueueNode;//定義隊列結構
typedef struct Queue 
{// 隊列頭部QueueNode *head;// 隊列尾部QueueNode *tail;
} Queue;extern void CreateTree(BiTNode **root);
extern void PreOrderTraverse(BiTNode *root);
extern void InOrderTraverse(BiTNode *root);
extern void PostOrderTraverse(BiTNode *root);
extern void DestroyTree(BiTNode *root); extern int isQueueEmpty(Queue *queue);
extern void enqueue(Queue *queue, BiTNode *treeNode);
extern BiTNode* dequeue(Queue *queue);
extern void each_of_tree(BiTNode *root);
extern void initQueue(Queue *queue);
#endif

函數

#include <stdio.h>
#include "tree.h"
#include <stdlib.h>char data[] = "Abd#g###ce#h##fi###";
int ind = 0;void CreateTree(BiTNode **root)
{char c = data[ind++];if ('#' == c){*root = NULL;return;}else{*root = malloc(sizeof(BiTNode));if (NULL == *root)               /*判斷申請是否成功*/{printf("malloc error\n");*root = NULL;return;}  (*root)->data = c;CreateTree(&(*root)->lchild);    /*左*/CreateTree(&(*root)->rchild);    /*右*/}return;
}
//根左右（前序）
void PreOrderTraverse(BiTNode *root)
{if (NULL == root){return;}else{printf("%c", root->data);PreOrderTraverse(root->lchild);PreOrderTraverse(root->rchild);}return;
}
//左根右(中序)
void InOrderTraverse(BiTNode *root)
{if (NULL == root){return;}InOrderTraverse(root->lchild);printf("%c", root->data);InOrderTraverse(root->rchild);return;
}
//左右根（后序）
void PostOrderTraverse(BiTNode *root)
{if (NULL == root){return;}PostOrderTraverse(root->lchild);PostOrderTraverse(root->rchild);printf("%c", root->data);return;
}
void DestroyTree(BiTNode *root)
{if (NULL == root){return;}DestroyTree(root->lchild);DestroyTree(root->rchild);free(root);root = NULL;return;
}// 初始化隊列
void initQueue(Queue *queue) 
{queue->head = queue->tail = NULL;
}//  判斷隊列是否為空
int isQueueEmpty(Queue *queue) 
{return queue->head == NULL;
}// 入隊
void enqueue(Queue *queue, BiTNode *treeNode) 
{QueueNode *newNode = malloc(sizeof(QueueNode));newNode->treeNode = treeNode;newNode->next = NULL;if (isQueueEmpty(queue)) {queue->head = queue->tail = newNode;} else {queue->tail->next = newNode;queue->tail = newNode;}
}// 出隊
BiTNode* dequeue(Queue *queue) 
{if (isQueueEmpty(queue)) {return NULL;}QueueNode *temp = queue->head;BiTNode *treeNode = temp->treeNode;queue->head = queue->head->next;if (queue->head == NULL) {queue->tail = NULL;}free(temp);return treeNode;
}// 層序遍歷
void each_of_tree(BiTNode *root) 
{if (root == NULL) {return;}//定義對聯Queue queue;// 初始化隊列initQueue(&queue);// 根節點入隊enqueue(&queue, root);while (!isQueueEmpty(&queue)) {// 出隊BiTNode *current = dequeue(&queue);//訪問節點printf("%c \n", current->data);// 左子節點入隊if (current->lchild != NULL) {enqueue(&queue, current->lchild);}// 右子節點入隊if (current->rchild != NULL) {enqueue(&queue, current->rchild);}}
}

主函數

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h"int main(int argc, char **argv)
{BiTNode *root;CreateTree(&root);PreOrderTraverse(root);printf("\n");InOrderTraverse(root);printf("\n");PostOrderTraverse(root);printf("\n");DestroyTree(root);root = NULL;each_of_tree(root);return 0;
}

7. ??整體總結??

  • ??數據結構核心??：樹和二叉樹的定義、屬性、存儲及遍歷是重點，強調樹的結構特性（如度、深度）和二叉樹的具體規則（如左右子樹順序）。數學特性（如結點數量公式）和遍歷方法（前序、中序、后序）為算法實現奠定基礎。
  • ??實用工具??：GDB 調試部分提供 step-by-step 指南，解決段錯誤和一般調試問題，突出命令如 where、b、p 的重要性。
  • ??算法應用??：希爾排序作為高效排序算法，以代碼示例展示其 gap 策略和插入優化。

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

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

相關文章

sqlite的sql語法與技術架構研究

sqlite的sql語法與技術架構研究

(Owed by: 春夜喜雨 http://blog.csdn.net/chunyexiyu) 參考&#xff1a;參考提示詞與豆包AI交互輸出內容。 sqlite作為最常用的本地數據庫&#xff0c;其支持的sql語法也比較全面&#xff0c;歷經了二十多年經久不衰&#xff0c;其技術架構設計也是非常優秀的。 一&#xff1a…
閱讀更多...
Javascript中的一些常見設計模式

Javascript中的一些常見設計模式

1. 單例模式&#xff08;Singleton Pattern&#xff09; 核心思想 一個類只能有一個實例&#xff0c;并提供一個全局訪問點。 場景 全局緩存Vuex / Redux 中的 store瀏覽器中的 localStorage 管理類 示例 const Singleton (function () {let instance;function createInstance…
閱讀更多...
2025 年最佳 AI 代理：工具、框架和平臺比較

2025 年最佳 AI 代理：工具、框架和平臺比較

目錄 什么是 AI Agents 應用 最佳 AI Agents&#xff1a;綜合列表 LangGraph AutoGen CrewAI OpenAI Agents SDK Google Agent Development Kit (ADK) 最佳no-code和open-source AI Agents Dify AutoGPT n8n Rasa BotPress 最佳預構建企業 AI agents Devin AI …
閱讀更多...
Linux 學習 ------Linux 入門（上）

Linux 學習 ------Linux 入門（上）

Linux 是一種自由和開放源代碼的類 Unix 操作系統。它誕生于 1991 年&#xff0c;由芬蘭程序員林納斯?托瓦茲&#xff08;Linus Torvalds&#xff09;發起并開發。與 Windows 等閉源操作系統不同&#xff0c;Linux 的源代碼是公開的&#xff0c;任何人都可以查看、修改和傳播&…
閱讀更多...
[202403-E]春日

[202403-E]春日

[202403-E]春日 題目背景 春水初至&#xff0c; 文筆亦似花開。 題目描述 坐看萬紫千紅&#xff0c; 提筆洋洋灑灑&#xff0c; 便成篇文章。 現在給你這篇文章&#xff0c; 這篇文章由若干個單詞組成&#xff0c; 沒有標點符號&#xff0c; 兩兩單詞之間由一個空格隔開。 為了…
閱讀更多...
Unity筆記(三)——父子關系、坐標轉換、Input、屏幕

Unity筆記(三)——父子關系、坐標轉換、Input、屏幕

寫在前面寫本系列的目的(自用)是回顧已經學過的知識、記錄新學習的知識或是記錄心得理解&#xff0c;方便自己以后快速復習&#xff0c;減少遺忘。這里只有部分語法知識。九、父子關系1、獲取、設置父對象(1)獲取父對象可以通過this.transform.parent獲取當前對象的父對象Trans…
閱讀更多...
基于Dubbo的高并發服務治理與流量控制實戰指南

基于Dubbo的高并發服務治理與流量控制實戰指南

基于Dubbo的高并發服務治理與流量控制實戰指南 在微服務架構的大規模應用場景中&#xff0c;如何保證服務在高并發壓力下的穩定與可用&#xff0c;是每位后端開發者必須面對的挑戰。本文結合實際生產環境經驗&#xff0c;分享基于Apache Dubbo的高并發服務治理與流量控制方案&a…
閱讀更多...
Mac 洪泛攻擊筆記總結補充

Mac 洪泛攻擊筆記總結補充

一、Mac 洪泛攻擊原理交換機依靠 MAC 地址表來實現數據幀的精準轉發&#xff0c;該表記錄著端口與相連主機 MAC 地址的對應關系。交換機具備自動學習機制&#xff0c;當收到一個數據幀時&#xff0c;會將幀中的源 MAC 地址與進入的端口號記錄到 MAC 表中。同時&#xff0c;由于…
閱讀更多...
路由器不能上網的解決過程

路由器不能上網的解決過程

情況 前段時間&#xff0c;公司來人弄了一下網絡后&#xff0c;我的路由器就不能上網了&#xff0c;怎么回事啊。 先看看路由器的情況&#xff1a;看著網絡是有連接的&#xff1a;看這上面是能上網的&#xff0c;但是網都是上不去。 奇怪&#xff01; 路由器介紹 路由器&#x…
閱讀更多...
Rancher 和 KubeSphere對比

Rancher 和 KubeSphere對比

以下是 Rancher 與 KubeSphere 的深度對比&#xff0c;涵蓋核心定位、架構設計、功能模塊、適用場景等關鍵維度&#xff0c;助您精準選型&#xff1a;一、核心定位與設計哲學維度RancherKubeSphere本質Kubernetes 多集群管理控制平面Kubernetes 全棧云原生操作系統目標簡化K8s集…
閱讀更多...
【深度學習新浪潮】TripoAI是一款什么樣的產品？

【深度學習新浪潮】TripoAI是一款什么樣的產品？

TripoAI是由硅谷AI初創公司VAST開發的多模態3D內容生成平臺，其核心技術基于數十億參數的3D基礎模型，專注于通過文本描述、單圖/多圖輸入或手繪涂鴉快速生成高精度可編輯的3D模型。以下是其核心信息： 一、技術架構與核心功能 秒級生成與多模態輸入 生成速度：僅需8秒即可生成…
閱讀更多...
二十八天（數據結構：圖的補充）

二十八天（數據結構：圖的補充）

圖&#xff1a;是一種非線性結構形式化的描述: G{V,R}V:圖中各個頂點元素(如果這個圖代表的是地圖&#xff0c;這個頂點就是各個點的地址)R:關系集合&#xff0c;圖中頂點與頂點之間的關系(如果是地圖&#xff0c;這個關系集合可能就代表的是各個地點之間的距離)在頂點與頂點…
閱讀更多...
戶外廣告牌識別準確率↑32%：陌訊多模態融合算法實戰解析

戶外廣告牌識別準確率↑32%：陌訊多模態融合算法實戰解析

原創聲明本文為原創技術解析&#xff0c;核心技術參數與架構設計引用自《陌訊技術白皮書》&#xff0c;禁止任何形式的轉載與抄襲。一、行業痛點&#xff1a;戶外廣告牌識別的三大技術瓶頸戶外廣告牌作為城市視覺符號的重要載體&#xff0c;其智能化識別在商業監測、合規監管等…
閱讀更多...
【vue組件通信】一文了解組件通信多種方式

【vue組件通信】一文了解組件通信多種方式

前言 在 Vue 中&#xff0c;組件通信有多種方式&#xff0c;適用于不同場景&#xff08;父子組件、兄弟組件、跨級組件等&#xff09;。以下是完整的組件傳值方法總結&#xff0c;僅供概覽參考&#xff1a;一、父子組件通信 1. Props&#xff08;父 → 子&#xff09; 父組件通…
閱讀更多...
項目一系列-第3章 若依框架入門

項目一系列-第3章 若依框架入門

第3章 若依框架入門 3.1 若依框架概述 為什么要基于若依框架開發&#xff1f; 快速開發&#xff1a;能快速搭建一個應用框架&#xff0c;減少工作量。可定制化&#xff1a;提供豐富插件和拓展點&#xff0c;滿足不同項目的特定需求。簡化開發流程&#xff1a;框架提供常用的功能…
閱讀更多...
WSL安裝MuJoco報錯——FatalError: gladLoadGL error

WSL安裝MuJoco報錯——FatalError: gladLoadGL error

文章目錄WSL中配置MuJoCo報錯 FatalError: gladLoadGL error 的終極解決方案&#x1f50d; 問題原因分析? 解決方案&#xff1a;切換至 EGL 渲染后端第一步&#xff1a;安裝系統級依賴庫第二步&#xff1a;使用 Conda 安裝兼容的圖形庫第三步&#xff1a;設置環境變量以啟用 E…
閱讀更多...
2025產品經理接單經驗分享與平臺匯總

2025產品經理接單經驗分享與平臺匯總

產品和開發永遠是一家&#xff0c;如此說來產品和開發接單的經驗和平臺其實大差不差&#xff0c;今天剛好看到后臺有人咨詢產品經理接單的問題&#xff0c;索性直接寫一篇文章好了。 目錄 一、產品經理接單的三個關鍵建議 1、能力產品化&#xff0c;比履歷更重要 2、合同、…
閱讀更多...
無人機航拍數據集|第8期 無人機海上目標檢測YOLO數據集3641張yolov11/yolov8/yolov5可訓練

無人機航拍數據集|第8期 無人機海上目標檢測YOLO數據集3641張yolov11/yolov8/yolov5可訓練

簡介 示例 數據集地址 無人機海上目標檢測YOLO數據集
閱讀更多...
BGP協議筆記

BGP協議筆記

一、BGP協議&#xff08;邊界網關協議&#xff09; 是一種用于自治系統間的動態路由協議&#xff0c;是一種外部網關(EGP)協議。負責在不同自治系統(AS)之間交換路由信息&#xff0c;目的是實現大規模網絡的可擴展性、策略控制和穩定性。 自治系統AS&#xff1a;一組被進行統…
閱讀更多...
Ⅹ—6.計算機二級綜合題27---30套

Ⅹ—6.計算機二級綜合題27---30套

第27套 【填空題】 給定程序中，函數fun的功能是:計算形參x所指數組中N個數的平均值(規定所有數均為正數），將所指數組中小于平均值的數據依次移至數組的前部，大于等于平均值的數據依次移至x所指數組的后部，平均值作為函數值返回，在主函數中輸出平均值和移動后的數據。 …
閱讀更多...
最新文章

Copyright @ 2022~2023