C++アルゴリズムの判断は平衡二叉樹で二叉樹の鏡像を求めるかどうか

1:バランスツリーかどうかを判断する:

//  1：
int TreeDepth(BTree* pRoot)
{
	if (pRoot == NULL)
		return 0;
	int nLeftDepth = TreeDepth(pRoot->m_pLeft);
	int nRightDepth = TreeDepth(pRoot->m_pRight);

	return (nLeftDepth > nRightDepth)? (nLeftDepth+1):(nRightDepth+1);
}

bool IsBalanced(BTree* pRoot)
{
	if (pRoot == NULL)
		return true;
	int nLeftDepth = TreeDepth(pRoot->m_pLeft);
	int nRightDepth = TreeDepth(pRoot->m_pRight);
	int diff = nRightDepth - nLeftDepth;
	if (diff > 1 || diff < -1)
		return false;

	return IsBalanced(pRoot->m_pLeft)&&IsBalanced(pRoot->m_pRight);
	
}
/*
     ：                     ，                 
     ，      ！
*/
bool IsBalanced3(BTree* pRoot, int& depth)
{
	if(pRoot== NULL)
	{
		depth = 0;
		return true;
	}

	int nLeftDepth;
	bool bLeft= IsBalanced3(pRoot->m_pLeft, nLeftDepth);
	int nRightDepth;
	bool bRight = IsBalanced3(pRoot->m_pRight, nRightDepth);
	
	if (bLeft && bRight && abs(nLeftDepth - nRightDepth) <=1)
	{
		depth = 1+(nLeftDepth > nRightDepth ? nLeftDepth : nRightDepth);
		return true;	
	}
	else
	{
		return false;
	}
}

bool IsBalanced3(BTree* pRoot)
{
	int depth = 0;
	return IsBalanced3(pRoot, depth);
}

2:ツリーのミラーリングを求めます

/*
       ：

  1：         ，            ，          。（          ，               ）
  2：         ，           ，            

*/

void Mirror(BTree* &pRoot)
{
	if(pRoot == NULL)
		return;
	if(pRoot->m_pLeft ==NULL && pRoot->m_pRight == NULL)
		return;

	BTree* pTemp = pRoot->m_pLeft;
	pRoot->m_pLeft = pRoot->m_pRight;
	pRoot->m_pRight = pTemp;

	if(pRoot->m_pLeft)
		Mirror(pRoot->m_pLeft);
	if(pRoot->m_pRight)
		Mirror(pRoot->m_pRight);
}

BTree* Mirror2(BTree* pRoot)
{
	if(pRoot == NULL)
		return NULL;

	BTree*  pLeft = Mirror2(pRoot->m_pLeft);
	BTree*  pRight = Mirror2(pRoot->m_pRight);


	pRoot->m_pLeft = pRight;
	pRoot->m_pRight = pLeft;

	return pRoot;
}

完全なテストコード:

// BalanceOfBT.cpp :              。
//

#include "stdafx.h"
#include 
using namespace std;

class BTree
{
public:
	int     m_nValue;
	BTree*  m_pLeft;
	BTree*  m_pRight;

	BTree(int m):m_nValue(m)
	{
		m_pLeft = m_pRight = NULL;
	}

};
//        
void Insert(int value, BTree* &root)
{
	if (root == NULL)
	{
		root = new BTree(value);
	}
	else if(value < root->m_nValue)
		Insert(value,root->m_pLeft);
	else if(value > root->m_nValue)
		Insert(value,root->m_pRight);
	else
		;
}

//  1：
int TreeDepth(BTree* pRoot)
{
	if (pRoot == NULL)
		return 0;
	int nLeftDepth = TreeDepth(pRoot->m_pLeft);
	int nRightDepth = TreeDepth(pRoot->m_pRight);

	return (nLeftDepth > nRightDepth)? (nLeftDepth+1):(nRightDepth+1);
}

bool IsBalanced(BTree* pRoot)
{
	if (pRoot == NULL)
		return true;
	int nLeftDepth = TreeDepth(pRoot->m_pLeft);
	int nRightDepth = TreeDepth(pRoot->m_pRight);
	int diff = nRightDepth - nLeftDepth;
	if (diff > 1 || diff < -1)
		return false;

	return IsBalanced(pRoot->m_pLeft)&&IsBalanced(pRoot->m_pRight);
	
}
/*
     ：                     ，                 
     ，      ！
*/
bool IsBalanced3(BTree* pRoot, int& depth)
{
	if(pRoot== NULL)
	{
		depth = 0;
		return true;
	}

	int nLeftDepth;
	bool bLeft= IsBalanced3(pRoot->m_pLeft, nLeftDepth);
	int nRightDepth;
	bool bRight = IsBalanced3(pRoot->m_pRight, nRightDepth);
	
	if (bLeft && bRight && abs(nLeftDepth - nRightDepth) <=1)
	{
		depth = 1+(nLeftDepth > nRightDepth ? nLeftDepth : nRightDepth);
		return true;	
	}
	else
	{
		return false;
	}
}

bool IsBalanced3(BTree* pRoot)
{
	int depth = 0;
	return IsBalanced3(pRoot, depth);
}

/*
       ：

  1：         ，            ，          。（          ，               ）
  2：         ，           ，            

*/

void Mirror(BTree* &pRoot)
{
	if(pRoot == NULL)
		return;
	if(pRoot->m_pLeft ==NULL && pRoot->m_pRight == NULL)
		return;

	BTree* pTemp = pRoot->m_pLeft;
	pRoot->m_pLeft = pRoot->m_pRight;
	pRoot->m_pRight = pTemp;

	if(pRoot->m_pLeft)
		Mirror(pRoot->m_pLeft);
	if(pRoot->m_pRight)
		Mirror(pRoot->m_pRight);
}

BTree* Mirror2(BTree* pRoot)
{
	if(pRoot == NULL)
		return NULL;

	BTree*  pLeft = Mirror2(pRoot->m_pLeft);
	BTree*  pRight = Mirror2(pRoot->m_pRight);


	pRoot->m_pLeft = pRight;
	pRoot->m_pRight = pLeft;

	return pRoot;
}

void PrintPrev(BTree* pRoot)
{
	if(pRoot == NULL)
		return;

	cout<m_nValue<m_pLeft);
	PrintPrev(pRoot->m_pRight);
}






int _tmain(int argc, _TCHAR* argv[])
{

	BTree* m_pRoot = new BTree(9);
	Insert(3,m_pRoot);
	Insert(6,m_pRoot);
	Insert(1,m_pRoot);
	Insert(2,m_pRoot);
	Insert(5,m_pRoot);
	Insert(8,m_pRoot);
	Insert(7,m_pRoot);
	Insert(10,m_pRoot);

	cout<