不用栈的二叉树中序遍历#

1
// 中序遍历非栈非递归
2
void inOrder_noRecursion_noStack(TreeNode* r, char* pattern)
3
{
4
    TreeNode* current = r;
5
    while(current)
6
    {
7
        if(current->lchild == NULL)
8
        {
9
            // 当前节点没有左孩子，所以是应该访问的结点
10
            printf(pattern, current->value);
11
            current = current->rchild;
12
        }
13
        else
14
        {
15
            TreeNode* past = current->lchild;
16
            // past一直到最右下
17
            while(past->rchild != NULL && past->rchild != current)
18
                past = past->rchild;
19

20
            if(past->rchild == NULL)
21
            {
22
                // 此时current是past的后继结点，建立链接方便下次找到后继节点
23
                past->rchild = current;
24
                current = current->lchild;
25
            }
26
            else
27
            {
28
                /*
29
                此时past的右孩子指向后继节点，所以是第二次访问
30
                代表当前结点的左子树已经访问完毕，所以访问当前结点
31
                然后把指针移到后继或者右子树，并消除多余链接
32
                */
33
                printf(pattern, current->value);
34
                past->rchild = NULL;
35
                current = current->rchild;
36
            }
37
        }
38
    }
39
}