- /**
- * 用二叉树链式存储实现 王道P149 T3
- *
- * ①算法思想
- *
- * ②算法设计
- */
- //10、二叉树的非递归遍历---后序遍历
- //void PostOrderN(BiTree T){
- // BiTree stack[MaxSize],p = T;
- // int top = -1;
- // while(p || top != -1){
- // if(p){
- // stack[++top] = p;//压栈
- // p = p -> lchild;
- // }else{
- // p = stack[top];//注意这边不能出栈,因为栈顶的元素还没有访问过
- // p = p -> rchild;
- //Visit(p);如果Visit直接在这边写的话那么是不对的,因为并不能保证此时p节点是“叶子节点”,
- // }
- // }
- //}
- /**
- * 原因是p虽然是父节点的右孩子,但是他自己有可能也有左右孩子,如果有的话p就是“根节点”,那么要最后访问,而不是现在访问。
- * 那么如何解决这个问题呢?问题的关键就是要搞明白p这个节点到底有没有左右孩子。
- * 分析一下过程:以此树为例:1 2 99999 4 99999 99999 3 99999 99999
- * 1 入栈... 然后 2 入栈
- * 然后 p = p -> lchild;因为 p 没有左孩子,所以 p 为空,所以访问栈顶元素的位置,然后执行p = p -> rchild;
- * 现在 p 就指向 4 了,然后 4 入栈,然后执行p = p -> lchild; 因为 4 没有左孩子,所以 p 为空,
- * ①然后 p 指向栈顶元素的位置,也就是自己 4 ,
- * 然后p = p -> rchild;p又变成了空,那么 p 下一步就会执行 p = stack[top];
- * ②也就是 p 又指向了4!
- * 那么我们就会发现当 4 自己没有左孩子的时候,p 会指向 4;
- * 然而当 4 自己没有右孩子的时候,p 也会指向 4;
- * 当第二种情况发生时,说明 p 是叶子节点,那么就应该 Visit(p);
- * 那么现在要做的就是要区分这两种情况!
- * 这两种情况有一个不同点,情况一是没有左孩子导致 p 指向 4 的,而情况二是没有右孩子导致 p 指向 4 的,
- * 那么就可以自就此区分两种情况。
- * 那么我们就 int 一个 tag,用来标记,如果是因为没有左孩子,就标记为 1,如果是因为没有右孩子,就标记为 2;
- * 只有当 tag 为 2 的时候,才能说明这个 p 是没有左右孩子的,也就是“叶子节点”,那么就可以进行visit(p)。
- * 以下为正确代码:
- */
- void PostOrderN(BiTree T){
- BiTree stack[MaxSize],p = T;
- int top = -1;
- while(p || top != -1){
- if(p){
- stack[++top] = p;//压栈
- p -> tag = 1;
- p = p -> lchild;
- }else{
- p = stack[top];//注意这边不能出栈,因为栈顶的元素还没有访问过
- if(p -> tag == 1){
- p -> tag = 2;
- p = p -> rchild;
- }else{
- Visit(p);
- top--;
- p = NULL;//让p为空后才能继续取栈顶新元素进行下一步
- }
- }
- }
- }
- //非递归后序遍历的另一种写法:
- void PostOrderNR(BiTree T){
- BiTree stack[MaxSize],p = T;
- int top = -1,tag[MaxSize] = {0};
- while(p || top != -1){
- if(p){
- stack[++top] = p;
- tag[top] = 1;
- p = p -> lchild;
- }else{
- if(tag[top] == 1){
- tag[top] = 2;
- p = stack[top];
- p = p -> rchild;
- }else{//说明是叶子节点了
- p = stack[top--];
- Visit(p);
- p = NULL;
- }
- }
- }
- }