接著上次的話題。這次我們要討論，二叉查找樹的中序遍歷和后序遍歷（遞歸和非遞歸），另外還有先序遍歷（非遞歸）

1.中序遍歷（遞歸）

static void __in_order(struct bnode_info *bnode,void (*todo)(struct bnode_info *bnode)) {if (bnode != NULL) { __in_order(bnode->lchild, todo);todo(bnode);__in_order(bnode->rchild, todo);} }static void btree_in_order(struct btree_info *info,void (*todo)(struct bnode_info *bnode)) {assert(todo != NULL && info != NULL);__in_order(info->root, todo); } 其實很簡單了，就是把語句的順序換一換就可以了。

--in_order--

5 16 24 26 50 80?

這是運行的結(jié)果。有沒有發(fā)現(xiàn)，數(shù)字是按從小到大排序的！ 如果一棵二叉查找樹 的節(jié)點值是數(shù)值，那么中序遍歷的結(jié)果為升序排列的數(shù)組。

2.中序遍歷-非遞歸

static void btree_in_order_norecur(struct btree_info *info,void (*todo)(struct bnode_info *bnode)) {assert(info != NULL && todo != NULL);if (btree_is_empty(info)) return ;//棧空間的創(chuàng)建struct stack_info *stack = (struct stack_info *)malloc(sizeof(struct stack_info));assert(stack != NULL);//棧初始化stack_init(stack);struct bnode_info *cur = info->root;while (!stack->is_empty(stack) || cur != NULL) {if (cur != NULL) {stack->push(stack, &cur, sizeof(cur));cur = cur->lchild;}else{stack->pop(stack, &cur, sizeof(cur));todo(cur);cur = cur->rchild;}}stack_destroy(stack);free(stack); }思路是創(chuàng)建一個棧，順著樹根，一直往左邊的節(jié)點走，一路壓棧，走到最左邊的那個節(jié)點，也壓棧。這時候當前節(jié)點為NULL，開始出棧，彈出的這個元素就是子樹的樹根，todo(cur), 然后遍歷右子樹。對于右子樹，也是同樣的方法，一路向左，依次壓棧......

3.先序遍歷-非遞歸

static void btree_pre_order_norecur(struct btree_info *info,void (*todo)(struct bnode_info *bnode)) {assert(info != NULL && todo != NULL);if (btree_is_empty(info)) {return ;}//棧空間的創(chuàng)建struct stack_info *stack = (struct stack_info *)malloc(sizeof(struct stack_info));assert(stack != NULL);//棧初始化stack_init(stack);struct bnode_info *cur = info->root;while (!stack->is_empty(stack) || cur != NULL) {if (cur != NULL) {todo(cur);stack->push(stack, &cur, sizeof(cur));cur = cur->lchild;}else{stack->pop(stack, &cur, sizeof(cur));cur = cur->rchild;}}stack_destroy(stack);free(stack); }其實和上面的代碼類似，也是用了棧。首先cur指向樹根，既然是先序，直接todo(cur); 之后要把當前節(jié)點壓棧，因為后面還要利用這個節(jié)點找到它的右子樹，再然后 cur = cur->lchild, 也就是遍歷左子樹，一直向左，直到左子樹為空，這時候就遍歷右子樹，于是出棧一個節(jié)點，得到他的右孩子，進入下一輪循環(huán)。

4.后序遍歷--非遞歸

后序遍歷的非遞歸思路應該是所有順序中最難的一個了。

錯誤的思路介紹：

1.首先一路向左，把從樹根開始，到樹根的左孩子，再到左孩子的左孩子，全部壓棧；

2.接著，取棧頂?shù)脑?#xff0c;看看他有沒有右孩子，轉(zhuǎn)到3或者4；

3.如果沒有，就彈出這個元素，并且打印（也可以是別的操作）這個元素，然后回到2；

4.如果有，就把右孩子作為新的樹根，回到1；

以上的思路是錯誤的，為什么呢？我們結(jié)合代碼來說明，下面請看錯誤的代碼。

static void btree_post_order_norecur_wrong(struct btree_info *info,void (*todo)(struct bnode_info *bnode)) {assert(info != NULL && todo != NULL);if (btree_is_empty(info)) {return ;}//棧空間的創(chuàng)建struct stack_info *stack = (struct stack_info *)malloc(sizeof(struct stack_info));assert(stack != NULL);//棧初始化stack_init(stack);struct bnode_info *cur = info->root;struct bnode_info *pre = NULL;while (!stack->is_empty(stack) || cur != NULL) {if (cur != NULL) {stack->push(stack, &cur, sizeof(cur));todo(cur);printf("in stack\n");cur = cur->lchild;}else{stack->top(stack, &cur, sizeof(cur));todo(cur);printf("get top stack\n");if (cur->rchild != NULL){todo(cur);printf("his rchild not null\n");cur = cur->rchild;}else{stack->pop(stack, &cur, sizeof(cur));todo(cur);//這個是真正的打印，其他地方只是為了打印日志。printf(" -----ok \n");cur = NULL;//for out stack continue}}}stack_destroy(stack);free(stack);}
為了說明清楚，我加了很多打印的地方。運行結(jié)果如下（括號里面的是我的解釋）

----wrong:post_order_norecur---
50 in stack
24 in stack
16 in stack
5 in stack
5 get top ?stack
5 ?ok ? ? ? ? ? ? ? （這個是對的）
16 get top ?stack
16 ?ok ? ? ? ? ? ??（這個是對的）
24 get top ?stack ?（24第一次 get top）
24 his rchild not null
26 in stack
26 get top ?stack
26 ?ok ? ? ? ? ? ?(這個是對的)
24 get top ?stack ?（24第二次 get top, 其實他的右子樹已經(jīng)遍歷了，可是后面發(fā)現(xiàn)又開始遍歷右子樹）
24 his rchild not null
26 in stack
26 get top ?stack
26 ?ok ? ? ? ? ?
24 get top ?stack（24第三次 get top, ?后面再次遍歷右子樹）
24 his rchild not null

……

……

后面的日志太長了，因為陷入了死循環(huán)。程序就是反復地 取棧頂元素24，遍歷他的右子樹

分析到這里，我們看出了癥結(jié)，第一次取棧頂元素24沒有錯，是為了遍歷他的右子樹。第二次取的時候，右子樹已經(jīng)遍歷過了，這時候就應該讓24出棧，并且打印。

可是怎么知道棧頂元素的右子樹是否已經(jīng)遍歷過了？方法有很多，這里我們采用這樣一種方法：根據(jù)后序遍歷的特性，如果24是第一次取（就是get top 的操作）且右孩子不為空，那么最近遍歷的元素，一定不是24的右孩子（因為還沒有遍歷）；如果24是第二次取，也就是說他的右子樹遍歷過了，那么最近遍歷的那個元素，一定是24的右孩子。

所以，我們把上面的錯誤思路改一下：

1.從樹根開始，到樹根的左孩子，再到左孩子的左孩子，全部壓棧；

2.接著，取棧頂?shù)脑?#xff0c;看看他有沒有右孩子，沒有就轉(zhuǎn)到3，有就轉(zhuǎn)到4；

3.彈出這個元素，并且打印（也可以是別的操作）這個元素，還要記錄這個元素作為最近打印的元素，然后回到2；

4.再看看他的右孩子是否等于最近打印的元素，等于轉(zhuǎn)到5 ， 不等于轉(zhuǎn)到6；

5.說明他的右子樹已經(jīng)遍歷了，轉(zhuǎn)到3；

6. 把右孩子作為新的樹根，回到1；

看看正確的代碼吧：

static void btree_post_order_norecur(struct btree_info *info,void (*todo)(struct bnode_info *bnode)) {assert(info != NULL && todo != NULL);if (btree_is_empty(info)) return ;//棧空間的創(chuàng)建struct stack_info *stack = (struct stack_info *)malloc(sizeof(struct stack_info));assert(stack != NULL);//棧初始化stack_init(stack);struct bnode_info *cur = info->root;struct bnode_info *pre = NULL; // 為了記錄最近打印的節(jié)點while (!stack->is_empty(stack) || cur != NULL){if (cur != NULL) {stack->push(stack, &cur, sizeof(cur));cur = cur->lchild; //一路向左壓棧}else{stack->top(stack, &cur, sizeof(cur));if ((cur->rchild != NULL) && (cur->rchild != pre)) //存在右子樹，且右子樹沒有遍歷{cur = cur->rchild; //遍歷右子樹}else // 沒有右孩子或者右子樹已經(jīng)遍歷的情況{stack->pop(stack, &cur, sizeof(cur));todo(cur);pre = cur;//更新最近打印的節(jié)點cur = NULL;}}}stack_destroy(stack);free(stack); }

運行后得到正確的結(jié)果：

5 16 26 24 80 50?

===============================================================================================================================

5.后序遍歷--遞歸

這個很簡單，其實遞歸遍歷思路都一樣，先序中序后序的區(qū)別就是在于 todo(bnode) 語句的位置不一樣。直接上代碼：

static void __post_order(struct bnode_info *bnode,void (*todo)(struct bnode_info *bnode)) {if (bnode != NULL) {__post_order(bnode->lchild, todo);__post_order(bnode->rchild, todo);todo(bnode);} }static void btree_post_order(struct btree_info *info,void (*todo)(struct bnode_info *bnode)) {__post_order(info->root, todo); }
今天就說到這里，還有一些內(nèi)容，下次再見！

總結(jié)

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

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