完成一个函数,输入一个二叉树,该函数输出它的镜像。
镜像其实就是在转变成镜子当中的像,观察可以发现,根结点不变,左右结点交换顺序,然后以左右结点为根结点,其左右结点再次交换顺序,依次类推,所以可以用递归来完成;但是这样的一种方法会改变原来树的结构,如果这是我们想要的就没什么,但如果不想破坏原来树的结构,就不能改变左右结点的连接;
另外一种方法,其实可以观察,树的镜像,如果用前序遍历输出原来树的结点,如果要用相同的前序遍历输出树的镜像,会发现树的镜像用前序遍历输出,其实就是在原来的树中采用“根->右结点->左结点”的方法,不同于前序遍历“根->左结点->右结点”;
程序设计如下:
#include <iostream>
#include <assert.h>
using namespace std;
struct BinaryTreeNode
{
int _val;
BinaryTreeNode* _Lchild;
BinaryTreeNode* _Rchild;
BinaryTreeNode(int val)
:_val(val)
,_Lchild(NULL)
,_Rchild(NULL)
{}
};
BinaryTreeNode* _CreatTree(const int *arr, size_t& index, size_t size)
{
if((arr[index] != '#') && (index < size))
{
BinaryTreeNode *root = new BinaryTreeNode(arr[index]);
root->_Lchild = _CreatTree(arr, ++index, size);
root->_Rchild = _CreatTree(arr, ++index, size);
return root;
}
else
return NULL;
};
BinaryTreeNode* CreatTree(const int *arr, size_t size)
{
assert(arr && size);
size_t index = 0;
return _CreatTree(arr, index, size);
}
void PrevOrder(BinaryTreeNode *root)
{
if(root != NULL)
{
cout<<root->_val<<"->";
PrevOrder(root->_Lchild);
PrevOrder(root->_Rchild);
}
}
void DestoryTree(BinaryTreeNode *root)
{
if(root != NULL)
{
delete root;
DestoryTree(root->_Lchild);
DestoryTree(root->_Rchild);
}
}
//方法一:
//void ImageTree(BinaryTreeNode *root)
//{
// if(root == NULL)
// return;
// BinaryTreeNode* tmp = root->_Lchild;
// root->_Lchild = root->_Rchild;
// root->_Rchild = tmp;
//
// ImageTree(root->_Lchild);
// ImageTree(root->_Rchild);
//}
//方法二:
void ImageTree(BinaryTreeNode *root)
{
if(root != NULL)
{
cout<<root->_val<<"->";
ImageTree(root->_Rchild);
ImageTree(root->_Lchild);
}
}
int main()
{
int arr[] = {1,2,4,'#','#',5,'#','#',3,6,'#','#',7,'#','#'};
BinaryTreeNode *root = CreatTree(arr, sizeof(arr)/sizeof(arr[0]));
PrevOrder(root);
cout<<"NULL"<<endl;
ImageTree(root);
//PrevOrder(root);
cout<<"NULL"<<endl;
DestoryTree(root);
return 0;
}
运行程序:
运行两种方法结果是相同的。
《完》
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。