将一棵二叉查找对转换为它的镜像

题目：输入一颗二元查找树，将该树转换为它的镜像，

即在转换后的二元查找树中，左子树的结点都大于右子树的结点。

用递归和循环两种方法完成树的镜像转换。

例如输入：

8
/   \
6    10
/ \   /  \
5  7  9  11

输出：

8
/  \
10   6
/ \    /\
11 9  7  5

这个题目没什么难度，关键在于对指针的理解，转换成镜像只需要交换每个节点的左右孩子指针。

下面只把两个函数贴出来，关于创建树，以及栈的操作前面几篇文章已写。

递归算法

只需要10行，recursiveMirrorBST函数

//递归，将二叉查找树转换为它的镜像
void recursiveMirrorBST(BSTreeNode *root)
{
	if(root)
	{
		recursiveMirrorBST(root->left);
		recursiveMirrorBST(root->right);
		BSTreeNode *p;
		p = root->left;
		root->left = root->right;
		root->right = p;
	}
}

非递归的算法

借助栈来完成操作，定义栈需要占用一些体积

//循环，将二叉查找树转换为它的镜像
void loopMirrorBST(BSTreeNode *root)
{
	BSTreeNode *p, *q;
	Stack *s;
	s = (Stack *)malloc(sizeof(Stack));
	initStack(s);
	push(root,s);
	
	while(s->top > -1)
	{
		p=pop(s);
		if(p->left)
			push(p->left, s);
		if(p->right)
			push(p->right, s);
		q = p->left;
		p->left = p->right;
		p->right = q;
	}

}