用c++11完成二叉树的创建与遍历

在C++11中，我们可以使用模板和类来实现二叉树的基本操作。这里我会简述如何创建一个二叉搜索树，并提供基本的插入和遍历（前序、中序和后序）的示例。

首先，定义一个简单的二叉树节点结构：

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

接下来是二叉搜索树的类，包含插入和遍历方法：

template <typename T>
class BinarySearchTree {
public:
    // 插入节点
    void insert(const T& value) {
        if (root == nullptr) {
            root = new TreeNode(value);
        } else {
            insertHelper(root, value);
        }
    }

private:
    void insertHelper(TreeNode<T>* &node, const T& value) {
        if (value < node->val)
            node->left = insertHelper(node->left, value);
        else if (value > node->val)
            node->right = insertHelper(node->right, value);
        else
            return; // 避免重复值
    }

    // 基本遍历函数模板，分别实现前序、中序和后序遍历
    template<typename Fn>
    void traverse(Fn fn) {
        traverseHelper(root, fn, false);
    }

    void traverseHelper(TreeNode<T> *node, Fn fn, bool preOrder) {
        if (node != nullptr) {
            if (preOrder) fn(node->val);
            traverseHelper(node->left, fn, preOrder);
            traverseHelper(node->right, fn, preOrder);
        }
    }

    TreeNode<T>* root = nullptr;
};

现在你可以这样使用这个二叉搜索树：

int main() {
    BinarySearchTree<int> bst;
    bst.insert(50);
    bst.insert(30);
    bst.insert(70);
    bst.insert(40);
    bst.insert(60);

    // 前序遍历
    bst.traverse([](int v) { std::cout << v << " "; });

    // 中序遍历
    bst.traverse([](int v) { traverseHelper(bst.root, [](int) {}, true, v); });

    // 后序遍历
    bst.traverse([](int v) { traverseHelper(bst.root, [](int) {}, false, v); });

    return 0;
}