一、樹(Tree)結構詳解

1. 樹的基本概念

樹的核心特性

• 非線性結構：數據元素之間存在一對多的層次關系

• 遞歸定義：樹的子樹仍然是樹

• 專業術語：

  • 度(Degree)：結點擁有的子樹數

  • 葉子結點：度為0的結點

  • 層次(Level)：根為第1層，依次遞增

  • 深度/高度：樹中結點的最大層次

  • 

樹的存儲結構

c

/* 樹結點的鏈式存儲結構 */
typedef struct _tree_node_ {DATATYPE data;struct _tree_node_ *left;  // 左子樹指針struct _tree_node_ *right; // 右子樹指針
} TreeNode;

2. 二叉樹專題

二叉樹特殊形態

1. 斜樹：所有結點只有左子樹或只有右子樹

2. 滿二叉樹：

   • 所有分支結點都有左右子樹

   • 所有葉子在同一層

3. 完全二叉樹：

   • 結點位置與同深度滿二叉樹對應

   • 葉子結點集中在左部連續位置

二叉樹性質（重要公式）

1. 第i層最多有2^(i-1)個結點

2. 深度為k的二叉樹最多有2^k -1個結點

3. 葉子結點數n0 = 度為2的結點數n2 + 1

4. 具有n個結點的完全二叉樹深度為?log?n?+1

3. 二叉樹遍歷實現

(1) 先序遍歷

c

void PreOrderTraverse(TreeNode *root) {if (NULL == root) return;printf("%c", root->data);      // 訪問根結點PreOrderTraverse(root->left);  // 遍歷左子樹PreOrderTraverse(root->right); // 遍歷右子樹
}

(2) 中序遍歷

c

void InOrderTraverse(TreeNode *root) {if (NULL == root) return;InOrderTraverse(root->left);   // 遍歷左子樹printf("%c", root->data);      // 訪問根結點InOrderTraverse(root->right);  // 遍歷右子樹
}

(3) 后序遍歷

c

void PostOrderTraverse(TreeNode *root) {if (NULL == root) return;PostOrderTraverse(root->left);  // 遍歷左子樹PostOrderTraverse(root->right); // 遍歷右子樹printf("%c", root->data);       // 訪問根結點
}

4. 二叉樹創建與銷毀

靜態創建示例

c

char data[] = "abd#f###c#eg###"; // '#'表示空結點
int ind = 0;void CreateTree(TreeNode **root) {char c = data[ind++];if ('#' == c) {*root = NULL;return;}*root = malloc(sizeof(TreeNode));(*root)->data = c;CreateTree(&(*root)->left);   // 遞歸創建左子樹CreateTree(&(*root)->right);  // 遞歸創建右子樹
}

內存釋放

c

void DestroyTree(TreeNode *root) {if (NULL == root) return;DestroyTree(root->left);   // 釋放左子樹DestroyTree(root->right);  // 釋放右子樹free(root);                // 釋放當前結點
}

二、哈希表(Hash Table)實現

1. 哈希表核心概念

關鍵技術點

• 哈希函數：將關鍵字映射到存儲位置

• 沖突解決：

  • 開放定址法：線性探測、二次探測

  • 鏈地址法：數組+鏈表結構

常用哈希函數

c

/* 除留余數法 */
int HSFun(HSTable* hs, DATATYPE* data) {return *data % hs->tlen;  // 取模運算得到索引
}

2. 哈希表完整實現

結構定義

c

typedef struct {DATATYPE* head;  // 存儲數組int tlen;        // 表長度
} HSTable;

創建與初始化

c

HSTable* CreateHsTable(int len) {HSTable* hs = malloc(sizeof(HSTable));hs->head = malloc(sizeof(DATATYPE) * len);for (int i = 0; i < len; i++) {hs->head[i] = -1;  // -1表示空位置}hs->tlen = len;return hs;
}

插入操作（線性探測法）

c

int HSInsert(HSTable* hs, DATATYPE* data) {int ind = HSFun(hs, data);while (hs->head[ind] != -1) {  // 處理沖突ind = (ind + 1) % hs->tlen;  // 線性探測}hs->head[ind] = *data;return 0;
}

查找實現

c

int HsSearch(HSTable* hs, DATATYPE* data) {int ind = HSFun(hs, data);int old_ind = ind;while (hs->head[ind] != *data) {ind = (ind + 1) % hs->tlen;if (old_ind == ind) return -1;  // 未找到}return ind;  // 返回找到的索引
}

三、Linux內核鏈表解析

1. 內核鏈表特點

與傳統鏈表的區別

• 嵌入設計：list_head結構體嵌入到宿主數據結構中

• 雙向循環：首尾相連形成環狀結構

• 高復用性：與具體數據類型解耦

核心結構定義

c

struct list_head {struct list_head *next, *prev;
};

2. 內核鏈表操作示例

鏈表初始化

c

struct my_data {int value;struct list_head list;  // 嵌入鏈表結點
};INIT_LIST_HEAD(&my_list);  // 初始化鏈表頭

添加結點

c

list_add(&new_node->list, &head);       // 頭插法
list_add_tail(&new_node->list, &head);  // 尾插法

遍歷鏈表

c

struct my_data *pos;
list_for_each_entry(pos, &my_list, list) {printk("Value: %d\n", pos->value);
}

刪除結點

c

list_del(&node->list);  // 從鏈表中移除
kfree(node);            // 釋放內存

四、嵌入式開發應用建議

1. 樹結構適用場景：

   • 配置文件解析（XML/JSON）

   • 設備樹(Device Tree)管理

   • 路由算法實現

2. 哈希表優化技巧：

   • 選擇質數作為表長度減少沖突

   • 動態擴容機制設計

   • 嵌入式環境下可考慮靜態內存分配

3. 內核鏈表最佳實踐：

   • 多線程環境配合spinlock使用

   • 使用container_of宏獲取宿主結構

   • 注意內存屏障(Memory Barrier)的使用