先序遍历#

1
// 中序遍历
2
void inOrder(TreeNode* r, char* pattern)
3
{
4
    if(r==NULL)
5
    {
6
        return;
7
    }
8

9
    inOrder(r->lchild,pattern);
10
    printf(pattern, r->value);
11
    inOrder(r->rchild,pattern);
12
}
13

14
// 中序遍历非递归实现
15
void inOrder_noRecursion(TreeNode* r, char* pattern)
16
{
17
    TreeNode* current = r;
18
    TreeNode* s[100];
19
    int i = -1;
20
    do
21
    {
22
        while(current) // 一直找左子树直到为空
23
        {
24
            s[++i] = current;
25
            current = current->lchild;
26
        }
27

28
    // 等于最后一个左子树或已经访问完左子树的根节点，也就是需要输出的根结点
29
        current = s[i--];
30
        printf("%d ", current->value);
31
        if(current->rchild) // 如果有右子树子，对右子树进行遍历
32
        {
33
            current = current->rchild;
34
        }
35
        else
36
        {
37
            /*
38
            如果没有右子树，将当前树置空，
39
            这样就在下次出栈时得到下一个需要访问的树，
40
            并且会跳过左子树的访问
41
            */
42
            current = NULL;
43
        }
44

45
    }while(i != -1 || current);
46
    // 当栈空但当前结点不为空时，当前树是下一个要访问的结点
47
}

1
// 后序遍历
2
void postOrder(TreeNode* r, char* pattern)
3
{
4
    if(r==NULL)
5
    {
6
        return;
7
    }
8

9
    postOrder(r->lchild,pattern);
10
    postOrder(r->rchild,pattern);
11
    printf(pattern, r->value);
12
}
13

14
// 后序遍历非递归实现
15
void postOrder_noRecursion(TreeNode* r, char* pattern)
16
{
17
    TreeNode* current = r;
18
    TreeNode* past = NULL;
19
    TreeNode* s[100];
20
    int i = -1;
21

22
    // 先到最左的结点
23
    while(current)
24
    {
25
        s[++i] = current;
26
        current = current->lchild;
27
    }
28

29
    while(i != -1)
30
    {
31
        current = s[i--];
32
        // 如果上次访问过右子树或右子树为空，则输出当前值
33
        if(current->rchild == NULL || current->rchild == past)
34
        {
35
            printf(pattern, current->value);
36
            past = current;
37
        }
38
        else // 如果上次访问的是左子树
39
        {
40
            // 到右子树的最左的结点
41
            s[++i] = current;
42
            // 此时根节点必有右子树，若没有则会直接在if中输出
43
            current = current->rchild;
44
            while(current)
45
            {
46
                s[++i] = current;
47
                current = current->lchild;
48
            }
49
        }
50
    }
51
}