欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

网易游戏面试题 如何判断一棵二叉树是AVL(平衡二叉树)

程序员文章站 2022-05-16 11:24:07
...

一棵树是否是AVL,则只要这棵二叉树满足是BST并且每个结点的平衡因子都满足在1、0、-1的范围。则符合条件。

核心代码如下:

template <typename keyType>
bool is_AVL(BT<keyType> &bt){
	return is_AVL_Core(bt.root);
}

template <typename keyType>
bool is_AVL_Core(BinaryTreeNode<keyType> *root){
	return is_BST(root,INT_MIN,INT_MAX) && is_balance(root);
}

template <typename keyType>
bool is_BST(BinaryTreeNode<keyType> *root,keyType min,keyType max){//判断是否是BST 
	if(root == nullptr)
		return true;
	if(root->value < min || root->value > max)
		return false;
	return is_BST(root->m_pLeft,min,root->value - 1) && is_BST(root->m_pRight,root->value + 1,max);
}
	
template <typename keyType>
bool is_balance(BinaryTreeNode<keyType> *root){//判断二叉树平衡因子是否满足 
	if(root == nullptr)
		return true;
	if(BT<keyType>::diff(root) > 1 || BT<keyType>::diff(root) < -1)
		return false;
	return is_balance(root->m_pLeft) && is_balance(root->m_pRight);
}
template <typename keyType>
int BT<keyType>::getHeight(){
	_getHeight(root);	 
} 

template <typename keyType>
int BT<keyType>::_getHeight(BTNode *root){//获取结点高度 
	if(root == nullptr)
		return 0;
	return max(_getHeight(root->m_pLeft),_getHeight(root->m_pRight))+1;
} 

template <typename keyType>
int BT<keyType>::diff(BTNode *root){//计算结点平衡因子 
	if(root == nullptr)
		return 0;
	return _getHeight(root->m_pLeft) - _getHeight(root->m_pRight);
}

程序完整代码如下:

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
template <typename keyType>//之后的类名一定要记得加上<typename> 
class BinaryTreeNode{
public:
	keyType value;
	BinaryTreeNode *m_pLeft;
	BinaryTreeNode *m_pRight;
	BinaryTreeNode(keyType v):value(v),m_pLeft(nullptr),m_pRight(nullptr){}
};

//AVL树 
template <typename keyType>
class BT{
	typedef BinaryTreeNode<keyType> BTNode;//给结点定义别名 
public:
	BT(){ root = nullptr; }//默认构造函数
	
	BTNode * insertBTNode(BTNode *&root,keyType val);
	BTNode *createBT(keyType arr[],int n);//通过数组创建二叉排序树,通过*&来改变指针的值
	BTNode *createBT_ByQue(queue<keyType> que);//通过队列创建二叉排序树
	
	
	BTNode *search_AVL(keyType v);
	BTNode *search_AVL_Core(BTNode *root,keyType v);
 
	void midorder_showBT();//中序遍历 
	void midorder_showBT_core(const BTNode *root); 
	
	void level_showBT();//中序遍历 
	void level_showBT_core(BTNode *root);
	
	~BT();//析构函数 
	void release_BT_core(BTNode *root);	
	
	static int _getHeight(BTNode *root);
	int getHeight();//获取高度
	
	static int diff(BTNode *root);//计算平衡因子
	
	static BTNode *balance(BTNode *root);//平衡操作 
	
	static BTNode *LL_Rotation(BTNode *root);//LL旋转 
	static BTNode *LR_Rotation(BTNode *root);
	static BTNode *RL_Rotation(BTNode *root);
	static BTNode *RR_Rotation(BTNode *root);
	
	queue<keyType> get_AVL_Node();
	void get_AVL_Node_Core(queue<keyType> &que,BTNode *root);
					
	BTNode *root;	
};

int INT_MIN = -99999,INT_MAX = 99999; 

template <typename keyType>
//注意这里要是引用，不然析构时会出错 
bool is_AVL(BT<keyType> &bt);//判断是否是平衡二叉树 

template <typename keyType>
bool is_AVL_Core(BinaryTreeNode<keyType> *root);

template <typename keyType>
bool is_BST(BinaryTreeNode<keyType> *root,keyType min,keyType max);


