二叉树-2

拖到下午才写剩下这两个函数，都折腾了好久。

中序遍历的这个版本是不用栈的，用一个flag记住上一步是否是从左子树操作完回溯上来的。如果不是，那么左子树、自己、右子树都没有访问，就先深入左子树，向左下行。如果是回溯的（或者没有左子树），那么左子树已经访问完毕，就操作自己，然后去找右子树。右子树存在，就深入右子树，同时这一步肯定不是回溯的，flag置否。右子树不存在，那包括爹爹的这棵大树就访问完了，往上面回溯，通过succ()找到回溯到哪里去，当然flag为真。感觉这逻辑拆得蛮暴力的。

void travInI3(BinNode* root){ //中序遍历 迭代3
    bool backtrack = false; //前一步是否刚从左子树回溯，如果不是，就去找左子树；如果是，就该访问自己和右子树了。
    BinNode *x = root;
    while(1){
        if(!backtrack && x -> lc){ //有左子树且不是刚回溯
            x = x -> lc; //左下行
        }else{ //无左子树或刚回溯，反正都不考虑左子树了
            printf("%d ", x -> data);
            if(x -> rc){ //有右子树，向下
                x = x -> rc;
                backtrack = false; 
            }else{ //没有右子树，那就向上回溯
                x = succ(x);
                if(!x) break; //如果后继为NULL，是出口了
                backtrack = true;
            }
        }
    } 
}

然后后序遍历就只研究这一个非递归版本吧。这个和前面先序、中序的版本是类似的，不过感觉逻辑绕了一些。

首先是一个HLVFL（"highest leaf visible from left"），即，先进行访问的是一个左下链条上，从左侧看过去的最高层的叶子。因为对于局部访问的次序是左孩子、右孩子、自己，在找HLVFL过程中，顺带入栈时要很注意次序：如果有左孩子，那出栈顺序肯定是左孩子、可能存在的右孩子、自己（入栈相反），然后x深入左子树；如果只有右孩子，好吧，那出栈顺序就是右孩子、自己（入栈相反），然后x深入右子树。

找到HLVFL后， 就可以弹出，操作。可是在这左、右、爹的出栈顺序中，下一个待出栈的可能是爹（爹爹的子树访问完了，不用找HLVFL，操作爹就可以），也可能是右兄弟（要深入右子树，就得找HLVFL）。所以下一轮循环开始有个看起来很奇葩的判断。

void travPostI1(BinNode* root){
    BinNode *stack[50], *x = root;
    int len = 1;
    stack[0] = x;
    while(len){
        if(x -> parent != stack[len - 1]){ //当前栈顶不是x的父亲，一定是x的右兄弟.
            x = stack[len - 1]; //右兄弟赋值给x
            while(x){ //"highest leaf visible from left"
                if(x -> lc){ //x有左孩子，优先的是x的左孩子
                    if(x -> rc) {stack[len] = x -> rc; len ++;} //如果有右孩子，右孩子先入栈，后出
                    stack[len] = x -> lc; len ++;
                    x = x -> lc;
                }else{ //x没有左孩子，那访问x之前访问的只能是x的右孩子了
                    stack[len] = x -> rc; len ++;
                    x = x -> rc;
                }
            }
            len --; //最后一个入栈的x是个NULL，扔了
        }
        x = stack[len - 1]; len --; //弹出栈顶
        printf("%d ", x -> data); //操作
    }
}

我也快晕了，撤。