二叉树的镜像

镜像：右树由左树产生，像是从镜子中看。

#include<iostream>
#include<stack>
using namespace std;
struct BinaryTreeNode
{
	int data;
	BinaryTreeNode* left;
	BinaryTreeNode* right;
	BinaryTreeNode(int x)
		:data(x)
		, left(NULL)
		, right(NULL)
	{}
};
class BinaryTree
{
protected:
	BinaryTreeNode* _root;
	BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size)
	{
		BinaryTreeNode* root = NULL;
		if (index<size&&arr[index] != ‘#‘)
		{
			root = new BinaryTreeNode(arr[index]);
			root->left = _CreateBinaryTree(arr, ++index, size);
			root->right = _CreateBinaryTree(arr, ++index, size);
		}
		return root;
	}
	BinaryTreeNode* _CopyMirrorint(BinaryTreeNode* root)
	{
		if (root == NULL)
			return NULL;
		BinaryTreeNode* tmp = new BinaryTreeNode(root->data);
		tmp->left = _CopyMirrorint(root->right);
		tmp->right= _CopyMirrorint(root->left);
		return tmp;
	}
public:
	BinaryTree()
		:_root(NULL)
	{}
	BinaryTree(int *arr, int size)
	{
		int index = 0;
		_root = _CreateBinaryTree(arr, index, size);
	}
	void PreOrder_Non()
	{
		if (_root == NULL)
			return;
		BinaryTreeNode* cur = _root;
		stack<BinaryTreeNode*> s;
		s.push(_root);
		while (!s.empty())
		{
			cur= s.top();
			printf("%d ", cur->data);
			s.pop();
			if (cur->right)
				s.push(cur->right);
			if (cur->left)
				s.push(cur->left);
		}
		cout << endl;
	}
	void InOrder_Non()
	{
		if (_root == NULL)
			return;
		stack<BinaryTreeNode*> s;
		BinaryTreeNode* cur = _root;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->left;
			}
			if (!s.empty())
			{
				cout << s.top()->data << " ";
				cur = s.top()->right;
				s.pop();
			}
		}
		cout << endl;
	}
	void PostOrder_Non()
	{
		if (_root == NULL)
			return;
		stack<BinaryTreeNode*> s;
		BinaryTreeNode* cur = _root;
		BinaryTreeNode* prev = NULL;
		BinaryTreeNode* top = NULL;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->left;
			}
			top = s.top();
			if (top->right == NULL || top->right == prev)
			{
				cout << top->data << " ";
				s.pop();
				prev = top;
			}
			else
			{
				cur = top->right;
			}
		}
		cout << endl;
	}
	void  CopyMirroring(BinaryTree& b)
	{
		_root = _CopyMirrorint(b._root);
	}
};

void Test1()
{
	int arr[] = { 1, 2, 4, ‘#‘, ‘#‘, 5, ‘#‘, ‘#‘, 3, 6, ‘#‘, ‘#‘, 7 };
	BinaryTree bt1(arr, sizeof(arr) / sizeof(arr[0]));
	BinaryTree bt2;
	bt1.InOrder_Non();
	bt1.PostOrder_Non();
	bt2.CopyMirroring(bt1);
	bt2.PostOrder_Non();
}

本文出自 “小止” 博客，请务必保留此出处http://10541556.blog.51cto.com/10531556/1768768

二叉树的镜像

原文：http://10541556.blog.51cto.com/10531556/1768768