传递指针变量给函数调用时，是用按值传递的方式把指针值（地址）传递给函数，函数通过指针直接操作原变量。这个过程中是无法修改指针的。如，要实现修改T->lchild，使得，T->lchild = p，在function( T->child, p ) 中是实现不了的，应该对采用引用传递，或传递指针的指针。

题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。

例如输入：

     8

    /  \

  6     10

 / \     / \

5   7  9   11

输出：

      8

    /   \

  10     6

 /  \     / \

11  9  7    5

定义二元查找树的结点为：

 

1 typedef struct BSTNode2 {3 　　elemtype data；4 　　struct BSTNode *lchild, *rchild;5 }BSTNode, *BSTree

 

解法一：采用递归思路，层层交换节点的左右孩子指针。(要按引用传递指针，或传递指针的指针)

解法二：用栈代替递归。因为递归的本质是编译器产生了一个函数调用的栈。做法是首先将root节点push入栈。然后进入循环，当栈不为空时，pop栈顶。交换栈顶的左右子树。将左右子树分别push进栈。继续循环。

本题无论采用什么方式遍历树，只要保证每个节点只访问一次，在访问节点的时候交换左右子树，都能得到正确的结果。

方法一：

1 void swap( BSTree *left, BSTree *right )//这里用的是指针的指针，我更偏向指针的引用传递 2 { 3 　　　　BSTree p = *left; 4 　　　　*left = *right; 5 　　　　*right = p; 6 } 7  8 void Function( BSTree T ) 9 {10 　　if ( T )11 　　{12 　　    swap( &( T-> left ), &( T-> right ) );13 　　    Mirror( T-> left );14 　　    Mirror( T-> right );15 　　}16 }

方法二：

1 void Function( BSTree T ) 2 { 3 　　if (T) 4 　　{ 5 　　　　stack< BSTree > S; 6 　　　　buf.push( T ); 7 　　　　while ( !stack.empty() )  // 这里用队列也可以 8 　　　　{ 9 　　　　　　BSTree p = stack.pop();10 　　　　　　swap( &( p-> left ), &( p-> right ) );11 　　　　　　if ( p->left )12 　  　　　　　　buf.push( p-> left );13 　　　　　　if ( p-> right )14 　　　　　　　　buf.push( p-> right );15 　　　　}16 　　}17 }