二叉树的先序、中序、后序、层序递归及非递归遍历

二叉树是一种常见的数据结构，其中每个节点最多有两个子节点，分别被称为左子节点和右子节点。在操作二叉树时，常常需要遍历树中的所有节点，以便对节点进行处理。常见的遍历方式包括先序遍历、中序遍历、后序遍历和层序遍历。除了递归遍历的方式之外，还可以使用非递归遍历的方式实现。

一、先序遍历

在先序遍历中，首先访问根节点，然后按照左子树、右子树的顺序递归遍历子树。对于任意一棵二叉树，其先序遍历序列的访问顺序为：根节点、左子树、右子树。

先序遍历的递归实现方式：

void preOrderTraversal(BiTree *root) {
    if (root == NULL) {
        return;
    }
    // 先访问根节点
    printf("%d ", root->data);
    // 再遍历左子树
    preOrderTraversal(root->lchild);
    // 最后遍历右子树
    preOrderTraversal(root->rchild);
}

先序遍历的非递归实现方式：

void preOrderTraversal(BiTree *root) {
    stack<BiTree*> s;
    BiTree *p = root;
    while (p != NULL || !s.empty()) {
        if (p != NULL) {
            // 遇到新节点，先访问该节点并入栈
            printf("%d ", p->data);
            s.push(p);
            p = p->lchild;
        } else {
            // 没有新节点，出栈当前节点并处理其右子树
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
}

二、中序遍历

在中序遍历中，先递归访问左子树，然后访问根节点，最后递归访问右子树。对于任意一棵二叉树，其中序遍历序列的访问顺序为：左子树、根节点、右子树。

中序遍历的递归实现方式：

void inOrderTraversal(BiTree *root) {
    if (root == NULL) {
        return;
    }
    // 先遍历左子树
    inOrderTraversal(root->lchild);
    // 再访问根节点
    printf("%d ", root->data);
    // 最后遍历右子树
    inOrderTraversal(root->rchild);
}

中序遍历的非递归实现方式：

void inOrderTraversal(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();
            s.pop();
            printf("%d ", p->data);
            p = p->rchild;
        }
    }
}

三、后序遍历

在后序遍历中，先递归访问左子树，然后递归访问右子树，最后访问根节点。对于任意一棵二叉树，其后序遍历序列的访问顺序为：左子树、右子树、根节点。

后序遍历的递归实现方式：

void postOrderTraversal(BiTree *root) {
    if (root == NULL) {
        return;
    }
    // 先遍历左子树
    postOrderTraversal(root->lchild);
    // 再遍历右子树
    postOrderTraversal(root->rchild);
    // 最后访问根节点
    printf("%d ", root->data);
}

后序遍历的非递归实现方式：

void postOrderTraversal(BiTree *root) {
    stack<BiTree*> s;
    BiTree *cur = root;  // 当前节点指针
    BiTree *pre = NULL;  // 上一个访问的节点指针
    while (cur != NULL || !s.empty()) {
        if (cur != NULL) {
            s.push(cur);  // 当前节点入栈
            cur = cur->lchild;
        } else {
            cur = s.top();  // 获取当前节点
            if (cur->rchild != NULL && cur->rchild != pre) {
                // 如果当前节点有右子树，并且右子树还没有访问过
                cur = cur->rchild;  // 处理右子树
            } else {
                s.pop();  // 没有右子树或右子树已经访问过了，出栈并访问当前节点
                printf("%d ", cur->data);
                pre = cur;  // 当前节点已访问，将其设置为上一个访问的节点
                cur = NULL;  // 将当前节点设置为 NULL，以便下一次出栈
            }
        }
    }
}

四、层序遍历

在层序遍历中，从树的根节点开始，按照从上到下、从左到右的顺序逐层遍历树中的节点。层序遍历的实现需要使用队列来辅助遍历。

层序遍历的实现方式：

void levelOrderTraversal(BiTree *root) {
    if (root == NULL) {
        return;
    }
    queue<BiTree*> q;
    q.push(root);
    while (!q.empty()) {
        BiTree *p = q.front();
        q.pop();
        printf("%d ", p->data);
        if (p->lchild != NULL) {
            q.push(p->lchild);
        }
        if (p->rchild != NULL) {
            q.push(p->rchild);
        }
    }
}

以上是二叉树的先序、中序、后序、层序递归及非递归遍历的实现方式，通过这些方式可以方便地访问二叉树中的节点，并进行处理。对于不同的二叉树操作，可以根据需要选择适当的遍历方式。