【C/C++练习题】二叉树的镜像

《剑指Offer》面试题27：二叉树的镜像

1 题目

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

2 代码

      #include "iostream"
      #include "cstdlib"
      using namespace std;
      //问题：二叉树的镜像
      typedef struct Node
      {
     	int m_nValue;
      	Node* m_pLeft;
      	Node* m_pRight;
      }BinaryTreeNode;
      //功能：利用递归方式实现打印二叉树的镜像
      //输入：
      //返回：
      void Mirror_btree(BinaryTreeNode* pNode)
      {
     	//1.回归条件1，空指针pNode（也检查参数有效性）
     	if (nullptr == pNode)
      	{
     		return ;
      	}
     	//2.回归条件2，叶子节点
     	if (nullptr == pNode->m_pLeft && nullptr == pNode->m_pRight)
      	{//
     		return ;
      	}
     	//4.至上而下，交换左右子树
      	BinaryTreeNode* pTemp = pNode->m_pLeft;
      	pNode->m_pLeft = pNode->m_pRight;
      	pNode->m_pRight = pTemp;
     	//3.进行递归调用
     	Mirror_btree(pNode->m_pLeft);
     	Mirror_btree(pNode->m_pRight);
      }
      //先序打印二叉树
      void Print_Btree(BinaryTreeNode* pNode)
      {
     	//1.回归条件1，空指针pNode（也检查参数有效性）
     	if (nullptr == pNode)
      	{
     		return ;
      	}
     	//2.打印二叉树
      	cout << pNode->m_nValue << ",";
     	//3.进行递归调用
     	Print_Btree(pNode->m_pLeft);
     	Print_Btree(pNode->m_pRight);
      }
      // ====================测试代码====================
      // 测试完全二叉树：除了叶子节点，其他节点都有两个子节点
      // 8(node1)
      // 6(node2) 10(node3)
      // 5(node4) 7(node5) 9(node6) 11(node7)
      void test01()
      {
      	BinaryTreeNode* node1  = new BinaryTreeNode();
      	BinaryTreeNode* node2  = new BinaryTreeNode();
      	BinaryTreeNode* node3  = new BinaryTreeNode();
      	BinaryTreeNode* node4  = new BinaryTreeNode();
      	BinaryTreeNode* node5  = new BinaryTreeNode();
      	BinaryTreeNode* node6  = new BinaryTreeNode();
      	BinaryTreeNode* node7  = new BinaryTreeNode();
     	//node1
      	node1->m_nValue = 8;
      	node1->m_pLeft = node2;
      	node1->m_pRight = node3;
     	//node2
      	node2->m_nValue = 6;
      	node2->m_pLeft = node4;
      	node2->m_pRight = node5;
     	//node3
      	node3->m_nValue = 10;
      	node3->m_pLeft = node6;
      	node3->m_pRight = node7;
     	//node4
      	node4->m_nValue = 5;
      	node4->m_pLeft = nullptr;
      	node4->m_pRight = nullptr;
     	//node5
      	node5->m_nValue = 7;
      	node5->m_pLeft = nullptr;
      	node5->m_pRight = nullptr;
     	//node6
      	node6->m_nValue = 9;
      	node6->m_pLeft = nullptr;
      	node6->m_pRight = nullptr;
     	//node7
      	node7->m_nValue = 11;
      	node7->m_pLeft = nullptr;
      	node7->m_pRight = nullptr;
     	//测试部分
     	Print_Btree(node1);
      	cout << endl;
     	Mirror_btree(node1);
     	Print_Btree(node1);
      	cout << endl;
     	delete node1;delete node2;
     	delete node3;delete node4;
     	delete node5;delete node6;
     	delete node7;
      }
      int main(int argc, char const *argv[])
      {
     	test01();
     	return 0;
      }
  
 

3 运行结果

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/99195146