欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求一颗二叉树的镜像

程序员文章站 2024-03-12 12:00:20
...

二叉树的镜像,通俗来讲就是镜子中所呈的像,左右颠倒。如图就是一个简单的二叉树镜像图。

求一颗二叉树的镜像

二叉树镜像的过程

求一颗二叉树的镜像

从图中可以看出,这棵树的根节点相同,但它们的左右两个子节点交换了位置。因此,我们不妨先交换根节点的两个子节点,就得到图中的第二颗树。

交换根节点的两个子节点后,我们发现值为3,2的节点的子节点仍然保持不变,因此我们还需要交换这两个节点的左右子节点。交换完之后就分别得到图中的第三、四颗树。做完这两次交换之后,就已经遍历完这颗树了,此时交换完之后的二叉树就是原树的镜像。

#include <iostream>

using namespace std;

template<class T>
struct BinaryTreeNode
{
    BinaryTreeNode(const T data)
        :_data(data)
        ,_Left(NULL)
        ,_Right(NULL)
    {}

    T _data;
    BinaryTreeNode<T>* _Left;
    BinaryTreeNode<T>* _Right;
};

template<class T>
class BinaryTree
{
    typedef BinaryTreeNode<T> Node;
public:
    BinaryTree()
        :_root(NULL)
    {}

    BinaryTree(const T array[], size_t size, const T& invalid)
    {
        size_t index = 0;
        _CreateBinaryTree(_root, array, size, invalid, index);
    }

    void MirrorTree()
    {
        _MirrorTree(_root);
    }
private:

    //创建二叉树
    void _CreateBinaryTree(Node*& root, const T array[], size_t size, const T& invalid, size_t& index)
    {
        while ((index < size) && (array[index] != invalid))
        {
            //创建根节点
            root = new Node(array[index]);
            //创建根节点的左子树
            _CreateBinaryTree(root->_Left, array, size, invalid, ++index);
            //创建根节点的右子树
            _CreateBinaryTree(root->_Right, array, size, invalid, ++index);
        }
    }

    //二叉树的镜像
    void _MirrorTree(Node* root)
    {
        if (root == NULL)
            return ;

        if (root->_Left == NULL && root->_Right == NULL)
            return ;

        Node* tmp = root->_Left;
        root->_Left = root->_Right;
        root->_Right = tmp;

        if (root->_Left != NULL)
            _MirrorTree(root->_Left);

        if (root->_Right != NULL)
            _MirrorTree(root->_Right);
    }

private:
    BinaryTreeNode<T>* _root;
};


int main()
{
    const char* ptr = "124###35##6";
    BinaryTree<char> t(ptr, strlen(ptr), '#');

    t.MirrorTree();

    return 0;

}
相关标签: 镜像