计算平衡因子代码c语言实现
时间: 2024-09-16 17:03:35 浏览: 26
在C语言中,平衡因子也称为树的高度差,通常用于二叉搜索树(BST)的数据结构中,用于判断树是否保持了左小于右的特性。平衡因子是指一个节点的左子树高度减去右子树高度的结果。以下是一个简单的C语言函数,用于计算单个节点的平衡因子:
```c
int getBalanceFactor(struct Node* node) {
// 如果节点为空,则认为平衡因子为0
if (node == NULL) {
return 0;
}
// 计算左子树高度
int leftHeight = height(node->left);
// 计算右子树高度
int rightHeight = height(node->right);
// 返回左右子树高度之差作为平衡因子
return leftHeight - rightHeight;
}
// 这里假设height()函数是一个辅助函数,返回给定节点的子树高度
int height(struct Node* node) {
if (node == NULL)
return 0;
else
return 1 + max(height(node->left), height(node->right));
}
```
相关问题
平衡二叉树代码实现c语言
平衡二叉树(AVL树)是一种自平衡的二叉搜索树,它的左子树和右子树的高度差不超过1。下面是一个简单的平衡二叉树的代码实现(C语言):
```c
#include <stdio.h>
#include <stdlib.h>
// 定义平衡二叉树节点结构
typedef struct AVLNode {
int data; // 节点数据
int height; // 节点高度
struct AVLNode* left; // 左子树指针
struct AVLNode* right; // 右子树指针
} AVLNode;
// 获取节点的高度
int getHeight(AVLNode* node) {
if (node == NULL) {
return 0;
}
return node->height;
}
// 计算节点的平衡因子
int getBalanceFactor(AVLNode* node) {
if (node == NULL) {
return 0;
}
return getHeight(node->left) - getHeight(node->right);
}
// 更新节点的高度
void updateHeight(AVLNode* node) {
int leftHeight = getHeight(node->left);
int rightHeight = getHeight(node->right);
node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// 左旋操作
AVLNode* leftRotate(AVLNode* node) {
AVLNode* newRoot = node->right;
node->right = newRoot->left;
newRoot->left = node;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
// 右旋操作
AVLNode* rightRotate(AVLNode* node) {
AVLNode* newRoot = node->left;
node->left = newRoot->right;
newRoot->right = node;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
// 插入节点
AVLNode* insertNode(AVLNode* root, int data) {
if (root == NULL) {
AVLNode* newNode = (AVLNode*)malloc(sizeof(AVLNode));
newNode->data = data;
newNode->height = 1;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
if (data < root->data) {
root->left = insertNode(root->left, data);
} else if (data > root->data) {
root->right = insertNode(root->right, data);
} else {
// 已存在相同节点,不进行插入
return root;
}
updateHeight(root);
int balanceFactor = getBalanceFactor(root);
// 左子树高度大于右子树
if (balanceFactor > 1) {
if (data < root->left->data) {
// 左左情况,进行右旋操作
return rightRotate(root);
} else if (data > root->left->data) {
// 左右情况,先对左子树进行左旋操作,再对根节点进行右旋操作
root->left = leftRotate(root->left);
return rightRotate(root);
}
}
// 右子树高度大于左子树
if (balanceFactor < -1) {
if (data > root->right->data) {
// 右右情况,进行左旋操作
return leftRotate(root);
} else if (data < root->right->data) {
// 右左情况,先对右子树进行右旋操作,再对根节点进行左旋操作
root->right = rightRotate(root->right);
return leftRotate(root);
}
}
return root;
}
// 中序遍历二叉树
void inorderTraversal(AVLNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
int main() {
AVLNode* root = NULL;
int data[] = {5, 3, 7, 2, 4, 6, 8};
int n = sizeof(data) / sizeof(data);
for (int i = 0; i < n; i++) {
root = insertNode(root, data[i]);
}
printf("中序遍历结果:");
inorderTraversal(root);
printf("\n");
return 0;
}
```
这段代码实现了平衡二叉树的插入操作,并提供了一个简单的示例来演示插入操作后的中序遍历结果。你可以根据需要修改代码来适应其他操作,比如删除节点等。
平衡二叉树算法的c语言代码
平衡二叉树,如AVL树或红黑树,是一种特殊的二叉搜索树,它的左右两个子树的高度差不超过1。以下是使用C语言实现AVL树的基本插入操作的一个简单示例,它包含了旋转操作来保持平衡:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
int height; // 节点高度
} Node;
// 计算新插入节点的新高度
int computeHeight(Node* node) {
if (node == NULL)
return 0;
else
return node->height;
}
// 更新节点的平衡因子(左子树高度 - 右子树高度)
int getBalanceFactor(Node* node) {
if (node == NULL)
return 0;
else
return computeHeight(node- computeHeight(node->right);
}
// 左旋
Node* leftRotate(Node* y) {
Node* x = y->right;
Node* T2 = x->left;
// 将y的右子树替换为x
y->right = T2;
// 如果x有左孩子,则设置x的左孩子为新的y
if (T2 != NULL)
T2->parent = y;
// 设置x为新的根
x->parent = y->parent;
// 如果y是空子树的根,则将新的根设为x
if (y->parent == NULL) {
root = x;
}
// 否则,y的父亲成为新的祖父母
else if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
// 更新y和x的height
y->height = computeHeight(y);
x->height = computeHeight(x);
return x;
}
// 右旋
Node* rightRotate(Node* x) {
// 类似于leftRotate,只是方向相反
// ...
}
// 插入函数
Node* insert(Node* node, int data) {
if (node == NULL)
return (Node*)malloc(sizeof(Node));
else if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
else // 数据已存在,不做处理
return node;
// 记录当前节点的新高度
node->height = 1 + max(computeHeight(node->left), computeHeight(node->right));
// 检查是否需要旋转
int balance = getBalanceFactor(node);
// 如果左子树太高,需要右旋
if (balance > 1 && data < node->left->data)
return rightRotate(node);
// 如果右子树太高,需要左旋
else if (balance < -1 && data > node->right->data)
return leftRotate(node);
// 或者如果一边太低并且新插入的是不平衡节点,也需要旋转
else if (balance > 1 && data > node->left->data) { // 左旋左孩子的右旋
node->left = leftRotate(node->left);
return rightRotate(node);
} else if (balance < -1 && data < node->right->data) { // 右旋右孩子的左旋
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// 示例主函数
int main() {
// 初始化树...
Node* root = insert(root, 9);
// 插入更多数据...
return 0;
}
```
请注意,这只是一个基础的实现,并未包含完整的删除和查找功能,以及所有必要的错误检查。实际应用中会更复杂一些,包括处理更多的边界情况和异常。