歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

二叉樹鏡像

題目描述:

輸入一個二叉樹,輸出其鏡像。

九度OJ的測試很蛋疼啊~ 這裡,我先寫一個求二叉樹鏡像的代碼,使用自己的測試代碼: 思路很簡單:先判斷是否左右孩子都為空,如果不是,則交換,然後遞歸左右子樹。其實是先序遍歷。

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm

/*
二叉樹鏡像
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;
}

Copyright © Linux教程網 All Rights Reserved