二叉排序树的遍历方式

有必要把二叉排序树的几种遍历方式总结一下，只考虑中序遍历，先序遍历和后序遍历同理。

1. 递归方式

这是最简单的，代码也很简洁。

1   void inorder_walk(Node *t)

2   {

3       if(t != NULL) {

4           inorder_walk(t->left);

5           print(t);

6           inorder_walk(t->right);

7       }

8   }

2. 消除尾递归

所有的尾递归都会被编译器优化，这在编译原理中都有介绍。如果我没记错的话，原理应该是这样的：

文法 A: NIL | a | aA 具有尾递归的形式，可以改写成:

A: NIL | Ba

B: NIL | Bb

这样就消除了尾递归。消除尾递归后的遍历代码为：

1   void inorder_walk_notailrecursion(Node *t)

2   {

3       while(t != NULL) {

4           inorder_walk_notailrecursion(t->left);

5           print(t);

6           t = t->right;

7       }

8   }

3. 消除递归

操作系统在函数调用的实现上，是采用栈的形式，递归调用实际上就是将同一个函数不断压入栈中，因此要消除递归，可以在程序中用一个显示的栈来模拟。代码如下：

 1    void inorder_walk_norecursion(Node *t)

 2    {

 3        stack<Node *> s;

 4        while(1) {

 5            while(t != NULL) {

 6                s.push(t);

 7                t = t->left;

 8            }

 9            if(s.empty())

10                break;

11            t = s.top();

12            s.pop();

13            print(t);

14            t = t->right;

15        }

16    }

4. 消除递归并且不用栈

这个就比较复杂一些，基本思想是根据之前的访问的节点和当前节点的关系判断下一步的操作，具体分析和代码可以参考上一篇文章算法导论-二叉排序树。再贴一遍代码如下：

 1    void inorder_walk_nonrecursive_nostack(Node *t)

 2    {

 3        Node *prev = NULL;

 4        Node *curr = t;

 5        Node *next = NULL;

 6        while (curr != NULL) {

 7            if (prev == curr->parent) {

 8                next = curr->left;

 9                if (next == NULL) {

10                    print(curr);

11                    next = curr->right;

12                    if (next == NULL)

13                        next = curr->parent;

14                }

15            } else if (prev == curr->left) {

16                print(curr);

17                next = curr->right;

18                if (next == NULL)

19                    next = curr->parent;

20            } else {

21                next = next->parent;

22            }

23            prev = curr;

24            curr = next;

25        }

26    }