C++算法之 判斷是否為平衡二叉樹 求二叉樹的鏡像

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<<" ";
	PrintPrev(pRoot->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<