二叉树非递归遍历算法

二叉树非递归遍历算法 先序非递归（栈实现） 算法思想：

1. 沿着根节点向左下依次访问，访问完然后立马将结点入栈（直到左孩子为空）；
2. 走到最左下时，栈顶元素出栈，转向右子树（判断右孩子是否为空，如果右孩子不为空，则要对当前结点进行跟 1 相同的 *** 作；若为空，则将当前结点继续执行 2 ）
3. 口诀：访问入栈向左走，出栈转向右子树

void PreOrder(BiTree T){
    InitStack(S);
    BiTree p=T;
    while(p || ！IsEmpty(S)){ //如果p不为空或者栈非空
        if(p){   //p不为空
            visit(p->data); //先访问
            push(S,p);		//再入栈
            p=p->lchild;	//不为空一直向左走
        }else{
            pop(S,p);  //栈顶元素出栈
            p=p->rchild; //转向右子树
        }
    }
}

中序非递归（栈实现） 算法思想：

1. 沿着根节点的左孩子，依次入栈，直到左孩子为空（说明已经找到可以输出的结点，此时栈顶元素即是可以输出的结点）；
2. 栈顶元素出栈并访问：若其右孩子为空，则继续执行 2 ，若右孩子不为空则以当前结点为根结点的右子树执行 1
3. 口诀：入栈向左一直走，出栈访问（转向）右子树

void InOrder(BiTree T){
    InitStack(S);
    BiTree p=T;
    while(p || ！IsEmpty(S)){ //如果p不为空或者栈非空
        if(p){   //p不为空
            push(S,p);		//先入栈
            p=p->lchild;	//不为空一直向左走
        }else{
            pop(S,p);  //栈顶元素出栈
            visit(p->data); //出栈后访问
            p=p->rchild; //转向右子树
        }
    }
}

后序非递归（栈实现） 算法思想：

1. 沿着根的左孩子，依次入栈，直到左孩子为空（走到最左下）；
2. 读栈顶元素：若右孩子不空且未被访问过，则将右孩子执行 1 *** 作；//这一步需要一个r指针用来指向已访问过的结点（做标记作用）
3. 否则，直接将栈顶元素出栈并访问；（因为此时p所指结点一定是叶子节点，左右子树均为空）。

void PostOrder(BiTree T){
    InitStack(S); //初始化一个栈
    BiTree p=T;		//p指针指向根节点
    r=NULL;		//初始化辅助指针用来标记已被访问过的结点
    while(p || !IsEmpty(S)){ //树（p所指结点）非空或者栈非空
        if(p){			//p不为空
            push(S,p);	//依次入栈
            p=p->lchild; //p一直往左下走
        }else{				//p为空，也就是走到最左下了
            GetTop(S,p); //读取栈顶元素，也就是让p重新指向上一层非空结点（p重新指回去）
            if(p->rchlid && p->rchild != r) //如果p的右子树不为空并且p的右子树没被访问过
                p=p->rchild; //p指向p的右子树，转向右，做与左边同样的 *** 作
            else		//如果右子树不存在或者已经被访问过了，则直接将p所指结点d出栈，然后访问
                pop(S,p); //d出栈
            	visit(p->data); //访问
            	r=p;		//标记已访问过的结点
            	p=NULL;    //因为此时相当于以p所指结点为根结点的子树已经全部遍历完了，所以将p置空
        }
    }    
}

//为什么要搞个辅助指针用来标记已经访问过的结点呢？
//因为后序遍历是要先访问左子树，再访问右子树，最后访问根节点。
//代码中要从左子树先回到根结点（回到根节点先不访问，因为右子树如果有且未被访问过，则要先访问右子树）
//再访问右子树，最后从右子树返回根节点（此时就需要一个指针来指向最近已被访问的结点了
//因为我们并不知道这个结点是否是左子树返回的还是右子树返回的
//如果是右子树返回的，此时返回根节点，则就可以直接访问根节点
//如果是左子树返回的，则还要进行访问右子树的 *** 作）

层次遍历（队列实现） 算法思想：

1. 先将根结点入队，然后出队，访问出队结点；
2. 若出队结点有左子树，则将其左子树根结点入队；若有出队结点有右子树，则将其右子树根结点入队。（循环下去，直到队列为空）。
3. 口诀：根入出访问，左右接着入

void LevelOrder(BiTree T){
    InQueue(Q);	//初始化队列
    BiTree p;
    EnQueue(Q,p); //根结点入队
    while(!IsEmpty(Q)){ //队列非空则循环
        DeQueue(Q,p); //队头结点出队
        visit(p);		//访问出队结点
        if(p->lchild !=NULL){	//若被访问结点的左子树不为空，将其左子树根结点入队
            EnQueue(Q,p->lchild);
        }
        if(p->rchild !=NULL){	//若被访问结点的右子树不为空，将其右子树根结点入队
            EnQueue(Q,p->rchild);
        }
    }
}

​