完成一个函数，输入一个二叉树，该函数输出它的镜像
struct BinaryTreeNode
{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; void MirrorRecursive(BinaryTreeNode *pNode) { if((pNode == NULL) || (pNode->m_pLeft == NULL && pNode->m_pRight == NULL)) return; BinaryTreeNode* pTemp = pNode->m_pLeft; pNode->m_pLeft = pNode->m_pRight; pNode->m_pRight = pTemp; if(pNode->m_pLeft) MirrorRecursive(pNode->m_pLeft); if(pNode->m_pRight) MirrorRecursive(pNode->m_pRight); } void MirrorIterative(BinaryTreeNode* pRoot) { if(pRoot == NULL) return; stack<BinaryTreeNode*>stackTreeNode; stackTreeNode.push(pRoot); while(stackTreeNode.size() > 0) { BinaryTreeNode* pNode = stackTreeNode.top(); stackTreeNode.pop(); BinaryTreeNode* pTemp = pNode->m_pLeft; pNode->m_pLeft = pNode->m_pRight; pNode->m_pRight = pTemp; if(pNode->m_pLeft) stackTreeNode.push(pNode->m_pLeft); if(pNode->m_pRight) stackTreeNode.push(pNode->m_pRight); } } BinaryTreeNode* CreateBinaryTreeNode(int value) { BinaryTreeNode* pNode = new BinaryTreeNode(); pNode->m_nValue = value; pNode->m_pLeft = NULL; pNode->m_pRight = NULL; return pNode; } void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight) { if(pParent != NULL) { pParent->m_pLeft = pLeft; pParent->m_pRight = pRight; } } void PrintTreeNode(BinaryTreeNode* pNode) { if(pNode != NULL) { printf("value of this node is: %d\n", pNode->m_nValue); if(pNode->m_pLeft != NULL) printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue); else printf("left child is null.\n"); if(pNode->m_pRight != NULL) printf("value of its right child is: %d.\n", pNode->m_pRight->m_nValue); else printf("right child is null.\n"); } else { printf("this node is null.\n"); } printf("\n"); } void PrintTree(BinaryTreeNode* pRoot) { PrintTreeNode(pRoot); if(pRoot != NULL) { if(pRoot->m_pLeft != NULL) PrintTree(pRoot->m_pLeft); if(pRoot->m_pRight != NULL) PrintTree(pRoot->m_pRight); } } void DestroyTree(BinaryTreeNode* pRoot) { if(pRoot != NULL) { BinaryTreeNode* pLeft = pRoot->m_pLeft; BinaryTreeNode* pRight = pRoot->m_pRight; delete pRoot; pRoot = NULL; DestroyTree(pLeft); DestroyTree(pRight); } } void Test1() { printf("=====Test1 starts:=====\n"); BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8); BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6); BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10); BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5); BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7); BinaryTreeNode* pNode9 = CreateBinaryTreeNode(9); BinaryTreeNode* pNode11 = CreateBinaryTreeNode(11); ConnectTreeNodes(pNode8, pNode6, pNode10); ConnectTreeNodes(pNode6, pNode5, pNode7); ConnectTreeNodes(pNode10, pNode9, pNode11); PrintTree(pNode8); printf("=====Test1: MirrorRecursively=====\n"); MirrorRecursive(pNode8); PrintTree(pNode8); printf("=====Test1: MirrorIteratively=====\n"); MirrorIterative(pNode8); PrintTree(pNode8); DestroyTree(pNode8); } void Test2() { printf("=====Test2 starts:=====\n"); BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8); BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7); BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6); BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5); BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4); ConnectTreeNodes(pNode8, pNode7, NULL); ConnectTreeNodes(pNode7, pNode6, NULL); ConnectTreeNodes(pNode6, pNode5, NULL); ConnectTreeNodes(pNode5, pNode4, NULL); PrintTree(pNode8); printf("=====Test2: MirrorRecursively=====\n"); MirrorRecursive(pNode8); PrintTree(pNode8); printf("=====Test2: MirrorIteratively=====\n"); MirrorIterative(pNode8); PrintTree(pNode8); DestroyTree(pNode8); } void Test3() { printf("=====Test3 starts:=====\n"); BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8); BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7); BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6); BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5); BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4); ConnectTreeNodes(pNode8, NULL, pNode7); ConnectTreeNodes(pNode7, NULL, pNode6); ConnectTreeNodes(pNode6, NULL, pNode5); ConnectTreeNodes(pNode5, NULL, pNode4); PrintTree(pNode8); printf("=====Test3: MirrorRecursively=====\n"); MirrorRecursive(pNode8); PrintTree(pNode8); printf("=====Test3: MirrorIteratively=====\n"); MirrorIterative(pNode8); PrintTree(pNode8); DestroyTree(pNode8); } void Test4() { printf("=====Test4 starts:=====\n"); BinaryTreeNode* pNode = NULL; PrintTree(pNode); printf("=====Test4: MirrorRecursively=====\n"); MirrorRecursive(pNode); PrintTree(pNode); printf("=====Test4: MirrorIteratively=====\n"); MirrorIterative(pNode); PrintTree(pNode); } void Test5() { printf("=====Test5 starts:=====\n"); BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8); PrintTree(pNode8); printf("=====Test4: MirrorRecursively=====\n"); MirrorRecursive(pNode8); PrintTree(pNode8); printf("=====Test4: MirrorIteratively=====\n"); MirrorIterative(pNode8); PrintTree(pNode8); } int main() { Test1(); Test2(); Test3(); Test4(); Test5(); return 0; }