镜像二叉树

#include <iostream>
using namespace std;

// 树节点，包括左二子、右儿子指针和保存的值
class TreeNode
{
public:
    TreeNode* _left;
    TreeNode* _right;
    int _val;

    TreeNode(int val, TreeNode* left = NULL, TreeNode* right = NULL) :
        _val(val), _left(left), _right(right){}
};

// 二叉树类
class BSTree
{
public:
    TreeNode* _root;

    BSTree(TreeNode* root = NULL) : _root(root) {}

    // 往树里增加元素
    void add(int val)
    {
        add(_root, val);
    }

    // 中序遍历并打印输出
    void midOrder()
    {
        cout << "中序遍历输出序列：";
        midOrder(_root);
        cout << endl;
    }

    // 做镜像
    void mirror()
    {
        mirror(_root);
    }

private:
    // 镜像，使用递归进行镜像，具体的做法为交换左右儿子，然后递归的对左右子树做镜像
    void mirror(TreeNode* root)
    {
        if (root == NULL) return;

        TreeNode* tmp = root->_left;
        root->_left = root->_right;
        root->_right = tmp;

        mirror(root->_left);
        mirror(root->_right);
    }

    // 中序遍历并打印序列，也用了递归
    void midOrder(TreeNode* root)
    {
        if (root == NULL) return;

        midOrder(root->_left);
        cout << root->_val << " ";
        midOrder(root->_right);
    }

    // 使用递归比较简单
    void add(TreeNode*& root, int val)
    {
        // 如果比根节点大，则添加到右子树，否则添加到左子树
        if (root == NULL) root = new TreeNode(val);
        else
        {
            if (root->_val > val) add(root->_left, val);
            else add(root->_right, val);
        }
    }
};

// 测试主函数
int main()
{
    // 建立搜索树
    BSTree tree;
    tree.add(10);
    tree.add(8);
    tree.add(123);
    tree.add(11);
    tree.add(900);

    // 输出中序遍历序列
    tree.midOrder();

    // 做完镜像后再输出中序遍历序列
    tree.mirror();
    tree.midOrder();

    system("pause");
}