上一篇：iOS標準庫中常用數據結構和算法之排序

?二叉排序樹

功能：二叉排序樹的標準實現是一顆平衡二叉樹。二叉排序樹主要用來解決高效插入和高效檢索以及進行排序的問題。系統分別提供了二叉排序樹節點的查找、添加、刪除、遍歷4個功能。

iOS中實現的二叉排序樹并不是一顆平衡二叉樹，因此進行檢索時其時間復雜度可能不是O(logN)。這里極度鄙視一下！但是其它UNIX系統中的實現則是正確的。

對于二叉排序樹節點的數據結構，系統給出了一個模板：

typedef struct node {char *key; //第一個數據成員必須是指針類型！struct node *llink; //左子樹 struct node *rlink; //又子樹 } node_t; 復制代碼

要實現用二叉排序樹時需要我們自己來定義節點的數據結構，因為下列函數中所有關于節點的參數都是void*類型的。所以其內部實現不關心結構體是如何的，但是一定要滿足上面的模板的格式。

頭文件：#include <search.h>

平臺: BSD Unix。

1.查找和添加

函數簽名：

//查找節點，如果找不到則返回NULL。void *tfind(const void *key, void *const *rootp, int (*compar) (const void *key1, const void *key2)); //查找節點，如果找不到則添加到樹中去。void *tsearch(const void *key, void **rootp, int (*compar) (const void *key1, const void *key2)); 復制代碼

參數：

key:[in] 要查找或者插入的內容

rootp:[in/out] 二叉樹根節點指針的指針，這里作為輸出的原因是因為要構造出一顆平衡二叉樹，所以樹根節點可能會變化。如果要建立的是第一個節點則可以傳一個空指針的指針作為輸入輸出。

compar:[in] 節點函數比較器，這個比較器的格式如下：

/* @key1: 函數傳遞進來的關鍵字。 @key2: 樹中節點中的關鍵字，注意的是這個參數并不是樹的節點指針而是節點中的key數據成員。 @return: 如果比較結果相等則返回0, 如果key1在key2前返回小于0，如果key1在key2后面則返回大于0 */int compar(const void *key1, const void *key2); 復制代碼

return:[out] 對于tfind來說如果在樹中查找到對應的節點則返回節點指針，如果沒有找到則返回NULL。對于tsearch來說如果在樹中查找到對應的節點則返回節點指針，如果沒有找到則會將創建一個新的節點并將要查找的key作為新插入節點的key屬性，同時把新創建的節點返回。

描述：

這兩個函數分別負責查找和插入操作。樹節點的內存分配和構建由系統來完成。

2.刪除

函數簽名：

void * tdelete(const void *restrict key, void **restrict rootp, int (*compar) (const void *key1, const void *key2));復制代碼

參數： key:[in] 要刪除的節點key屬性。 rootp:[in/out] 樹的根節點，隨著節點的刪除為了保證平衡性會調節樹的根節點，因此這里需要傳遞指針的指針值。 compar:[in] 節點函數比較器。 return:[out] 返回刪除的節點的父節點指針，如果刪除的是根節點則返回根節點本身，如果要刪除的key并不在樹中則返回NULL。

描述 系統內部負責節點內存的創建和銷毀，因此當某個樹節點被刪除后這個樹節點內存會被銷毀而不能再訪問了，否則會出現crash。

3.遍歷

函數簽名：

void twalk(const void *root, void (*action) (const void *node, VISIT order, int level));復制代碼

參數：

root:[in] 樹的根節點指針，注意這里不是指針的指針。因為遍歷不會調整樹的根節點。

action:[in] 遍歷一棵樹有前序遍歷、中序遍歷和后序遍歷三種遍歷方式，因為系統不知道你要怎么處理遍歷的節點，因此通過提供一個回調函數來實現節點的遍歷。這個回調函數的格式如下：

@node: 要遍歷的節點。 @order:要遍歷的順序，這個VISIT是一個枚舉類型。 @level: 當前遍歷的節點所處的樹的層級，層級以0開始，對應樹根節點的層級。 void action(const void *node, VISIT order, int level); 復制代碼

描述：

可以看出上面要實現遍歷時必須提供一個回調的action函數，在action函數中通過對VISIT類型的參數order進行判斷可以實現各種遍歷。VISIT的定義如下：

typedef enum {preorder,postorder,endorder,leaf } VISIT; 復制代碼

當order的值是preorder或者leaf時系統將執行的是前序遍歷，當order的值是postorder或者leaf時系統將執行的是中序遍歷，當order的值是endorder或者leaf時系統將執行的是后序遍歷，當order的值是leaf系統將執行的葉子遍歷。下面的代碼將演示對遍歷的處理。

void action(const void *node, VISIT order, int level) {if (order == preorder || order == leaf){//前序遍歷}if (order == postorder || order == leaf){//中序遍歷}if (order == endorder || order == leaf){//后序遍歷}if (order == leaf){//只遍歷葉子} } 復制代碼

示例代碼

//定義一個樹節點類型，節點必須按這個格式定義 typedef struct _node {char *key; //樹節點的內容。struct _node *left;struct _node *right; }node_t;//樹排序比較器函數 int bintreecompar(const char *key1, const char *key2) {return strcmp(key1, key2); }//樹遍歷函數，這里進行前序遍歷，按樹節點升序輸出。 void action(node_t *node, VISIT order, int level) {if (order == preorder || order == leaf){printf("node's key = %s\n", node->key);} }void main() {node_t *root = NULL; //定義樹的根節點，最開始時根節點為空。//添加//看這里對root參數傳遞的規則，因為每次插入都有可能會改變根節點的值。node_t *p1 = tsearch("Bob", &root, bintreecompar); //返回節點對象，我們不需要負責節點對象的銷毀，而是通過調用tdelete函數來銷毀。NSAssert(strcmp(p1->key, "Bob")==0, @"oops!");node_t *p2 = tsearch("Alice", &root, bintreecompar);node_t *p3 = tsearch("Max", &root, bintreecompar);node_t *p4 = tsearch("Lucy", &root, bintreecompar);//查找node_t *p = tfind("Lily", &root, bintreecompar);NSAssert(p == NULL, @"oops!");p = tfind("Lucy", &root, bintreecompar);NSAssert(p != NULL, @"oops!");//刪除p = tdelete("Jone", &root, bintreecompar);NSAssert(p == NULL, @"oops!");p = tdelete("Lucy", &root, bintreecompar);NSAssert(p != NULL, @"oops!");//遍歷樹twalk(root, action); }復制代碼

總結

以上是生活随笔為你收集整理的iOS标准库中常用数据结构和算法之二叉排序树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。