Problem
How to mirror a binary tree
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Mirror a tree
Created Date : 04-10-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <cassert>
using namespace std;
typedef struct binTreeNode
{
int value;
struct binTreeNode *left;
struct binTreeNode *right;
} BinTreeNode;
BinTreeNode *CreateNode(int value)
{
auto node = new BinTreeNode;
node->value = value;
node->left = nullptr;
node->right = nullptr;
return node;
}
BinTreeNode *AddNode(BinTreeNode* head, int value)
{
if(head->value > value){
if(head->left == nullptr){
BinTreeNode* node = CreateNode(value);
head->left = node;
}
else{
AddNode(head->left, value);
}
}
else{
if(head->right == nullptr){
BinTreeNode* node = CreateNode(value);
head->right = node;
}
else{
AddNode(head->right, value);
}
}
return head;
}
void PrintTree(BinTreeNode* head)
{
if(head == nullptr) return;
if(head->left != nullptr) PrintTree(head->left);
cout << head->value << endl;
if(head->right != nullptr) PrintTree(head->right);
}
BinTreeNode* CreateTree(int* arr, int len)
{
assert(arr != nullptr && len >= 1);
BinTreeNode* head = CreateNode(arr[0]);
for(int i = 1; i < len; ++i){
AddNode(head, arr[i]);
}
return head;
}
void MirrorTree(BinTreeNode* head)
{
if(head == nullptr) return;
swap(head->left, head->right);
MirrorTree(head->left);
MirrorTree(head->right);
}
int main(int argc, char* argv[])
{
int arr[] = {3, 1, 2, 5, 6, 4};
BinTreeNode* head = CreateTree(arr, sizeof(arr) / sizeof(arr[0]));
cout << "Before mirroring " << endl;
PrintTree(head);
MirrorTree(head);
cout << "After mirroring " << endl;
PrintTree(head);
return 0;
}
Output
Before mirroring
1
2
3
4
5
6
After mirroring
6
5
4
3
2
1
Press any key to continue . . .