题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入： 8 / / 6 10 / / / / 5 7 9 11
输出： 8 / / 10 6 / / / / 11 9 7 5
定义二元查找树的结点为：
struct BSTreeNode // a node in the binary search tree (BST) { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node };
我们输出的结果是把镜像的二元树进行中序遍历。
思想：主要结合递归，以及层序遍历的思想，交换当前节点的左右子树。
代码如下：
#include<iostream> #include<stack> using namespace std; struct BSTreeNode { int m_nValue; BSTreeNode *m_pleft; BSTreeNode *m_pright; }; void addBSTreeNode(BSTreeNode *&pCurrent, int value); void reverseBSTree1(BSTreeNode *pRoot); void reverseBSTree2(BSTreeNode *pRoot); void inOrderReverseBSTree(BSTreeNode *pRoot); int main() { BSTreeNode *pRoot = NULL; addBSTreeNode(pRoot, 8); addBSTreeNode(pRoot, 6); addBSTreeNode(pRoot, 5); addBSTreeNode(pRoot, 7); addBSTreeNode(pRoot, 10); addBSTreeNode(pRoot, 9); addBSTreeNode(pRoot, 11); reverseBSTree1(pRoot); //reverseBSTree2(pRoot); inOrderReverseBSTree(pRoot); return 0; } void reverseBSTree1(BSTreeNode *pRoot) { if(pRoot == NULL) return ; BSTreeNode *pCurrent; pCurrent = pRoot->m_pleft; pRoot->m_pleft = pRoot->m_pright; pRoot->m_pright = pCurrent; if(pRoot->m_pleft != NULL) reverseBSTree1(pRoot->m_pleft); if(pRoot->m_pright != NULL) reverseBSTree1(pRoot->m_pright); } void inOrderReverseBSTree(BSTreeNode *pRoot) { if(pRoot == NULL) return ; if(pRoot->m_pleft != NULL) inOrderReverseBSTree(pRoot->m_pleft); cout<<pRoot->m_nValue<<" "; if(pRoot->m_pright != NULL) inOrderReverseBSTree(pRoot->m_pright); } void addBSTreeNode(BSTreeNode *&pCurrent, int value) { if(pCurrent == NULL) { BSTreeNode *pBSTree = new BSTreeNode(); pBSTree->m_nValue = value; pBSTree->m_pleft = NULL; pBSTree->m_pright = NULL; pCurrent = pBSTree; } else { if((pCurrent->m_nValue) > value) addBSTreeNode(pCurrent->m_pleft, value); else if((pCurrent->m_nValue) < value) addBSTreeNode(pCurrent->m_pright, value); } } void reverseBSTree2(BSTreeNode *pRoot) { if(pRoot == NULL) return ; stack<BSTreeNode*> v; v.push(pRoot); while(v.size() != 0) { BSTreeNode *pCurrent = v.top(); v.pop(); BSTreeNode *pTemp; pTemp = pCurrent->m_pleft; pCurrent->m_pleft = pCurrent->m_pright; pCurrent->m_pright = pTemp; if(pCurrent->m_pleft != NULL) v.push(pCurrent->m_pleft); if(pCurrent->m_pright != NULL) v.push(pCurrent->m_pright); } }