学步园

/*
第 15  题：
题目：输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入：
		8
      /  \
	 6   10
	/ \  / \
   5  7 9  11
输出：
		8
      /  \
	 10  6
    / \ / \
   11 97  5

两种方法：
1.递归
2.队列BFS  
*/

//递归转换当前结点的左右子树  
void convert(BTreeNode *root)
{
	BTreeNode *temp=NULL;
	if(root!=NULL)
	{
		temp=root->left;
		root->left=root->right;
		root->right=temp;
		
		convert(root->left);
		convert(root->right);
	}
} 

//循环:利用BFS层次遍历每个结点 交换其子节点 
BTreeNode *convert2(BTreeNode *root)
{
	BTreeNode *temp,*start;
	queue<BTreeNode> q;
	q.push(root);
	
	while(q.empty())
	{
		start=q.front();
		q.pop();
		
		if(start->left!=NULL)
			q.push(start->left);
		
		if(start->rightt!=NULL)
			q.push(start->right);
		
		temp=start->left;
		start->left=start->right;
		start->right=temp;	
	}
	return root;
}