template <typename keyType>
bool is_balance(BinaryTreeNode<keyType> *root);
 
int main(){
	
	BT<int> bt;
	
	int arr[] = {16,3,7,11,9,26,18,14,15};
	bt.createBT(arr,sizeof(arr)/sizeof(arr[0]));//构建二叉排序树 
	
	cout<<"中序遍历:"<<endl;
	bt.midorder_showBT();//中序遍历打印 
	cout<<endl<<endl;
	
	cout<<"层次遍历:"<<endl;
	bt.level_showBT();//前序遍历打印 
	cout<<endl<<endl;
	
	
	if(is_AVL(bt))//可通过把构建AVL树过程中的balance函数注释掉，则看到不是AVL树 
		cout<<"是平衡二叉树"<<endl;
	else
		cout<<"不是平衡二叉树"<<endl;
		
	return 0;
}

template <typename keyType>
bool is_AVL(BT<keyType> &bt){
	return is_AVL_Core(bt.root);
}

template <typename keyType>
bool is_AVL_Core(BinaryTreeNode<keyType> *root){
	return is_BST(root,INT_MIN,INT_MAX) && is_balance(root);
}

template <typename keyType>
bool is_BST(BinaryTreeNode<keyType> *root,keyType min,keyType max){//判断是否是BST 
	if(root == nullptr)
		return true;
	if(root->value < min || root->value > max)
		return false;
	return is_BST(root->m_pLeft,min,root->value - 1) && is_BST(root->m_pRight,root->value + 1,max);
}
	
template <typename keyType>
bool is_balance(BinaryTreeNode<keyType> *root){//判断二叉树平衡因子是否满足 
	if(root == nullptr)
		return true;
	if(BT<keyType>::diff(root) > 1 || BT<keyType>::diff(root) < -1)
		return false;
	return is_balance(root->m_pLeft) && is_balance(root->m_pRight);
}

template <typename keyType>
BinaryTreeNode<keyType> *BT<keyType>::createBT(keyType arr[],int n){
	root = nullptr;
	for(int i=0;i<n;i++)
		insertBTNode(root,arr[i]);
	return root;	
}

template <typename keyType>
BinaryTreeNode<keyType> *BT<keyType>::createBT_ByQue(queue<keyType> que){
	root = nullptr;
	while(!que.empty()){
		insertBTNode(root,que.front());
		que.pop();
	}
	return 	root;
}

template <typename keyType>
BinaryTreeNode<keyType> * BT<keyType>::insertBTNode(BTNode *&root,keyType val){
	if(root == nullptr){
		root = new BTNode(val);
		return root;	
	}
	if(val == root->value){
		return root;
		
	}
	else if(val < root->value){
		root->m_pLeft = insertBTNode(root->m_pLeft,val);
		root = balance(root); //注意这里是把平衡后的返回置temp赋值给root 
		return root;
	}
	else{
		root->m_pRight = insertBTNode(root->m_pRight,val);
		root = balance(root); //注意这里是把平衡后的返回置temp赋值给root 
		return root;	
	}			
}

template <typename keyType>
BinaryTreeNode<keyType> *BT<keyType>::balance(BTNode *root){
	int dis = diff(root);//计算结点的平衡因子 
	
	if(dis > 1){//左 
		if( diff(root->m_pLeft) > 0)
			return LL_Rotation(root);
		else
			return LR_Rotation(root);
	} 
	else if(dis < -1){//右 
		if( diff(root->m_pRight) < 0)
			return RR_Rotation(root);
		else
			return RL_Rotation(root);
	}
	
	return root;//无需转换时记得返回root 
}

template <typename keyType>
BinaryTreeNode<keyType> *BT<keyType>::LL_Rotation(BTNode *root){
	BTNode *temp = root->m_pLeft;
	root->m_pLeft = temp->m_pRight;
	temp->m_pRight = root;
	return temp;//返回要旋转子树的主结点 
}

template <typename keyType>
BinaryTreeNode<keyType> *BT<keyType>::RR_Rotation(BTNode *root){
	BTNode *temp = root->m_pRight;
	root->m_pRight = temp->m_pLeft;
	temp->m_pLeft = root;
	return temp;
}

