二叉链表法表示二叉树，设计并实现二叉树遍历的递归算法和非递归算法

二叉链表法表示二叉树的节点结构体如下：

struct BinaryTreeNode {
    int val;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

其中，val 表示节点的值，left 和 right 分别表示左子树和右子树的指针，如果左子树或右子树为空，则指针为 nullptr。

下面分别介绍二叉树的递归遍历算法和非递归遍历算法。

## 递归遍历算法

### 前序遍历

前序遍历的顺序是：先遍历根节点，再遍历左子树，最后遍历右子树。递归算法如下：

void preorderTraversal(BinaryTreeNode* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " "; // 访问根节点
    preorderTraversal(root->left); // 遍历左子树
    preorderTraversal(root->right); // 遍历右子树
}

### 中序遍历

中序遍历的顺序是：先遍历左子树，再遍历根节点，最后遍历右子树。递归算法如下：

void inorderTraversal(BinaryTreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left); // 遍历左子树
    cout << root->val << " "; // 访问根节点
    inorderTraversal(root->right); // 遍历右子树
}

### 后序遍历

后序遍历的顺序是：先遍历左子树，再遍历右子树，最后遍历根节点。递归算法如下：

void postorderTraversal(BinaryTreeNode* root) {
    if (root == nullptr) {
        return;
    }
    postorderTraversal(root->left); // 遍历左子树
    postorderTraversal(root->right); // 遍历右子树
    cout << root->val << " "; // 访问根节点
}

## 非递归遍历算法

非递归遍历算法需要借助栈来实现。下面分别介绍前序、中序和后序遍历的非递归算法。

### 前序遍历

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

void preorderTraversal(BinaryTreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<BinaryTreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        BinaryTreeNode* node = st.top();
        st.pop();
        cout << node->val << " "; // 访问根节点
        if (node->right != nullptr) {
            st.push(node->right); // 先将右子树入栈
        }
        if (node->left != nullptr) {
            st.push(node->left); // 再将左子树入栈
        }
    }
}

### 中序遍历

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

void inorderTraversal(BinaryTreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<BinaryTreeNode*> st;
    BinaryTreeNode* node = root;
    while (node != nullptr || !st.empty()) {
        while (node != nullptr) {
            st.push(node);
            node = node->left; // 一直向左走，直到左子树为空
        }
        node = st.top();
        st.pop();
        cout << node->val << " "; // 访问根节点
        node = node->right; // 遍历右子树
    }
}

### 后序遍历

后序遍历的非递归算法比较复杂，需要用到两个栈来实现。具体实现如下：

void postorderTraversal(BinaryTreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<BinaryTreeNode*> st1, st2;
    st1.push(root);
    while (!st1.empty()) {
        BinaryTreeNode* node = st1.top();
        st1.pop();
        st2.push(node); // 将访问过的节点压入 st2 中
        if (node->left != nullptr) {
            st1.push(node->left); // 先将左子树入栈
        }
        if (node->right != nullptr) {
            st1.push(node->right); // 再将右子树入栈
        }
    }
    while (!st2.empty()) {
        BinaryTreeNode* node = st2.top();
        st2.pop();
        cout << node->val << " "; // 访问根节点
    }
}

以上就是二叉树的递归遍历算法和非递归遍历算法的实现。