计算平衡因子代码c语言实现

在C语言中，平衡因子也称为树的高度差，通常用于二叉搜索树（BST）的数据结构中，用于判断树是否保持了左小于右的特性。平衡因子是指一个节点的左子树高度减去右子树高度的结果。以下是一个简单的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语言）：

#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语言代码

当然，下面是一个简单的平衡二叉树的C语言代码示例：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct Node {
    int data;                 // 节点值
    struct Node* left;        // 左子节点指针
    struct Node* right;       // 右子节点指针
    int height;               // 节点高度
} Node;

// 计算节点的高度
int height(Node* node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 获取两个数中较大的值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 创建一个新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->height = 1;
    return newNode;
}

// 执行右旋操作
Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

// 执行左旋操作
Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

// 获取节点的平衡因子
int getBalanceFactor(Node* node) {
    if (node == NULL) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

// 插入节点
Node* insertNode(Node* node, int data) {
    if (node == NULL) {
        return createNode(data);
    }

    if (data < node->data) {
        node->left = insertNode(node->left, data);
    } else if (data > node->data) {
        node->right = insertNode(node->right, data);
    } else {
        // 忽略插入相同的节点
        return node;
    }

    node->height = 1 + max(height(node->left), height(node->right));

    int balanceFactor = getBalanceFactor(node);

    // 左-左情况，执行右旋操作
    if (balanceFactor > 1 && data < node->left->data) {
        return rightRotate(node);
    }
    
    // 右-右情况，执行左旋操作
    if (balanceFactor < -1 && data > node->right->data) {
        return leftRotate(node);
    }

    // 左-右情况，先对左子节点进行左旋，再对当前节点进行右旋
    if (balanceFactor > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // 右-左情况，先对右子节点进行右旋，再对当前节点进行左旋
    if (balanceFactor < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

// 中序遍历二叉树
void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

int main() {
    Node* root = NULL;

    root = insertNode(root, 10);
    root = insertNode(root, 20);
    root = insertNode(root, 30);
    root = insertNode(root, 40);
    root = insertNode(root, 50);
    root = insertNode(root, 25);

    printf("中序遍历结果：");
    inorderTraversal(root);

    return 0;
}

这段代码实现了一个平衡二叉树的插入和中序遍历操作。你可以根据需要自行修改和扩展。希望对你有所帮助！