template <typename keyType>
BinaryTreeNode<keyType> *BT<keyType>::LR_Rotation(BTNode *root){//先进行RR操作，再进行LL操作 
	
	//注意这里一定要对root->m_Pleft重新赋值 
	root->m_pLeft = RR_Rotation(root->m_pLeft);//先对root后的左结点进行RR操作 
	return LL_Rotation(root);//再对root进行LL操作 
}

template <typename keyType>
BinaryTreeNode<keyType> *BT<keyType>::RL_Rotation(BTNode *root){//先进行LL操作，再进行RR操作 

	//注意这里一定要对root->m_pRight重新赋值 
	root->m_pRight = LL_Rotation(root->m_pRight);//先对root后的右结点进行LL操作 
	return RR_Rotation(root);//再对root进行RR操作 
}

template <typename keyType>
void BT<keyType>::midorder_showBT(){
	midorder_showBT_core(root);
}

template <typename keyType>
void BT<keyType>::midorder_showBT_core(const BTNode *root){
	if(root == nullptr){
		return;
	}	
	
	midorder_showBT_core(root->m_pLeft);
	cout<<root->value<<" ";
	midorder_showBT_core(root->m_pRight);
}

template <typename keyType>
void BT<keyType>::level_showBT()//中序遍历
{
	level_showBT_core(root);
}

template <typename keyType>
void BT<keyType>::level_showBT_core(BTNode *root){
	if(root == nullptr)
		return;
	queue<BinaryTreeNode<keyType> *> que;
	que.push(root);
	while(!que.empty()){
		
		if( que.front()->m_pLeft != nullptr)
			que.push(que.front()->m_pLeft);
			
		if(que.front()->m_pRight != nullptr)
			que.push(que.front()->m_pRight);
			
		cout<<que.front()->value<<" ";
		que.pop();
	}
}

template <typename keyType>
BT<keyType>::~BT()//释放二叉树 
{
	release_BT_core(root);
}

template <typename keyType>
void BT<keyType>::release_BT_core(BTNode *root)//释放二叉树 
{
	if(root == nullptr)
		return;
	release_BT_core(root->m_pLeft);
	release_BT_core(root->m_pRight);
	delete root;
	root = nullptr;
	return ;
}

template <typename keyType>
int BT<keyType>::getHeight(){
	_getHeight(root);	 
} 

template <typename keyType>
int BT<keyType>::_getHeight(BTNode *root){//获取结点高度 
	if(root == nullptr)
		return 0;
	return max(_getHeight(root->m_pLeft),_getHeight(root->m_pRight))+1;
} 

template <typename keyType>
int BT<keyType>::diff(BTNode *root){//计算结点平衡因子 
	if(root == nullptr)
		return 0;
	return _getHeight(root->m_pLeft) - _getHeight(root->m_pRight);
}

template <typename keyType>
queue<keyType> BT<keyType>::get_AVL_Node()//获取AVL树的所有结点值并返回 
{
	
	queue<keyType> que;
	get_AVL_Node_Core(que,root);
	return que;
}

template <typename keyType>
void BT<keyType>::get_AVL_Node_Core(queue<keyType> &que,BTNode *root)//获取AVL树的所有结点值并返回 
{
	if(root == nullptr)
		return ;
	
	get_AVL_Node_Core(que,root->m_pLeft);
	que.push(root->value);
	get_AVL_Node_Core(que,root->m_pRight);
}

//查找结点，AVLTree查找的复杂度能控制在对数范围O(log n)
template <typename keyType>
BinaryTreeNode<keyType> *BT<keyType>::search_AVL(keyType v){
	return search_AVL_Core(root,v);
}

template <typename keyType>
BinaryTreeNode<keyType> *BT<keyType>::search_AVL_Core(BTNode *root,keyType v){
	if(root == nullptr)
		return nullptr;
	if(v == root->value)
		return root;
	else if(v < root->value)
		search_AVL_Core(root->m_pLeft,v);
	else
		search_AVL_Core(root->m_pRight,v);
}

运行结果如下:

网易游戏面试题 如何判断一棵二叉树是AVL(平衡二叉树)


上一篇： 如何将cv2.imread与keras image.img_load输出相匹配？

下一篇： PIL.Image.open与cv2.imread格式问题

推荐阅读