程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++算法之 判斷是否為平衡二叉樹 求二叉樹的鏡像

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

編輯: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<


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved