数据结构的基础,二叉树,该结构应用之广泛,相信大家都知道了。很多在校学生在学习数据结构的时候不知道树有什么用,所以不去认真学。连翻转二叉树都不会的话,面试的时候被HR问到不会回答,基本上就bye bye了。
什么是镜像二叉(翻转二叉树) 看图
简单来说就是节点左右换位置。
那么我们应该怎么理解呢?是不是有同学就开始想不通了?
怎么样才能保证每个节点都换一次呢?怎么才知道换了没有?换了以后会不会存在忘记换的节点呢?
那么我们设身处地想:
如果我是一个节点,我的工作是,我的左边和右边换一下,其他的我都不管。
那么每一个节点都左右换一下,不就可以了么?
我们得到了伪代码
fun(该节点)
{
如果该节点为空,则返回
左右交换
fun(左节点)——交换右节点里面的所有节点
fun(右节点)——交换右节点里面的所有节点
}
代码实现
void ChangeLeftRight(tree* t)
{
if(!t) return;
std::swap(t->_left,t->_right);
ChangeLeftRight(t->_left);
ChangeLeftRight(t->_right);
}
问题:那么采取,前中后序遍历又有什么不同呢?会不会不同呢?请想一下
答:相同。
以下是代码
#include <iostream>
struct tree
{
tree(){_left = _right = nullptr;}
~tree(){
delete _left;
delete _right;
}
tree* _left ; //左
tree* _right; //右
int _value; //值
};
std::ostream& operator<<(std::ostream& os,tree& t)
{
os<<" "<<t._value<<std::endl;
os<<" / \\"<<std::endl;
os<<" "<<t._left->_value;
os<<" "<<t._right->_value<<std::endl;
os<<" / \\ / \\"<<std::endl;
os<<""<<t._left->_left->_value;
os<<" "<<t._left->_right->_value;
os<<" "<<t._right->_left->_value;
os<<" "<<t._right->_right->_value;
return os;
}
void CreateTreeNode(tree* head,int l ,int r)
{
head->_left = new tree;
head->_left->_value = l;
head->_right = new tree;
head->_right->_value = r;
}
void ChangeLeftRight(tree* t)
{
if(!t) return;
std::swap(t->_left,t->_right);
ChangeLeftRight(t->_left);
ChangeLeftRight(t->_right);
}
int main()
{
//创建二叉树
tree head;
head._value = 1;
CreateTreeNode(&head,2,3);
CreateTreeNode(head._left,4,5);
CreateTreeNode(head._right,6,7);
std::cout<<"翻转前:\n"<<head<<"\n\n";
//翻转二叉树
ChangeLeftRight(&head);
std::cout<<"翻转后:\n"<<head<<"\n\n";
system("pause");
}