精华内容
下载资源
问答
  • C语言使用递归创建一平衡二叉树的源代码文件
  • 创建一棵平衡二叉树(C语言)

    千次阅读 2019-10-30 22:03:17
    二叉树树高 叶节点的树高都为1,如果个节点的左右节点的高度不同,则取两者中较大的节点的高度加1为该节点的高度,别忘了加一 这里我们采用递归求节点的高度 int GetHeight(AVLTree AT) { int HL, HR, MaxH; if...

    先来了解一些基本概念

    二叉树树高

    叶节点的树高都为1,如果一个节点的左右节点的高度不同,则取两者中较大的节点的高度加1为该节点的高度,别忘了加一
    树高
    这里我们采用递归求节点的高度

    int GetHeight(AVLTree AT)
    {
    	int HL, HR, MaxH;
    	if (AT)//有这个节点,返回左右子树中较大的那个值再加一
    	{
    		HL = GetHeight(AT->Left);
    		HR = GetHeight(AT->Right);
    		MaxH = HL > HR ? HL : HR;
    		return (MaxH + 1);
    	}
    	else//就是没有这个节点,返回0
    		return 0;
    }
    

    平衡因子

    平衡因子是判断平衡二叉树是否平衡的条件,每个节点的平衡因子都不同,(节点的平衡因子=该节点的左子树第一个节点的高度—该节点的右子树的第一个节点的高度)若无左(右)子树,则左(右)子树的高度为0。平衡二叉树的平衡因子的绝对值<=1,如果某个节点平衡因子的绝对值不满足这个条件,插入的这个节点就为问题节点,这是我们就需要进行调整,调整方法有左单旋,右单旋,左右双旋,右左双旋。
    平衡因子

    调整方法

    这个是二叉树节点的结构体定义

    typedef int ElementType;
    typedef struct AVLNode* AVLTree;
    struct AVLNode//二叉树节点结构体
    {
    	ElementType Data;//节点数据
    	AVLTree Left;
    	AVLTree Right;
    	int Height;//节点高
    };
    

    每当插入一个数据节点后,都要判断二叉树是否平衡,检测到二叉树不平衡,就要通过左单旋,右单旋来调整二叉树使其达到平衡,二叉树的左单旋和右单旋混合使用,可以组成左右双旋和右左双旋

    左单旋

    如图,新插入C节点后A的平衡因子由1变成2,需要进行调整变成平衡二叉树
    左单旋
    下面这种是一般情况左单旋
    这个是实现的代码

    AVLTree SingleLeftRotation(AVLTree A)
    {
    	AVLTree B = A->Left;
    	A->Left = B->Right;
    	B->Right = A;
    	//只需要更新A,B的节点的高度
    	A->Height = MAX(GetHeight(A->Left), GetHeight(A->Right)) + 1;//更新A节点的树高
    	B->Height = MAX(GetHeight(B->Left), A->Height) + 1;//更新B节点的树高
    	return B;
    }
    

    右单旋

    右单旋和左单旋就是对称的情况
    右单旋
    右单旋
    下面是实现的代码

    AVLTree SingleRightRotation(AVLTree A)
    {
    	AVLTree B = A->Right;
    	A->Right = B->Left;
    	B->Left = A;
    	//只需要更新A,B的节点的高度
    	A->Height = MAX(GetHeight(A->Left), GetHeight(A->Right)) + 1;//更新A节点的树高
    	B->Height = MAX(GetHeight(B->Right), A->Height) + 1;//更新B节点的树高
    	return B;
    }
    

    左右双旋

    左右双旋就是先进行右单旋,再进行左单旋,下图是一种简单的情况
    在这里插入图片描述
    下图是左右双旋的一般情况
    左右双旋
    下面是实现的代码,通过调用左单旋和右单旋的函数实现

    AVLTree DoubleLeftRightRotation(AVLTree A)
    {
    	A->Left = SingleRightRotation(A->Left);//先进行右单旋
    	A = SingleLeftRotation(A);//后进行左单旋
    }
    

    右左双旋

    右左双旋
    右左双旋
    下面是实现的代码,先调用左单旋函数,后调用右单旋函数

    AVLTree DoubleRightLeftRotaion(AVLTree A)
    {
    	A->Right = SingleLeftRotation(A->Right);//先进行左单旋
    	A = SingleRightRotation(A);//后进行右单旋
    }
    

    整体代码实现

    本人的设计思路是用户每输入一个数据,都使用递归,当达到最里面一层嵌套时找到节点插入的位置,然后插入节点。随后嵌套逐渐退出,所操作的节点逐渐向根节点靠近,对于每一个所操作的节点都要判断其平衡因子是否符合条件,若不符合则根据不同情况进行调整,每次嵌套结束之前都要更新当前节点的高度,递归结束后二叉树达到平衡,返回二叉树根节点指针。如果用户输入的数据为0,则,输入结束,中序遍历输出二叉树。

    //这是主函数
    int main()
    {
    	int Data;
    	AVLTree AT = NULL;
    	while (1)
    	{
    		scanf_s("%d", &Data);
    		if (!Data)如果输入为0就跳出循环
    			break;
    		AT = VALTreeInsert(AT, Data);//把数据插入二叉树中并做调整
    	}
    	printf("中序遍历输出结果是");
    	InorderTraversal(AT);//中序遍历输出二叉树
    	return 0;
    }
    

    接下来是二叉树的插入操作

    AVLTree VALTreeInsert(AVLTree AT, ElementType Data)
    {
    	if (AT == NULL)//如果这个节点为空,就在这里建立一个节点,相当于把数据插入到二叉树上,接下来要做的就是判断和调整
    	{
    		AT = (AVLTree)malloc(sizeof(struct AVLNode));
    		AT->Data = Data;
    		AT->Left = AT->Right = NULL;//把指针置空
    		AT->Height = 1;//记得置1
    	}
    	else if (Data < AT->Data)//如果要插入的数据的值小于当前节点的值,就插入到该节点的左子树
    	{//递归遍历二叉树然后把数据插入到二叉树里面,此时我们已经跑到二叉树底层了,然后再从底层一点一点的往上返回判断平衡因子,发现不平衡问题就要调整
    		AT->Left = VALTreeInsert(AT->Left, Data);//接着往左子树递归遍历下去
    		if ((GetHeight(AT->Left) - GetHeight(AT->Right)) == 2)//因为是往该节点的左子树中插入数据,如果该节点变成了发现问题的节点,则该节点的平衡因子只能是2,不可能是-2
    		{
    			if (Data < AT->Left->Data)//如果要插入的数据小于该节点的左子树的第一个节点的数据,则表示该数据插入到了该节点的左子树的左边去了,我们要做的就是左单旋
    				AT = SingleLeftRotation(AT);//左单旋
    			else//否则就是插入到该节点的左子树的第一个节点的右边去了,我们要做的是左-右双旋
    				AT = DoubleLeftRightRotation(AT);//左右双旋
    		}
    	}
    	else if (Data > AT->Data)//如果要插入的数据的值大于当前节点的值,就插入到该节点的右子树
    	{
    		AT->Right = VALTreeInsert(AT->Right, Data);
    		if ((GetHeight(AT->Left) - GetHeight(AT->Right)) == -2)//因为是往该节点的右子树中插入数据,如果这个节点变成了发现问题的节点,则该节点的平衡因子只能是-2,不可能是-2
    		{
    			if (Data > AT->Right->Data)//如果要插入的数据大于该节点的右子树的第一个节点的数据,则表示该数据插入到的该节点的右子树的右边去了,我们要做的是右单旋
    				AT = SingleRightRotation(AT);//右单旋
    			else//否则该数据就是插入到了该节点的右子树第一个节点的左边去了,我们要做的是右-左双旋
    				AT = DoubleRightLeftRotaion(AT);//右左双旋
    		}
    	}
    	else//如果要插入的数据的值等于当前节点的值,则输出该值已存在,不进行插入操作
    		printf("该值已存在\n");
    	AT->Height = MAX(GetHeight(AT->Left), GetHeight(AT->Right)) + 1;//插入节点,调整二叉树之后都要更新树的高度,别忘了加1
    	return AT;
    }
    

    得,下面是完整代码

    当然,递归可能会造成较大的空间复杂度,从而无法处理太大的数据量,读者理解了算法之后可以尝试使用非递归实现平衡二叉树

    #include<stdio.h>
    //
    typedef int ElementType;
    typedef struct AVLNode* AVLTree;
    struct AVLNode
    {
    	ElementType Data;
    	AVLTree Left;
    	AVLTree Right;
    	int Height;
    };
    /
    int GetHeight(AVLTree AT);//计算树的高度
    AVLTree VALTreeInsert(AVLTree AT, ElementType Data);//二叉树的插入兼调整操作
    int MAX(int HL, int HR);//取两者中较大的那个数的值
    AVLTree SingleLeftRotation(AVLTree A);//左单旋
    AVLTree SingleRightRotation(AVLTree A);//右单旋
    AVLTree DoubleLeftRightRotation(AVLTree A);//左右双旋
    AVLTree DoubleRightLeftRotaion(AVLTree A);//右左双旋
    void InorderTraversal(AVLTree AT);//中序遍历
    /
    int main()
    {
    	int Data;
    	AVLTree AT = NULL;
    	while (1)
    	{
    		scanf_s("%d", &Data);
    		if (!Data)如果输入为0就跳出循环
    			break;
    		AT = VALTreeInsert(AT, Data);//把数据插入二叉树中并做调整
    	}
    	printf("中序遍历输出结果是");
    	InorderTraversal(AT);//中序遍历输出二叉树
    	return 0;
    }
    int GetHeight(AVLTree AT)
    {
    	int HL, HR, MaxH;
    	if (AT)//有这个节点,返回左右子树中较大的那个值再加一
    	{
    		HL = GetHeight(AT->Left);
    		HR = GetHeight(AT->Right);
    		MaxH = HL > HR ? HL : HR;
    		return (MaxH + 1);
    	}
    	else//就是没有这个节点,返回0
    		return 0;
    }
    AVLTree VALTreeInsert(AVLTree AT, ElementType Data)
    {
    	if (AT == NULL)//如果这个节点为空,就在这里建立一个节点,相当于把数据插入到二叉树上,接下来要做的就是判断和调整
    	{
    		AT = (AVLTree)malloc(sizeof(struct AVLNode));
    		AT->Data = Data;
    		AT->Left = AT->Right = NULL;//把指针置空
    		AT->Height = 1;//记得置1
    	}
    	else if (Data < AT->Data)//如果要插入的数据的值小于当前节点的值,就插入到该节点的左子树
    	{//递归遍历二叉树然后把数据插入到二叉树里面,此时我们已经跑到二叉树底层了,然后再从底层一点一点的往上返回判断平衡因子,发现不平衡问题就要调整
    		AT->Left = VALTreeInsert(AT->Left, Data);//接着往左子树递归遍历下去
    		if ((GetHeight(AT->Left) - GetHeight(AT->Right)) == 2)//因为是往该节点的左子树中插入数据,如果该节点变成了发现问题的节点,则该节点的平衡因子只能是2,不可能是-2
    		{
    			if (Data < AT->Left->Data)//如果要插入的数据小于该节点的左子树的第一个节点的数据,则表示该数据插入到了该节点的左子树的左边去了,我们要做的就是左单旋
    				AT = SingleLeftRotation(AT);//左单旋
    			else//否则就是插入到该节点的左子树的第一个节点的右边去了,我们要做的是左-右双旋
    				AT = DoubleLeftRightRotation(AT);//左右双旋
    		}
    	}
    	else if (Data > AT->Data)//如果要插入的数据的值大于当前节点的值,就插入到该节点的右子树
    	{
    		AT->Right = VALTreeInsert(AT->Right, Data);
    		if ((GetHeight(AT->Left) - GetHeight(AT->Right)) == -2)//因为是往该节点的右子树中插入数据,如果这个节点变成了发现问题的节点,则该节点的平衡因子只能是-2,不可能是-2
    		{
    			if (Data > AT->Right->Data)//如果要插入的数据大于该节点的右子树的第一个节点的数据,则表示该数据插入到的该节点的右子树的右边去了,我们要做的是右单旋
    				AT = SingleRightRotation(AT);//右单旋
    			else//否则该数据就是插入到了该节点的右子树第一个节点的左边去了,我们要做的是右-左双旋
    				AT = DoubleRightLeftRotaion(AT);//右左双旋
    		}
    	}
    	else//如果要插入的数据的值等于当前节点的值,则输出该值已存在,不进行插入操作
    		printf("该值已存在\n");
    	AT->Height = MAX(GetHeight(AT->Left), GetHeight(AT->Right)) + 1;//插入节点,调整二叉树之后都要更新树的高度,别忘了加1
    	return AT;
    }
    int MAX(int HL, int HR)
    {
    	return HL > HR ? HL : HR;
    }
    AVLTree SingleLeftRotation(AVLTree A)
    {
    	AVLTree B = A->Left;
    	A->Left = B->Right;
    	B->Right = A;
    	//只需要更新A,B的节点的高度
    	A->Height = MAX(GetHeight(A->Left), GetHeight(A->Right)) + 1;//更新A节点的树高
    	B->Height = MAX(GetHeight(B->Left), A->Height) + 1;//更新B节点的树高
    	return B;
    }
    AVLTree SingleRightRotation(AVLTree A)
    {
    	AVLTree B = A->Right;
    	A->Right = B->Left;
    	B->Left = A;
    	//只需要更新A,B的节点的高度
    	A->Height = MAX(GetHeight(A->Left), GetHeight(A->Right)) + 1;//更新A节点的树高
    	B->Height = MAX(GetHeight(B->Right), A->Height) + 1;//更新B节点的树高
    	return B;
    }
    AVLTree DoubleLeftRightRotation(AVLTree A)
    {
    	A->Left = SingleRightRotation(A->Left);//先进行右单旋
    	A = SingleLeftRotation(A);//后进行左单旋
    }
    AVLTree DoubleRightLeftRotaion(AVLTree A)
    {
    	A->Right = SingleLeftRotation(A->Right);//先进行左单旋
    	A = SingleRightRotation(A);//后进行右单旋
    }
    void InorderTraversal(AVLTree AT)
    {
    	if (AT != NULL)
    	{
    		InorderTraversal(AT->Left);//输出左节点
    		printf("%d ", AT->Data);//输出节点的值
    		InorderTraversal(AT->Right);//输出右节点
    	}
    }
    
    展开全文
  • 面试题 合并两棵平衡二叉树

    千次阅读 2018-07-14 16:31:37
    首先看我的另一篇文章,如何构建一棵AVL树:C++ 平衡二叉树创建 然后可以将每棵AVL树的结点单独获取,并将结点整合到一个队列,再重新用队列构建出一棵合并后的AVL树。 实现代码如下: #include&lt;...

    首先看我的另一篇文章,如何构建一棵AVL树:C++ 平衡二叉树的创建

    然后可以将每棵AVL树的结点单独获取,并将结点整合到一个队列,再重新用队列构建出一棵合并后的AVL树。

    实现代码如下:

    #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){}
    };
    
    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);	
    	
    	int _getHeight(BTNode *root);
    	int getHeight();//获取高度
    	
    	int diff(BTNode *root);//计算平衡因子
    	
    	BTNode *balance(BTNode *root);//平衡操作 
    	
    	BTNode *LL_Rotation(BTNode *root);//LL旋转 
    	BTNode *LR_Rotation(BTNode *root);
    	BTNode *RL_Rotation(BTNode *root);
    	BTNode *RR_Rotation(BTNode *root);
    	
    	queue<keyType> get_AVL_Node();
    	void get_AVL_Node_Core(queue<keyType> &que,BTNode *root);
    					
    	BTNode *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<<"第一棵AVL树"<<endl; 
    	cout<<"中序遍历:"<<endl;
    	bt.midorder_showBT();//中序遍历打印 
    	cout<<endl<<endl;
    	
    	cout<<"层次遍历:"<<endl;
    	bt.level_showBT();//前序遍历打印 
    	cout<<endl<<endl;
    	
    	cout<<"树高:"; 
    	cout<<bt.getHeight()<<endl<<endl;
    	
    	cout<<"树的根结点平衡因子:"; 
    	cout<<bt.diff(bt.root)<<endl<<endl;//求平衡因子 
    	
    	//第二棵树 
    	BT<int> bt2;
    	int arr2[] = {26,13,17,21,19,36};
    	bt2.createBT(arr2,sizeof(arr2)/sizeof(arr2[0]));//构建二叉排序树 
    	
    	cout<<"第二棵AVL树"<<endl; 
    	cout<<"中序遍历:"<<endl;
    	bt2.midorder_showBT();//中序遍历打印 
    	cout<<endl<<endl;
    	
    	cout<<"层次遍历:"<<endl;
    	bt2.level_showBT();//前序遍历打印 
    	cout<<endl<<endl;
    	
    	cout<<"树高:"; 
    	cout<<bt2.getHeight()<<endl<<endl;
    	
    	cout<<"树的根结点平衡因子:"; 
    	cout<<bt2.diff(bt2.root)<<endl<<endl;//求平衡因子
    	
    	//合并第一、第二棵树 
    	cout<<"合并后的AVL树"<<endl;  
    	queue<int> que1 = bt.get_AVL_Node();
    	queue<int> que2 = bt2.get_AVL_Node();
    	
    	while(!que2.empty())
    	{
    		que1.push(que2.front());
    		que2.pop();
    	}
    
    	BT<int> bt3;
    	bt3.createBT_ByQue(que1);//构建二叉排序树 
    	
    	cout<<"中序遍历:"<<endl;
    	bt3.midorder_showBT();//中序遍历打印 
    	cout<<endl<<endl;
    	
    	cout<<"层次遍历:"<<endl;
    	bt3.level_showBT();//前序遍历打印 
    	cout<<endl<<endl;
    	
    	cout<<"树高:"; 
    	cout<<bt3.getHeight()<<endl<<endl;
    	
    	cout<<"树的根结点平衡因子:"; 
    	cout<<bt3.diff(bt3.root)<<endl<<endl;//求平衡因子
    	
    	//查找结点,AVLTree查找的复杂度能控制在对数范围O(log n)
    	int val;
    	cout<<"请输入要查找的结点:";
    	cin>>val;
    	
    	if(bt3.search_AVL(val) != nullptr){
    		cout<<bt3.search_AVL(val)<<endl;
    		cout<<bt3.search_AVL(val)->value<<endl;
    	}	
    	else
    		cout<<"该结点不存在!"<<endl; 
    	
    	return 0;
    }
    
    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);
    }

    运行结果如下:

    展开全文
  • 4.5 平衡二叉树

    2020-11-14 20:55:12
    实现了创建一棵平衡二叉树的方法 代码 /** * AVL树:平衡二叉树 也被称为 平衡二叉搜索树, * 目的:保证较高的查询效率,方便查询搜索 * 特点:它是一棵空树 或 它的左右两棵子树的高度差的绝对值不超过1,并且...

    4.5 平衡二叉树

    功能

    1. 实现了左旋转,右旋转
    2. 实现了查看树的高度的方法
    3. 实现了创建一棵平衡二叉树的方法

    代码

    /**
     * AVL树:平衡二叉树 也被称为 平衡二叉搜索树,
     * 目的:保证较高的查询效率,方便查询搜索
     * 特点:它是一棵空树 或 它的左右两棵子树的高度差的绝对值不超过1,并且左右两棵子树都是一棵平衡二叉树。
     * 实现:
     * 	 构建一棵平衡二叉树
     * 	  (1) 左旋转:右子树高度大于左子树
     *    (2) 右旋转:左子树高度大于右子树
     *    注意:一些条件下,需要进行两次旋转!!!!!!(双旋转)
     * @author dxt
     *
     */
    public class AVLTreeDemo {
    	public static void main(String[] args) {
    		//int[] arr = {4, 3, 6, 5, 7, 8};
    		//int[] arr = {10, 12, 8, 9, 7, 6};
    		int[] arr = {6, 7, 8, 9, 10, 11};
    		
    		//1. 创建一棵AVL树
    		AVLTree avltree = new AVLTree();
    		for(int i=0; i<arr.length; i++) {
    			avltree.add(new Node(arr[i]));
    		}
    		
    		//2. 遍历
    		System.out.println("前序遍历:");
    		avltree.preOrder();
    		System.out.println("中序遍历:");
    		avltree.infixOrder();
    		System.out.println("前序绘制");
    		avltree.preDraw();
    		
    		//3. 查看树的高度
    		System.out.println("树的高度:" + avltree.getRoot().height());
    		System.out.println("左子树的高度:" + avltree.getRoot().leftHeight());
    		System.out.println("右子树的高度:" + avltree.getRoot().rightHeight());
    		
    	}
    }
    
    class AVLTree{
    	private Node root;
    	
    	public AVLTree() {}
    	public AVLTree(Node root) {
    		this.root = root;
    	}
    	public Node getRoot() {
    		return root;
    	}
    	
    	public void add(Node node) {
    		if(root == null) {
    			root = node;
    		}else {
    			root.add(node);
    		}	
    	}
    	
    	//前序遍历
    	public void preOrder() {
    		if(root == null) {
    			System.out.println("AVL树为空。。。");
    			return;
    		}else {
    			this.root.preOrder();
    		}
    	}
    	//中序遍历
    	public void infixOrder() {
    		if(root == null) {
    			System.out.println("AVL树为空。。。");
    		}
    		this.root.infixOrder();
    	}
    	//前序绘制树形结构
    	public void preDraw() {
    		if(this.root == null) {
    			System.out.println("AVL树为空。。。");
    		}
    		this.root.preDraw(1); 	//根节点在第一层
    	}
    }
    
    class Node{
    	int value;
    	Node left;
    	Node right;
    	
    	public Node() {}
    	public Node(int value) {
    		this.value = value;
    	}
    	
    	/**
    	 * 左旋转
    	 * 用途: 当向AVL树添加一个节点时,此节点的添加造成树的 右子树高度 大于 左子树高度,导致AVL树的条件
    	 * 		被破坏,此时使用左旋转
    	 * 算法:
    	 * 	 (1)创建一个新的节点,新节点的值为当前结点的值
    	 *   (2)将新的节点的左子树 设置 为当前节点的左子树
    	 *   (3)将新的节点的右子树设置为当前节点右子树的左子树
    	 *   (4)将当前节点的值设置为当前节点右子节点的值
    	 *   (5)将当前节点的右子树 设置成 当前节点右子树的的右子树
    	 *   (6)将当前节点的左子树(左子节点) 设置成 新的节点
    	 */
    	public void leftRotate() {
    		//1. 创建一个新的节点,新节点的值为当前AVL树的根结点的值
    		Node newNode = new Node(this.value);
    		//2. 将新的节点的左子树 设置为 当前节点的左子树
    		newNode.left = this.left;
    		//3. 将新的节点的右子树设置为当前节点的右子树的左子树
    		newNode.right = this.right.left;
    		//4. 将当前节点的值 设置为 当前节点右子节点的值
    		this.value = this.right.value;
    		//5. 将当前节点的右子树 设置成 当前节点右子树的的右子树
    		this.right = this.right.right;
    		//6. 将当前节点的左子树(左子节点) 设置成 新的节点
    		this.left = newNode;
    	}
    	
    	/**
    	 * 右旋转
    	 * 用途: 当左子树的高度大于右子树的高度,导致AVL树的条件被破坏
    	 * 算法:
    	 *   (1)创建一个新节点,设置新节点的值为当前节点的值
    	 *   (2)将新节点的左子树设置为当前节点左子树的右子树
    	 *   (3)将新节点的右子树设置为当前节点的右子树
    	 *   (4)将当前节点的值设置为当前节点左子节点的值
    	 *   (5)将当前节点的左子树(左子节点) 设置为 当前节点的左子节点的左子节点
    	 *   (6)将当前节点的右子树(右子节点) 设置为 新节点
    	 */
    	public void rightRotate() {
    		//1. 
    		Node newNode = new Node(this.value);
    		//2. 
    		newNode.left = this.left.right;
    		//3. 
    		newNode.right = this.right;
    		//4. 
    		this.value = this.left.value;
    		//5. 
    		this.left = this.left.left;
    		//6. 
    		this.right = newNode;
    	}
    	
    	
    	//递归像树中添加节点
    	public void add(Node node) {
    		//1. 传入的参数是否合法
    		if(node == null) {
    			return;
    		}
    		
    		//2. 递归添加节点
    		if(node.value < this.value) {
    			if(this.left == null) {
    				this.left = node;
    			}else {
    				this.left.add(node);
    			}
    		} else {
    			if(this.right == null) {
    				this.right = node;
    			}else {
    				this.right.add(node);
    			}
    		}
    		
    		//3.1 当添加完一个节点后,如果: 右子树的高度 - 左子树的高度 > 1, 则进行 左旋转
    		if((this.rightHeight() - this.leftHeight()) > 1) {
    			//当前节点: 右子树的高度 - 左子树的高度 > 1, 则进行 左旋转
    			//如果当前节点的 右子树的左子树的高度 大于 右子树的右子树的高度
    			if(this.right != null && this.right.leftHeight() > this.right.rightHeight()) {
    				//则先对 右子树进行右旋转,然后在对当前节点进行左旋转
    				this.right.rightRotate();	//右子树 右旋转
    				this.leftRotate();			//左旋转
    			}else {
    				this.leftRotate();
    			}
    			
    			return;	//注意!!!
    		}
    		//3.2 当添加完一个节点后,如果: 左子树的高度 - 右子树的高度 > 1, 则进行 右旋转
    		if((this.leftHeight() - this.rightHeight()) > 1) {
    			//当前节点: 左子树的高度 - 右子树的高度 > 1
    			//如果当前节点 左子树的右子树的高度 大于 左子树的左子树的高度
    			if(this.left != null && this.left.rightHeight() > this.left.leftHeight()) {
    				//则先对左子树进行 右旋转, 然后在对当前节点进行左旋转
    				this.left.rightRotate();
    				this.leftRotate();
    			}else {
    				this.rightRotate();
    			}
    			
    		}
    	}
    	
    	//返回左子树的高度
    	public int leftHeight() {
    		if(this.left == null) {
    			return 0;
    		}
    		return this.left.height();
    	}
    	
    	//返回右子树的高度
    	public int rightHeight() {
    		if(this.right == null) {
    			return 0;
    		}
    		return this.right.height();
    	}
    	
    	//获取以当前节点为根节点的树的高度
    	public int height() {
    		return Math.max(this.left == null ? 0 : this.left.height(), 
    				this.right == null ? 0 : this.right.height()) + 1;
    	}
    	
    	//前序遍历
    	public void preOrder() {
    		System.out.println(this);
    		if(this.left != null) {
    			this.left.preOrder();
    		}
    		if(this.right != null) {
    			this.right.preOrder();
    		}
    	}
    	//中序遍历
    	public void infixOrder() {
    		if(this.left != null) {
    			this.left.infixOrder();
    		}
    		System.out.println(this);
    		if(this.right != null) {
    			this.right.infixOrder();
    		}
    	}
    	//前序树形结构输出
    	public void preDraw(int level) {
    		System.out.println(this.value);
    		//绘制左子树
    		if(this.left != null) {
    			for(int i=0; i<level-1; i++) {
    				System.out.print("     ");
    			}
    			System.out.print("+----");
    			this.left.preDraw(level+1);
    		}else {
    			for(int i=0; i<level-1; i++) {
    				System.out.print("     ");
    			}
    			System.out.print("+----");
    			System.out.println("null");
    		}
    		//绘制右子树
    		if(this.right != null) {
    			for(int i=0; i<level-1; i++) {
    				System.out.print("     ");
    			}
    			System.out.print("+----");
    			this.right.preDraw(level+1);
    		}else {
    			for(int i=0; i<level-1; i++) {
    				System.out.print("     ");
    			}
    			System.out.print("+----");
    			System.out.println("null");
    		}
    	}
    	
    	@Override
    	public String toString() {
    		return "Node : "+this.value;
    	}
    }
    

    结果

    p1

    总结

          旋转一共有四种情况,在学习时分别画个图会好很多。

    展开全文
  • . word 资料 平衡二叉树操作的演示 需求分析 本程序是利用平衡二叉树实现动态...平衡二叉树的显示采用凹入表现形式 合并两棵平衡二叉树一棵二叉树分裂为两棵平衡二叉树使得在一棵树中的所有关键字都小于或等于x另一
  • 二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储...

    二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,这篇博客重在研究二叉链。

    • 二叉树的链式存储结构如下图所示:
      在这里插入图片描述
    • 以下述二叉树为例,它的链式存储结构如下:
      在这里插入图片描述
      在这里插入图片描述
      可以看得出来二叉树的链式存储和链表基本是一样的。
    • 下面是自己总结的一些关于二叉树的经典笔试面试题,仅供大家参考:
    package com.xxx;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    /**
     * Description: 二叉树
     * Author: admin
     * Create: 2019-06-06 20:09
     */
    public class TestBinaryTree {
    
        class TreeNode {
            char value;
            TreeNode left;
            TreeNode right;
    
            public TreeNode(char value) {
                this.value = value;
            }
        }
    
        public int i = 0;
        //根据字符串创建二叉树
        public TreeNode createTestTree(String s) {
            TreeNode root = null;
            if (s.charAt(i) != '#') {
                root = new TreeNode(s.charAt(i));
                i++;
                root.left = createTestTree(s);
                root.right = createTestTree(s);
            }else {
                i++;
            }
            return root;
        }
    
        //结点个数
        public int getSize(TreeNode root) {
            if (root == null) {
                return 0;
            }
            return getSize(root.left) + getSize(root.right) + 1;
        }
    
        //叶子节点的个数
        public int getLeafSize(TreeNode root) {
            if (root == null) {
                return 0;
            }
            if (root.left == null && root.right == null) {
                return 1;
            }
            return getLeafSize(root.left) + getLeafSize(root.right);
        }
    
        //第k层节点个数
        public int getKLevelSize(TreeNode root, int k) {
            if (root == null) {
                return 0;
            }else if (k == 1) {
                return 1;
            }
            return getKLevelSize(root.left, k-1) + getKLevelSize(root.right, k-1);
        }
    
        //依次在二叉树的根、左子树、右子树中查找value,如果找到,返回结点,否则返回null
        public TreeNode find(TreeNode root, int value) {
            if (root == null) {
                return null;
            }
            if (root.value == value) {
                return root;
            }
            TreeNode ret = find(root.left, value);
            if (ret != null) {
                return ret;
            }
            ret = find(root.right, value);
            if (ret != null) {
                return ret;
            }
            return null;
        }
    
        //二叉树的高度
        public int height(TreeNode root) {
            if (root == null) {
                return 0;
            }else {
                int leftHeight = height(root.left);
                int rightHead = height(root.right);
                return (leftHeight > rightHead ? leftHeight : rightHead) + 1;
            }
        }
    
        //判断一棵树是否是完全二叉树,返回0代表是完全二叉树
        public int binaryTreeComplete(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            if (root != null) {
                queue.offer(root);
            }
            while (!queue.isEmpty()) {
                TreeNode top = queue.poll();
                if (top != null) {
                    queue.offer(root.left);
                    queue.offer(root.right);
                }else {
                    break;
                }
            }
            while (!queue.isEmpty()) {
                if (queue.peek() == null) {
                    queue.poll();
                }else {
                    return -1;
                }
            }
            return 0;
        }
    
        //检查两棵树是否相同
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if (p == null && q == null) {
                return true;
            }
            if ((p == null && q != null) || (p != null && q == null)) {
                return false;
            }
            if (p.value != q.value) {
                return false;
            }
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    
        //另一棵树的子树
        public boolean isSubtree(TreeNode s, TreeNode t) {
            if (s == null || t == null) {
                return false;
            }
            if (isSameTree(s, t)) {
                return true;
            }else if (isSubtree(s.left, t)) {
                return true;
            } else if (isSubtree(s.right, t)) {
                return true;
            }else {
                return false;
            }
        }
    
        //判断一颗二叉树是否是平衡二叉树  O(n^2)
        public boolean isBalanced(TreeNode root) {
            if (root == null) {
                return true;
            }else {
                int leftHeight = height(root.left);
                int rightHeight = height(root.right);
                return Math.abs(leftHeight - rightHeight) < 2
                        && isBalanced(root.left) && isBalanced(root.right);
            }
        }
    
        //对称二叉树
        public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
            if ((leftTree == null && rightTree != null)
                    || (leftTree != null && rightTree == null)) {
                return false;
            }
            if (leftTree == null && rightTree == null) {
                return true;
            }
            return leftTree.value == rightTree.value
                    && isSymmetricChild(leftTree.left, rightTree.right)
                    && isSymmetricChild(leftTree.right, rightTree.left);
        }
        public boolean isSymmetric(TreeNode root) {
            if (root == null) {
                return true;
            }
            return isSymmetricChild(root.left, root.right);
        }
    
        //根据二叉树创建字符串
        public void tree2strChild(TreeNode t, StringBuilder sb) {
            if (t == null) {
                return;
            }
            sb.append(t.value);
    
            if (t.left != null) {
                sb.append("(");
                tree2strChild(t.left, sb);
                sb.append(")");
            }else {
                if (t.right == null) {
                    return;
                }else {
                    sb.append("()");
                }
            }
    
            if (t.right == null) {
                return;
            }else {
                sb.append("(");
                tree2strChild(t.right, sb);
                sb.append(")");
            }
        }
        public String tree2str(TreeNode t) {
            StringBuilder sb = new StringBuilder();
            tree2strChild(t, sb);
            return sb.toString();
        }
    }
    
    展开全文
  • 平衡二叉树

    2021-02-09 20:15:27
    平衡二叉树它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 左旋转 举例说明,下面这颗二叉树的左子树的深度...
  • 一棵平衡的二叉树的平衡因子只能是1,0,-1如何构建一棵平衡二叉树呢?对一棵平衡的二叉树进行插入操作,插入后,可能导致不平衡,对不平衡的二叉树应该进行旋转操作,将其旋转为平衡二叉树。平衡二叉树应该具有...
  • 之前学习了二叉排序树,假如现有数列:1,2,3,4,5,要用这个数列创建一棵二叉排序树,结果是这样的:二叉排序树看起来就怪怪的,其实就是斜着放的单链表。这棵树存在以下问题:左子树全部为空,其实就是一个单链表;...
  • 平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 树形DP法求解 定义一个类先创建出结果是否是平衡的和高度为多少? public static class ReturnNode{ ...
  • 平衡二叉树操作的演示 1. 需求分析 本程序是利用平衡...更新平衡二叉树的显示 2 平衡二叉树的显示采用凹入表现形式 3 合并两棵平衡二叉树 4 把一棵二叉树分裂为两棵平衡二叉树使得在一棵树中的所有关键字都小于或 等
  • 源码博客上有,所有人可看 一、需求分析: (1) 构建一个平衡二叉树并实现创建、插入、查找、删除、销毁等操作。... F:输出打印一棵平衡二叉树 G:合并两棵平衡二叉树 H:分裂一颗平衡二叉树
  • 平衡二叉树(AVL):是一种结构平衡的二叉搜索树,即叶节点高度差的绝对值不超过1,并且左右两棵子树都是一棵平衡二叉树。它能在O(log n)内完成插入、查找和删除操作,其高度h>logN (N为节点个数)。 二、创建AVL...
  • 时我们创建一个二叉排序树 如下: 存在问题: 左子树为空,对插入速度没有影响。 查询速度明显变慢,因为每次还需要比较左子树,其查询速度比链表还要慢。 为解决这种问题,我们本篇讲讲平衡二叉树(AVL树) 基本...
  • 平衡二叉树(AVL树)

    2020-03-27 17:08:06
    2、它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 为什么需要AVL树 问题 给定一个数列{1,2,3,4,5,6},要求创建一颗二叉排序树(BST) 分析: 1、左子树全...
  • 平衡二叉树 又称AVL树,平衡二叉树具有的特性是:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 本文将从以下几个方面进行介绍: TreeNode结构介绍。 向平衡...
  • 平衡二叉树——AVL树

    2020-11-08 20:23:39
    平衡二叉树一棵空的二叉排序树,或者是具有下列性质的二叉排序树 根节点的左子树和右子树的深度最多相差1 根节点的左子树和右子树也是平衡二叉树 平衡因子 结点的平衡因子是该节点左子树和右子树的深度之差,如...
  • 一、性质:它或者是颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。...根据上述性质我们可以发现图(a)是一棵平衡二叉树,而图(b...
  • 学习笔记-平衡二叉树

    2021-04-01 00:01:47
    平衡二叉树的特点是每左子树和右子树的高度相差不超过1。 平衡二叉树的实现 实际上,平衡二叉树是通过对二叉排序树旋转来完成的。而旋转的实际意义是更改二叉排序树的根节点,通过二叉排序树的创立规则,数组的第...

空空如也

空空如也

1 2 3 4 5 6
收藏数 101
精华内容 40
关键字:

创建一棵平衡二叉树