二叉树镜像

二叉树镜像

题目描述：

输入一个二叉树，输出其镜像。

九度OJ的测试很蛋疼啊~ 这里，我先写一个求二叉树镜像的代码，使用自己的测试代码： 思路很简单：先判断是否左右孩子都为空，如果不是，则交换，然后递归左右子树。其实是先序遍历。

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

/*
二叉树镜像
by Rowandjj
2014/8/1
*/
#include<iostream>
using namespace std;
typedef struct _BNODE_
{
 int data;
 struct _BNODE_ *lChild;
 struct _BNODE_ *rChild;
}BNode,*pTree;
//求二叉树镜像,先序遍历的方式
//先判断是否左右孩子都为空，如果不是，则交换，然后递归左右子树
void getMirror(pTree pT)
{
 if(pT == NULL)
 {
  return;
 }
 if(pT->lChild==NULL && pT->rChild==NULL)
 {
  return;
 }
 //交换
 BNode *temp = pT->lChild;
 pT->lChild = pT->rChild;
 pT->rChild = temp;
 //递归
 if(pT->lChild)
 {
  getMirror(pT->lChild);
 }
 if(pT->rChild)
 {
  getMirror(pT->rChild);
 }
}
void Create(pTree *ppTree)
{
 int data;
 cin>>data;
 
 if(data != -1)
 {
  *ppTree = (BNode*)malloc(sizeof(BNode));
  if(*ppTree == NULL)
  {
   exit(-1);
  }
  (*ppTree)->data = data;
  (*ppTree)->lChild = NULL;
  (*ppTree)->rChild = NULL;
  Create(&(*ppTree)->lChild);
  Create(&(*ppTree)->rChild);
 }
}
//先序遍历
void PreTraverse(pTree pT)
{
 if(!pT)
 {
  return;
 }
 cout<<pT->data<<" ";
 if(pT->lChild)
  PreTraverse(pT->lChild);
 if(pT->rChild)
  PreTraverse(pT->rChild);
}
int main()
{
 pTree pT = NULL;
 Create(&pT);
 PreTraverse(pT);
 cout<<"\n---------------------\n";
 getMirror(pT);
 PreTraverse(pT);
 return 0;
}

本文永久更新链接地址：