平衡二叉树及优化(细节图解)(时间复杂度O(N))_平衡树 复杂度

一.平衡二叉树

定义：平衡二叉树是一种高度平衡的二叉树，它的节点结构和操作方式有特殊的规律。平衡二叉树的定义是：任意节点的子树的高度差都小于等于1。 平衡二叉树的作用是提高查询的效率，保证查询的时间复杂度为O(logn)。

平衡二叉树会使用到[递归(这里有递归基础)]

1.1平衡二叉树定义

二.构建二叉树节点

2.1构建结构体

typedef char BTDataType;
typedef struct BinaryTreeNode {
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

2.2连接图例

 2.3创建节点

BTNode* CreateNode(BTDataType x)//创建节点
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

三.构建二叉树

3.1快速构建二叉树

BTNode* A = CreateNode(1);
	BTNode* B = CreateNode(2);
	BTNode* C = CreateNode(3);
	BTNode* D = CreateNode(4);
	BTNode* E = CreateNode(5);
 
 
	BTNode* A2 = CreateNode(1);
	BTNode* B2 = CreateNode(2);
	BTNode* C2 = CreateNode(3);
	BTNode* D2 = CreateNode(4);
	BTNode* E2 = CreateNode(5);
	BTNode* F2 = CreateNode(5);
 
 
	//快速构建树A
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
 
	//快速构建树A2
	A2->left = B2;
	A2->right = C2;
	B2->left = D2;
	C2->right = E2;
	E2->right = F2;

 3.2构建的两颗树

 四.平衡二叉树(O(n^2))

4.1平衡二叉树代码

方法一(未优化):平衡二叉树的判断思路主要是看该二叉树是否满足两个条件：首先，它需要是一颗[二叉排序树]；其次，它的任何一个节点的左子树或者右子树都需要是平衡二叉树，也就是说左右子树的高度差必须小于等于1。

具体实现上，我们可以使用递归的方法来进行判断。首先检查当前子树是否是平衡二叉树，然后递归地对左子树和右子树做同样的检查。在检查过程中，需要求出每个节点的左右子树的高度，并判断它们的高度差是否超过了1。只有当每个节点都满足上述条件时，这颗二叉树才可以被称为是平衡二叉树。

int TreeDepth(BTNode* root)//树的高度
{
	if (root == NULL)
		return 0;
 
	int leftDepth = TreeDepth(root->left);
	int rightDepth = TreeDepth(root->right);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
 
 
 
 
//平衡二叉树(前序)
//TreeDepth()计算当前树的高度
bool isBalanced(BTNode* root)
{
	if (root == NULL)
		return true;
 
	int gap = TreeDepth(root->left) - TreeDepth(root->right);
	if (abs(gap) > 1)
		return false;
 
 
	return isBalanced(root->left) && isBalanced(root->right);
 
}

4.2计算树的高度图解

4.3平衡二叉树图解

对比当前根(root)左右子树的高度，这里每次对比的时候都要调用TreeDepth()计算当前根左右子树的高度，又因为TreeDepth()的时间复杂度为O(n),

所以整个isBalanced()的最坏时间复杂度为O(n^2)

五.平衡二叉树优化(O(n))

5.1平衡二叉树代码优化

从左子树叶子节点开始。判断的同时，把高度带给上一次调用的父亲节点，这里不需要再递归求树的高度，优化之后就不像之前存在大量的重复计算。isBalanced1()优化后的平衡二叉树代码，时间复杂度为O(N).

可以通过【前序中序后续递归】尝试打印出树中的数据。

bool _isBalanced1(BTNode* root, int* pDepth)
{
	if (root == NULL)
	{
		*pDepth = 0;
		return true;
	}
	else
	{
		int leftDepth = 0;
		if (_isBalanced1(root->left, &leftDepth) == 0)
		{
			return false;
		}
 
		int rightDepth = 0;
		if (_isBalanced1(root->right, &rightDepth) == 0)
		{
			return false;
		}
 
		if (abs(leftDepth - rightDepth) > 1)
			return false;
 
		*pDepth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
		return true;
 
	}
}
bool isBalanced1(BTNode* root)
{
	int Depth = 0;
	return _isBalanced1(root, &Depth);
}

5.1 平衡二叉树图解

六.全部代码

6.1全部代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef char BTDataType;
typedef struct BinaryTreeNode {
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
 
BTNode* CreateNode(BTDataType x)//创建节点
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
 
int TreeDepth(BTNode* root)//树的高度
{
	if (root == NULL)
		return 0;
 
	int leftDepth = TreeDepth(root->left);
	int rightDepth = TreeDepth(root->right);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
 
 
 
 
//平衡二叉树(前序)
//TreeDepth()计算当前树的高度
bool isBalanced(BTNode* root)
{
	if (root == NULL)
		return true;
 
	int gap = TreeDepth(root->left) - TreeDepth(root->right);
	if (abs(gap) > 1)
		return false;
 
 
	return isBalanced(root->left) && isBalanced(root->right);
 
}
 
 
 
 
bool _isBalanced1(BTNode* root, int* pDepth)
{
	if (root == NULL)
	{
		*pDepth = 0;
		return true;
	}
	else
	{
		int leftDepth = 0;
		if (_isBalanced1(root->left, &leftDepth) == 0)
		{
			return false;
		}
 
		int rightDepth = 0;
		if (_isBalanced1(root->right, &rightDepth) == 0)
		{
			return false;
		}
 
		if (abs(leftDepth - rightDepth) > 1)
			return false;
 
		*pDepth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
		return true;
 
	}
}
bool isBalanced1(BTNode* root)
{
	int Depth = 0;
	return _isBalanced1(root, &Depth);
}
 
 
 
int main()
{
	BTNode* A = CreateNode(1);
	BTNode* B = CreateNode(2);
	BTNode* C = CreateNode(3);
	BTNode* D = CreateNode(4);
	BTNode* E = CreateNode(5);
 
 
	BTNode* A2 = CreateNode(1);
	BTNode* B2 = CreateNode(2);
	BTNode* C2 = CreateNode(3);
	BTNode* D2 = CreateNode(4);
	BTNode* E2 = CreateNode(5);
	BTNode* F2 = CreateNode(5);
 
 
	//快速构建树A
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
 
	//快速构建树A2
	A2->left = B2;
	A2->right = C2;
	B2->left = D2;
	C2->right = E2;
	E2->right = F2;
 
 
	printf("A这棵树为平衡二叉树吗?   1是 0不是\n");
	bool a = isBalanced1(A);
	printf("A=%d", a);
	printf("\n");
 
	
	printf("A2这棵树为平衡二叉树吗?   1是 0不是\n");
	bool b = isBalanced1(A2);
	printf("A2=%d", b);
	printf("\n");
 
 
	return 0;
}

 6.2运行结果

   以上就是本期内容，欢迎参考指正，如有不懂，欢迎评论或私信出下期！！！