二叉树的遍历

【概述】

树中最基本的操作是遍历，即从根结点出发，按照某种次序访问树中的所有结点，使得每个结点仅被访问一次

在二叉树中，有两种遍历方式，一种是基于树的递归特性的前/中/后序遍历，一种是基于树的层次特性的层次遍历

【访问函数】

通常来说，二叉树都是使用二叉链表实现的，即：

typedef struct BiTNode {    //二叉链表
    int data;               //数据域
    struct BiTNode *lchild; //左指针
    struct BiTNode *rchild; //右指针
} BiTNode, *BiTree;
bool initBiTree(BiTree &root) { //初始化
    root = NULL;                //空树
    return true;
}

在使用二叉链表实现的二叉树中，从构建二叉树，到求二叉树的深度，以及求叶结点个数等操作，都是在遍历操作基础上来进行的，因此在实际应用时，在遍历操作的基础上修改访问函数 visit() 即可得到大部分操作

void visit(BiTree p) { //访问
    //根据实际需要更改该函数
    if (p == NULL)
        printf("null\n");
    else
        printf("%d\n", p->data);
}

【前中后序遍历的递归实现】

前序遍历

前序遍历，是按照根结点、左子树、右子树的顺序对二叉树进行遍历

void preOrder(BiTree root) { //递归先序遍历
    if (root == NULL)
        return;
    visit(root);
    preOrder(root->lchild);
    preOrder(root->rchild);
}

中序遍历

中序遍历，是按照左子树、根结点、右子树的顺序对二叉树进行遍历

void inOrder(BiTree root) { //递归中序遍历
    if (root == NULL)
        return;
    inOrder(root->lchild);
    visit(root);
    inOrder(root->rchild);
}

后序遍历

后序遍历，是按照左子树、右子树、根结点的顺序对二叉树进行遍历

void postOrder(BiTree root) { //递归后序遍历
    if (root == NULL)
        return;
    postOrder(root->lchild);
    postOrder(root->rchild);
    visit(root);
}

【前中后序遍历的非递归实现】

前序遍历

对于前序遍历，其非递归算法如下：

1）每遇到一个结点，若其不空，首先访问该结点，然后将其压入栈中，再访问它的左孩子，若当前结点为空且栈空时，算法结束

2）若其左孩子不空，转到步骤 1）

3）若其左孩子为空，说明已经到达该子树的最左底端，此时从栈中取出其父结点，访问父结点的右孩子，转到步骤 1）

void preOrderByStack(BiTree root){//非递归前序遍历
    stack<BiTree> S;
    BiTree p = root;       //工作指针
    while (p != NULL || !S.empty()) {
        if (p != NULL) {   //当前结点存在
            visit(p);
            S.push(p);     //当前结点入栈
            p = p->lchild; //指向其左孩子
        } else {           //当前结点不存在，到达子树最底端
            p = S.top();   //从栈中获取当前结点的父结点
            S.pop();       //父结点出栈
            p = p->rchild; //访问父结点的右孩子
        }
    }
}

中序遍历

对于中序遍历，其非递归算法如下：

1）每遇到一个结点，若其不空，首先将其压入栈中，再访问它的左孩子，若当前结点为空且栈空时，算法结束

2）若其左孩子不空，转到步骤 1）

3）若其左孩子为空，说明已经到达该子树的最左底端，此时从栈中取出其父结点，访问该结点，再访问父结点的右孩子，转到步骤 1）

void inOrderByStack(BiTree root) { //非递归中序遍历
    stack<BiTree> S;
    BiTree p = root;       //工作指针
    while (p != NULL || !S.empty()) {
        if (p != NULL) {   //当前结点存在
            S.push(p);     //当前结点入栈
            p = p->lchild; //指向其左孩子
        }
         else {            //当前结点不存在，到达子树最底端
            p = S.top();   //从栈中获取当前结点的父结点
            visit(p);
            S.pop();       //父结点出栈
            p = p->rchild; //访问父结点的右孩子
        }
    }
}

后序遍历

后序遍历要求先访问左子树和右子树后再访问根结点，在进行后序遍历时，首先访问左孩子，将父结点存于栈中，但当元素弹出时，如果利用非递归的前序中序遍历的思想，无法判断此时该访问右孩子还是访问父结点，因此其非递归实现需要一个标记，用于记录该结点的右孩子是否被访问过

后序遍历的非递归算法如下：

1）每遇到一个结点，若其不空，将其标记设为 0，代表其右孩子未被访问，然后将其压入栈中，再访问其左孩子，若当前结点为空且栈空时，算法结束

2）若其左孩子不空，转到步骤 1）

3）若其左孩子为空，说明已经到达该子树的最左底端，此时从栈中取出一个结点，通过标记判断右孩子是否被访问过

4）若取出结点的标记为 0，说明该结点的右孩子未被访问过，那么将标记改为 1，重新压入栈中，访问该结点的右孩子，转到步骤 1）

5）若取出结点的标记为 1，说明该结点的左右孩子均被访问过，访问该结点

6）若当前结点为空，但栈非空，说明已到达该子树的最右底端，此时从栈中取出一个结点，判断该结点的标记，若标记为 0，转到步骤 4），若标记为 1，转到步骤 5）

void postOrderByStack(BiTree root) { //非递归后序遍历
    struct stackNode {
        BiTree t;
        int tag;
    };
    stack<stackNode> S;

    BiTree p = root; //工作指针
    while (p != NULL || !S.empty()) {
        if (p != NULL) { //当前结点存在
            stackNode temp;
            temp.t = p;
            temp.tag = 1; //父结点标记设为 1

            S.push(temp);
            p = p->lchild; //访问左孩子
        } 
        else {             //当前结点不存在，到达子树最底端
            stackNode temp;
            temp = S.top(); //当前栈顶元素
            S.pop();
            if (temp.tag == 1) {    //右孩子未被访问过
                temp.tag = 0;       //改变当前结点访问状态
                S.push(temp);       //将该结点重新压入栈中
                p = temp.t->rchild; //访问该结点的右孩子
            } 
            else                    //右孩子已被访问过，访问该结点
                visit(temp.t);
        }
    }
}

说明：在后序遍历的非递归实现中，当访问一个结点 p 时，栈中的结点恰好是 p 的所有祖先，从栈底到栈顶的结点再加上 p，就构成了从根到结点 p 的一条路径，利用该思想，可以求解根到某结点的路径、求两结点的最近公共祖先

【层次遍历】

层序遍历，是按层序从小到大逐个访问，同一层次按照从左到右的顺序访问

void levelOrder(BiTree root) { //层序遍历
    queue<BiTree> Q;
    if (root != NULL) //根结点加入队列
        Q.push(root);
    BiTree p;
    while (!Q.empty()) {
        BiTree p = Q.front();  //取队首元素
        Q.pop();
        visit(p);              //访问该结点
        if (p->lchild != NULL) //左孩子加入队列
            Q.push(p->lchild);
        if (p->rchild != NULL) //右孩子加入队列
            Q.push(p->rchild);
    }
}