递归遍历是实现深度优先遍历的既直观又简单的方式, 代码特别容易写:

void traverse(struct TreeNode *root)
{
    if (!root) return;
    traverse(root->left);
    traverse(root->right);
}

而上面这段递归代码的背后究竟发生了什么呢? 二叉树递归遍历的本质其实就是在不断的压栈与出栈, 明白了这一道理之后就很容易借助栈结构来将递归遍历转换成迭代遍历.

函数调用与递归的本质

要分析递归遍历的细节, 我们就要知道递归的过程中发生了什么, 而递归实际上也只是函数调用的一种, 所以我们需要先来看一下函数调用的过程中发生了什么.

当函数调用发生时, 传给该函数的参数, 以及被调函数内部的局部变量都会被压入栈中 (现在的处理器和编译器基本都支持通过寄存器传参, 这里我们没必要考虑这些个情况), 而在被调函数返回时, 这些信息又都会从栈中弹出. 递归只是一种自己调用自己的函数调用, 也是符合这个规则的.

我们以上面的 traverse(struct TreeNode *root) 方法和下面的一颗二叉树为例, 观察一下递归遍历过程中的栈变化.

                        A
                     /     \
                    B       C
                   / \     / \
                  D   E   F   G

其中 A 是根节点, 遍历过程由 traverse(root) 被调用开始, 那么按照上述的规则, 会发生如下几步, 为方便起见, 栈的增长为从左往右:

1. traverse(A) 被调用, A 节点入栈

   ------------
   | A |
   ------------
   

2. 在 A 层 traverse 中, 判断 A 不是 NULL, 于是调用 traverse(root->left), 也就是 traverse(B), 于是 B 入栈

   ------------
   | A | B |
   ------------
   

3. 判断 B 不是 NULL, 继续调用 traverse(root->left), 即 traverse(D), 于是 D 入栈

   ----------------
   | A | B | D |
   ----------------
   

4. 判断 D 不是 NULL, 继续调用 traverse(root->left), 即 traverse(NULL), 于是 NULL 入栈

   ------------------
   | A | B | D | NULL
   ------------------
   

5. 这层 traverse 的 if 判断为 NULL, 函数直接返回, 返回时将弹出栈顶的 NULL

   ------------------
   | A | B | D |
   ------------------
   

6. 到达 D 层的 traverse, 继续调用 traverse(root->right), 即 traverse(NULL), 于是 NULL 入栈

   ------------------
   | A | B | D | NULL
   ------------------
   

7. 和 5. 的情况一样, 这层函数将直接返回, 并弹出栈顶的 NULL

   ------------------
   | A | B | D |
   ------------------
   

8. 此时 D 层 traverse 也结束了, 函数返回, 并弹出栈顶的 D

   ------------
   | A | B |
   ------------
   

9. 回到 B 层 traverse, 调用 traverse(root->right), 即 traverse(E), 于是 E 入栈

.....

所以一切都很清晰了, 主要注意两点:

1. 每一次递归调用需要把参数压栈*, 所以下面的 Stack 是我实现的一个非常简单的栈, 用来存节点地址.
2. 另外上面的递归过程中隐含了一个信息就是每一次递归调用的返回地址实际上也会被压栈*, 所以我们也需要把这个信息记录到栈中. 为了清晰起见, 我们用另一个栈: pc 存储这个信息, 意思就是 program counter.

(* 编译器基本也都支持通过寄存器传递参数和返回值, 我们只讨论算法, 不需要考虑这个情况)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct stack {
    void           *c;
    struct stack   *next;
} Stack;

void create(Stack **ptop)
{
    *ptop = NULL;
}

void push(Stack **ptop, void *c)
{
    Stack   *tmp;

    tmp = malloc(sizeof *tmp);
    tmp->c = c;
    tmp->next = *ptop;

    *ptop = tmp;
}

void pop(Stack **ptop, void **c)
{
    Stack   *tmp;

    if (! *ptop) return;

    tmp = *ptop;
    if (c) *c = tmp->c;
    *ptop = (*ptop)->next;
    free(tmp);
}

void top(Stack **ptop, void **c)
{
    *c = (*ptop)->c;
}

int empty(Stack **ptop)
{
   return *ptop == NULL; 
}

void traversal(struct TreeNode* root)
{
    long            mark;
    Stack           *s;
    Stack           *pc;
    
    create(&s);
    create(&pc);
    
    push(&s, root);
    push(&pc, 0);
    while (!empty(&s)) {
        top(&s, &root);
        
        if (!root) {
            pop(&s, &root);
            pop(&pc, &mark);
            continue;
        }

        pop(&pc, &mark);
            
        if (mark == 0) {
            push(&s, root->left);
            push(&pc, 1);
            push(&pc, 0);
        } else if (mark == 1) {
            push(&s, root->right);
            push(&pc, 2);
            push(&pc, 0);
        } else {
            pop(&s, &root);
        }
    }
}

Hello Steemit!

初来 steemit, 账号已经注册了有些日子了, 一直在纠结第一篇文章该写些啥, 看到好多人在发旅游和美食很是羡慕~ 不过我是个很宅的程序员, 想了想还是以一篇体现我职业的文章作为在 steemit 的开始吧~

大家好我是 cifer, 是个程序员, 很高兴能够在 steemit 遇到大家~

我很喜欢区块链技术, 最近在研究 ethereum 以及 smart contracts. 有兴趣的话可以一起交流~