二叉树-2 二叉树-2

【二叉树-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); //操作 } }

我也快晕了，撤。