题目
请完成一个函数，输入一棵二叉树，该函数输出它的镜像。二叉树节点的定义如下：
typedef int TElemType; /* 树结点的数据类型，目前暂定为整型 */ struct BianryTreeNode { TElemType m_nValue; BianryTreeNode* m_pLeft, * m_pRight;//左右孩子节点 };
分析
先画出一对二叉树，并写出三序列遍历结果，一会用于判断新的二叉树是否为原二叉树的镜像。观察下图，发现就是左右对调，本质就是依次交换该节点的左右子节点遇到空为止。
递归法
C++
#include <iostream> using namespace std; typedef int TElemType; /* 树结点的数据类型，目前暂定为整型 */ struct BinaryTreeNode { TElemType m_nValue; BinaryTreeNode* m_pLeft, * m_pRight;//左右孩子节点 }; void CreatTree(BinaryTreeNode** T) { TElemType elem; cin >> elem; if (elem != 999) { *T = new BinaryTreeNode(); if (NULL == T) { return; } (*T)->m_nValue = elem; CreatTree(&((*T)->m_pLeft)); CreatTree(&((*T)->m_pRight)); } else { *T = nullptr; } } void Print(TElemType n) { cout << n << " "; } void Preorder(BinaryTreeNode* root)//前序遍历 { if (NULL == root) { return; } Print(root->m_nValue); Preorder(root->m_pLeft); Preorder(root->m_pRight); } void Inorder(BinaryTreeNode* root)//中序输出 { if (NULL == root) { return; } Inorder(root->m_pLeft); Print(root->m_nValue); Inorder(root->m_pRight); } void Postorder(BinaryTreeNode* root)//后续输出 { if (NULL == root) { return; } Postorder(root->m_pLeft); Postorder(root->m_pRight); Print(root->m_nValue); } void MirrorRecursively(BinaryTreeNode* pNode)//二叉树的镜像 { //当前节点为空，或者没有子树了。 if ((nullptr == pNode) || (nullptr == pNode->m_pLeft && nullptr == pNode->m_pRight)) { return; } //交换左右子树 BinaryTreeNode* tmp = pNode->m_pLeft; pNode->m_pLeft = pNode->m_pRight; pNode->m_pRight = tmp; //调用自己的左子树 MirrorRecursively(pNode->m_pLeft); //调用自己的右子树 MirrorRecursively(pNode->m_pRight); } int main() { BinaryTreeNode* root = nullptr; cout << "请按照先序遍历规则输入节点值(输入999表示当前为空)：" << endl; CreatTree(&root); printf("先序输出:"); Preorder(root); printf("\n中序输出:"); Inorder(root); printf("\n后序输出:"); Postorder(root); MirrorRecursively(root); cout << "\n--------------二叉树的镜像---------" << endl; printf("先序输出:"); Preorder(root); printf("\n中序输出:"); Inorder(root); printf("\n后序输出:"); Postorder(root); }
测试结果如下，与上图对比发现完全一致。
本章完!
