什么是二叉查找樹？

二叉查找樹（Binary Search Tree），也稱有序二叉樹（ordered binary tree）,排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：

若任意節(jié)點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

若任意節(jié)點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

任意節(jié)點的左、右子樹也分別為二叉查找樹；

沒有鍵值相等的節(jié)點（no duplicate nodes）。

好的，我們來定義一個結構體， struct bnode_info {struct bnode_info *parent;struct bnode_info *lchild;struct bnode_info *rchild; };怎么沒有數(shù)據(jù)域呢？模仿內(nèi)核鏈表，我們把這個節(jié)點嵌入到大的結構體里。 static inline void bnode_init(struct bnode_info *bnode) {bnode->parent = NULL;bnode->lchild = NULL;bnode->rchild = NULL; }節(jié)點的初始化函數(shù)，為下文做準備。
struct data_info {int data;struct bnode_info bnode; };這個是測試用的，可以看到，把節(jié)點嵌入了進去。
static int bnode_cmp(struct bnode_info *a, struct bnode_info *b) {struct data_info *pa = list_entry(a, struct data_info, bnode);struct data_info *pb = list_entry(b, struct data_info, bnode);return pa->data - pb->data; }這是比較函數(shù)，關于list_entry宏，前面的博文已經(jīng)說了，這里不贅述。
struct btree_info {struct bnode_info *root; //指向樹根int (*key_cmp)(struct bnode_info *a, struct bnode_info *b);void (*push)(struct bnode_info *bnode, struct btree_info *info);int (*del)(struct bnode_info *bnode, struct btree_info *info);struct bnode_info *(*find)(struct bnode_info *bnode, struct btree_info *info);void (*pre_order)(struct btree_info *info, void (*todo)(struct bnode_info *bnode));void (*in_order)(struct btree_info *info, void (*todo)(struct bnode_info *bnode));void (*post_order)(struct btree_info *info, void (*todo)(struct bnode_info *bnode));//非遞歸遍歷void (*pre_order_norecur)(struct btree_info *info, void (*todo)(struct bnode_info *bnode));void (*in_order_norecur)(struct btree_info *info, void (*todo)(struct bnode_info *bnode));void (*post_order_norecur)(struct btree_info *info, void (*todo)(struct bnode_info *bnode));void (*level_order)(struct btree_info *info, void (*todo)(struct bnode_info *bnode));size_t (*get_depth)(const struct btree_info *info);int (*is_empty)(const struct btree_info *info); };這里定義了很多方法，我們先不管，只要知道里面有個指針，指向樹根就可以了。
static int btree_is_empty(const struct btree_info *btree) {return btree->root == NULL; }如果樹為空，那就是連樹根都沒有了。
下面進入正題，說把一個元素插入一棵樹。 分析：1.這棵樹是空的。那問題就簡單了，這個節(jié)點就是樹根。 ? ?2.這棵樹不空。那就需要從樹根查找。把新元素和樹根比一比，小了就繼續(xù)和樹根的左孩子比，大了就繼續(xù)和樹根的右孩子比（假設不存在相等的情況），......,如果左孩子或者右孩子為空，那就是找到位置了，讓這個新元素成為孩子就可以了。注意，這里我們不用遞歸，用迭代。 static void btree_push2(struct bnode_info *bnode, struct btree_info *info) {assert(bnode != NULL && info != NULL);bnode_init(bnode);//[1].空樹if (btree_is_empty(info)) {info->root = bnode;return;}//[2].非空樹struct bnode_info *cur = info->root;struct bnode_info *parent = NULL;int flag = 0;while (cur != NULL) {parent = cur; if (info->key_cmp(bnode, cur) >= 0) {//右cur = cur->rchild;flag = 1;}else {//左cur = cur->lchild;flag = 0;}} if(flag==0) parent->lchild=bnode;elseparent->rchild=bnode;bnode->parent = parent;}

為了驗證對錯，我們要寫個遍歷樹的方法。看看先序遍歷-遞歸版本，（先樹根，然后左子樹，最后右子樹） static void __pre_order(struct bnode_info *bnode,void (*todo)(struct bnode_info *bnode)) {if (bnode != NULL) {todo(bnode);__pre_order(bnode->lchild, todo);__pre_order(bnode->rchild, todo);} }static void btree_pre_order(struct btree_info *info,void (*todo)(struct bnode_info *bnode)) {__pre_order(info->root, todo); }
void print_node(struct bnode_info *node) {struct data_info *pa = list_entry(node, struct data_info, bnode);printf("%d ", pa->data); }這個是打印用的，到時候傳給todo。
測試函數(shù)： int main() {struct data_info s[]={{50},{24},{80},{16},{26},{5}};struct btree_info *btree = (struct btree_info *)malloc(sizeof(struct btree_info));assert(btree != NULL);btree_init(btree, bnode_cmp);int i;for (i = 0; i < sizeof s/ sizeof *s; ++i) {btree->push(&s[i].bnode, btree);}//遍歷printf("--pre_order--\n");btree->pre_order(btree, print_node);printf("\n");

我們先看看運行結果：

--pre_order--

50 24 16 5 26 80?

接著說插入，前面是非遞歸方法。這次我們用遞歸。思路很簡單，把要插入的節(jié)點，和樹根比，如果樹根為空，那么這個節(jié)點就成為樹根；如果比樹根小，就和樹根的左孩子比（左孩子可以看成是新的樹根）；如果比樹根大，就和樹根的右孩子比。這里需要注意的是，假設比樹根小，那么就和樹根的左孩子比，假設傳進來的參數(shù)是新節(jié)點和左孩子，我們發(fā)現(xiàn)左孩子為NULL，怎么辦呢？當然應該把新節(jié)點的地址寫入這里，為了改寫NULL，我們就應該知道這個域的地址，這里就引入了二級指針。也就是說，我們的函數(shù)設計的時候，參數(shù)是新節(jié)點的地址，和樹根的二級指針。
static void __push(struct bnode_info *bnode, struct bnode_info **pnode, int (*cmp)(struct bnode_info *a, struct bnode_info *b)) {if (*pnode == NULL){bnode_init(bnode);*pnode = bnode; }else{ if (cmp(bnode, *pnode) > 0)__push(bnode, &(*pnode)->rchild,cmp);else __push(bnode, &(*pnode)->lchild,cmp); } }void btree_push_recursion(struct bnode_info *bnode, struct btree_info *info) {assert(bnode != NULL && info != NULL);__push(bnode, &info->root,info->key_cmp);//第二個參數(shù)是二級指針 }
總結一下，這篇文章我們說了什么？1.節(jié)點的插入（遞歸和非遞歸）2.先序遍歷（遞歸版本） 下次我們接著說。









與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的二叉查找树的C语言实现（一）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。