C++定义二叉树类型，封装层次遍历算法，封装先序、中序、后序的递归和非递归版本的遍历算法；实现先序、中序确定二叉树代码，中序、后序确定二叉树代码，自己编写一个main函数测试以上功能

在C++中，我们可以首先定义一个简单的二叉树节点类型：

template <typename T>
struct TreeNode {
    T val;
    TreeNode<T>* left;
    TreeNode<T>* right;
    TreeNode(T x) : val(x), left(nullptr), right(nullptr) {}
};

接下来，我们定义一个二叉树类，包含层次遍历（广度优先搜索），以及递归和非递归版本的前序、中序和后序遍历方法：

#include <queue>

class BinaryTree {
public:
    // 层次遍历（广度优先）
    void levelOrderTraversal(TreeNode<T>* root) {
        if (!root) return;
        std::queue<TreeNode<T>*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode<T>* node = q.front();
            cout << node->val << " ";
            q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }

    // 递归版遍历
    void recursiveTraversePreorder(TreeNode<T>* root) {
        if (!root) return;
        cout << root->val << " ";
        recursiveTraversePreorder(root->left);
        recursiveTraversePreorder(root->right);
    }
    void recursiveTraverseInorder(TreeNode<T>* root) {
        if (!root) return;
        recursiveTraverseInorder(root->left);
        cout << root->val << " ";
        recursiveTraverseInorder(root->right);
    }
    void recursiveTraversePostorder(TreeNode<T>* root) {
        if (!root) return;
        recursiveTraversePostorder(root->left);
        recursiveTraversePostorder(root->right);
        cout << root->val << " ";
    }

    // 非递归版遍历
    void iterativePreorder(TreeNode<T>* root) {
        stack<TreeNode<T>*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode<T>* node = s.top();
            s.pop();
            cout << node->val << " ";
            if (node->right) s.push(node->right);
            if (node->left) s.push(node->left);
        }
    }
    void iterativeInorder(TreeNode<T>* root) {
        stack<TreeNode<T>*> s;
        TreeNode<T>* curr = root;
        while (curr || !s.empty()) {
            while (curr) {
                s.push(curr);
                curr = curr->left;
            }
            curr = s.top(); s.pop();
            cout << curr->val << " ";
            curr = curr->right;
        }
    }
    void iterativePostorder(TreeNode<T>* root) {
        stack<TreeNode<T>*> s1, s2; // 两个栈用于辅助操作
        s1.push(root);
        while (!s1.empty()) {
            TreeNode<T>* node = s1.top();
            s1.pop();
            s2.push(node);
            if (node->left) s1.push(node->left);
            if (node->right) s1.push(node->right);
        }
        while (!s2.empty()) {
            cout << s2.top()->val << " ";
            s2.pop();
        }
    }

private:
    template<typename U>
    friend std::ostream& operator<<(std::ostream& os, const std::vector<U>& vec);
};

// 为了方便输出，添加一个友元函数
template<typename U>
std::ostream& operator<<(std::ostream& os, const std::vector<U>& vec) {
    for (const auto& element : vec) {
        os << element << " ";
    }
    return os;
}

最后，你可以在一个`main`函数中创建一个二叉树实例，并测试这些遍历方法：

int main() {
    BinaryTree<int> tree;
    // ... 实例化并构建二叉树

    // 测试遍历
    tree.levelOrderTraversal(tree.root);   // 输出层次遍历结果
    tree.recursiveTraversePreorder(tree.root);  // 输出递归预序遍历结果
    tree.iterativePreorder(tree.root);      // 输出非递归预序遍历结果
    // 同理可以测试中序和后序遍历

    return 0;
}