二叉树的遍历有前序，中序，后序以及层次遍历，其中前序，中序和后序遍历使用递归来写非常简单。
例如

1
2
3
4
5
6
7

void tree_preorder_re(TreeNode *node, Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    if (!node) return;
    visit(tree, node);
    tree_preorder_re(node->left, tree, visit);
    tree_preorder_re(node->right, tree, visit);
}

中序和后序，不过是调整一下visit的位置，如果不用递归的写法，改用栈来实现，其实没有那么直观。
首先按照函数调用的关系，入栈的套路都是一样的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

    Stack *s = stack_new();
    TreeNode *tNode = tree->root;
    while (stack_depth(s) != 0 || tNode)
    {
        while (tNode != NULL)
        {
            stack_push(s, tNode);
            tNode = tNode->left;
        }

        if (!stack_is_empty(s))
        {
            tNode = (TreeNode *)stack_pop(s);
            tNode = tNode->right;
        }
    }

    stack_free(s);

前序遍历

前序遍历最简单，在节点入栈的时候访问。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

void tree_preorder(Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    Stack *s = stack_new();
    TreeNode *tNode = tree->root;
    while (stack_depth(s) != 0 || tNode)
    {
        while (tNode != NULL)
        {
            stack_push(s, tNode);
            visit(tree, tNode);
            tNode = tNode->left;
        }

        if (!stack_is_empty(s))
        {
            tNode = (TreeNode *)stack_pop(s);
            tNode = tNode->right;
        }
    }

    stack_free(s);
}

中序遍历

在节点出栈的时候访问。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void tree_inorder(Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    Stack *s = stack_new();
    TreeNode *tNode = tree->root;
    while(stack_depth(s) != 0 || tNode != NULL)
    {
        while (tNode != NULL)
        {
            stack_push(s, tNode);
            tNode = tNode->left;
        }

        if (!stack_is_empty(s))
        {
            tNode = (TreeNode *)stack_pop(s);
            visit(tree, tNode);
            tNode = tNode->right;
        }
    }
    stack_free(s);
}

后序遍历

保证左右节点都访问之后，再访问父节点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

void tree_postorder(Tree *tree, void (*visit)(Tree *, TreeNode *))
{
    Stack *s = stack_new();
    TreeNode *tNode = tree->root;
    TreeNode *last_visit = NULL;
    while(tNode != NULL || !stack_is_empty(s))
    {
        while (tNode != NULL)
        {
            stack_push(s, tNode);
            tNode = tNode->left;
        }

        if (!stack_is_empty(s))
        {
            tNode = (TreeNode *)stack_top(s);
            if (tNode->right == NULL || tNode->right == last_visit)
            {
                stack_pop(s);
                last_visit = tNode;
                visit(tree, tNode);
                tNode = NULL;
            }
            else
            {
                tNode = tNode->right;
            }
            
        }
    }
    stack_free(s);
}

验证

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

main(251): __debug preorder recursive---
1 2 4 5 3 6 7 
main(254): __debug preorder non-recursive---
1 2 4 5 3 6 7 
main(257): __debug inorder recursive---
4 2 5 1 6 3 7 
main(260): __debug inorder non-recursive---
4 2 5 1 6 3 7 
main(263): __debug postorder recursive---
4 5 2 6 7 3 1 
main(266): __debug postorder non_ecursive---
4 5 2 6 7 3 1