当前位置:C++技术网 > 资讯 > C++镜像二叉树,又叫翻转二叉树

C++镜像二叉树,又叫翻转二叉树

更新时间:2016-06-26 17:19:46浏览次数:1+次

数据结构的基础,二叉树,该结构应用之广泛,相信大家都知道了。很多在校学生在学习数据结构的时候不知道树有什么用,所以不去认真学。连翻转二叉树都不会的话,面试的时候被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");
}