本部分中的非递归方式的3种遍历方式相对复杂。

非递归 先序 遍历

Traverse 美 [trəˈvɜrs] n.穿过； 横贯，横切； 横木； [建]横梁 vt.横越，横贯； 通过； [法]否认，反驳； [木工]横刨 vi.来回移动； 旋转； 横越； adj.横贯的； 横切的；

//b: 指向二叉树的根节点
void PreOrderTraverse(BiTree b){
    //建栈
    InitStack(S);
    //设置临时的辅助指针,功能: 遍历结点，初值为指向根节点
    BiTree p = b;
    //p指向的结点不为空 || 栈不为空
    while(p || !IsEmpty(S)){
        //1. 从根结点走到左下角最下面的结点：每个结点，先访问（E.g 打印该结点数据），再压栈；
        //简记：只要左子树存在，就一直循环下去（访问+压栈），否则跳出当前循环；
        while(p){
            printf("%c",p->data);    //先访问：先序先遍历当前p指向的结点
            Push(S,p);        //压栈：将指向当前结点的指针（简记：将当前结点压栈），先压进栈保存
            p=p->lchild;    //让当前指针指向左孩子;
        }
        //2. 先将最左下角结点出栈（即：top保存的结点出栈），然后访问它的右子树，直到栈为空；
        //先判断当前栈是否有数据，如果有则出栈；
        if(!IsEmpty(S)){
            //让临时指针指向当前栈顶元素出栈，让p指向栈顶对应的结点：
            p = Pop(S);
            //然后让临时指针再指向当前结点的右孩子（右子树）：
            p = p->rchild;
        }
    }
}

非递归 中序 遍历

void MidOrderTraverse(BiTree b){
    //建栈
    InitStack(S);
    //设置临时的辅助指针,功能: 遍历结点，初值为指向根节点
    BiTree p = b;
    //p指向的结点不为空 || 栈不为空
    while(p || !IsEmpty(S)){
        //1. 从根结点走到左下角最下面的结点：每个结点，先访问（E.g 打印该结点数据），再压栈；
        //简记：只要左子树存在，就一直循环下去（访问+压栈），否则跳出当前循环；
        while(p){
            //printf("%c",p->data);    //先访问：先序先遍历当前p指向的结点
            Push(S,p);        //压栈：将指向当前结点的指针（简记：将当前结点压栈），先压进栈保存
            p=p->lchild;    //让当前指针指向左孩子;
        }
        //2. 先将最左下角结点出栈（即：top保存的结点出栈），然后访问它的右子树，直到栈为空；
        //先判断当前栈是否有数据，如果有则出栈；
        if(!IsEmpty(S)){
            //让临时指针指向当前栈顶元素出栈，让p指向栈顶对应的结点：
            p = Pop(S);
            //把访问放到这里:
            printf("%c",p->data);    //访问：先序先遍历当前p指向的结点
            //然后让临时指针再指向当前结点的右孩子（右子树）：
            p = p->rchild;
        }
    }
}

非递归 后续 遍历

void PostOrderTraverse(BiTree b)
{
    //建栈
    InitStack(S);
    //设置临时的辅助指针,功能: 遍历结点，初值为指向根节点
    BiTree p = b;
    //用于记录刚刚访问过的右子树的父结点：
    BiTree r = NULL;
    //p指向的结点不为空 || 栈不为空
    while(p || !IsEmpty(S))
    {
        //1. 从根结点到最左下角的左子树都入栈；
        //因为外循环while()已经包含了p的情况，所以这里可以直接判断:
        if(p)
        {
            //压栈：将指向当前结点的指针（简记：将当前结点压栈），先压进栈保存
            Push(S,p);
            //让当前指针指向左孩子;
            p=p->lchild;
            //然后返回到外循环while(),再继续判断p左孩子是否存在，如果存在则继续压栈；
        }
        //2. 返回栈顶的2种情况，需要分别处理：
        else
        {
            //只取栈顶的元素，先不出栈。相当于先试读一下栈顶的元素（让p指向栈顶对应的结点）：
            GetTop(S,p);
            //2.1 如果从左子树返回父结点，右子树还没有访问，则让p指向当前结点的右子树：
            //p指向的当前结点的右子树存在 && 相邻两次访问的结点是右结点
            if(p->rchild && p->rchild != r)
            {
                p = p->rchild;
            }
            //2.2 如果从右子树返回其父节点，则出栈，
            else
            {
                //让临时指针指向当前栈顶元素出栈，让p指向栈顶对应的结点：//不让p指向该栈顶结点元素，下面一句真么访问打印其内容呢？呵呵，所以要出栈。
                Pop(S,p);
                //然就访问该结点:
                printf("%c",p->data);
                //让r指向p，进行备份p的值，目的是让下次比较其是否相等，如果相等说明已经访问了右子树，如果不相等则说明还没有访问右子树：
                r = p;
                //置空的目的：保证从左侧返回到根结点或某个结点的左侧子树全部访问完，使其可以访问对应的右子树，所以这里将p置空，直接跳过上面if(p)的判断，直接去执行栈顶元素的右子树。
                p = NULL;
            }
        }
    }
}

线索 二叉树 遍历

//中序遍历线索二叉树
void InOrderTraverse(ThreadTree T)
{
    //临时指针p指向传递过来的二叉树的根结点：
    ThreadTree p = T;
    while(p)
    {
        //1. 找最左孩子
        //如果左标志位为0，即p当前指向的结点，其左孩子存在的话，则一直循环，找到最左下角结点：
        while(p->Itag == 0)
        {
            //再找其左孩子：
            p = p->lchild;
        }
        //2. 根据中序遍历的要求，访问结点
        //访问： E.g 这里的打印该结点的数据内容
        printf("%c", p->data);
        //3. 再访问它的右子树：
        //p当前指向的结点没有右孩子(即 p->rtag == 1，表示存在后继) && 后继指针指向的结点存在(因为最后右侧的后继指针=NULL，为了结束外循环)
        while(p->rtag == 1 && p->rchild)
        {
            //让p指向其对应的右结点：
            p = p->rchild;
            //访问该右结点：
            printf("%c", p->data);
        }
        //当上面一个while循环的p->tag=0时且其右孩子时（E.g B结点），那么下面的一句让其指向其右孩子结点：（避免漏掉此情况）； 
        //当指向C结点时其右孩子指向为NULL，同时即可跳出当前所在的外循环：
        p->rchild;
    }
}