探索树算法：C语言实现二叉树与平衡树

短命女 2023-10-14 22:01 117阅读 0赞

## 探索树算法：C语言实现二叉树与平衡树 ##

树是计算机科学中一个重要且广泛应用的数据结构，它在许多领域都有着重要作用。本篇博客将深入介绍两种常见的树算法：二叉树遍历和平衡二叉树（AVL树），并提供在C语言中的实现示例。

### 二叉树遍历 ###

二叉树是一种每个节点最多有两个子节点的树结构。常见的二叉树遍历方式有三种：前序遍历、中序遍历和后序遍历。下面是这三种遍历方式的C语言实现示例：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node {
        int data;
        struct Node* left;
        struct Node* right;
    } Node;
    
    Node* createNode(int data) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    
    void preOrder(Node* root) {
        if (root == NULL) return;
        printf("%d ", root->data);
        preOrder(root->left);
        preOrder(root->right);
    }
    
    void inOrder(Node* root) {
        if (root == NULL) return;
        inOrder(root->left);
        printf("%d ", root->data);
        inOrder(root->right);
    }
    
    void postOrder(Node* root) {
        if (root == NULL) return;
        postOrder(root->left);
        postOrder(root->right);
        printf("%d ", root->data);
    }
    
    int main() {
        Node* root = createNode(1);
        root->left = createNode(2);
        root->right = createNode(3);
        root->left->left = createNode(4);
        root->left->right = createNode(5);
    
        printf("Preorder traversal: ");
        preOrder(root);
        printf("\n");
    
        printf("Inorder traversal: ");
        inOrder(root);
        printf("\n");
    
        printf("Postorder traversal: ");
        postOrder(root);
        printf("\n");
    
        return 0;
    }

### 平衡二叉树（AVL树） ###

平衡二叉树是一种特殊的二叉搜索树，它的每个节点的左子树和右子树的高度差不超过1。这确保了树的高度始终保持在较小的范围内，提高了查找、插入和删除操作的效率。下面是AVL树的插入操作的C语言实现示例：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node {
        int data;
        struct Node* left;
        struct Node* right;
        int height;
    } Node;
    
    int max(int a, int b) {
        return (a > b) ? a : b;
    }
    
    int getHeight(Node* node) {
        if (node == NULL) return 0;
        return node->height;
    }
    
    int getBalanceFactor(Node* node) {
        if (node == NULL) return 0;
        return getHeight(node->left) - getHeight(node->right);
    }
    
    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* rotateRight(Node* y) {
        Node* x = y->left;
        Node* T2 = x->right;
    
        x->right = y;
        y->left = T2;
    
        y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
        x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    
        return x;
    }
    
    Node* rotateLeft(Node* x) {
        Node* y = x->right;
        Node* T2 = y->left;
    
        y->left = x;
        x->right = T2;
    
        x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
        y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    
        return y;
    }
    
    Node* insert(Node* root, int data) {
        if (root == NULL) return createNode(data);
    
        if (data < root->data) {
            root->left = insert(root->left, data);
        } else if (data > root->data) {
            root->right = insert(root->right, data);
        } else {
            return root; // Duplicate keys not allowed
        }
    
        root->height = 1 + max(getHeight(root->left), getHeight(root->right));
    
        int balance = getBalanceFactor(root);
    
        // Left Left Case
        if (balance > 1 && data < root->left->data) {
            return rotateRight(root);
        }
    
        // Right Right Case
        if (balance < -1 && data > root->right->data) {
            return rotateLeft(root);
        }
    
        // Left Right Case
        if (balance > 1 && data > root->left->data) {
            root->left = rotateLeft(root->left);
            return rotateRight(root);
        }
    
        // Right Left Case
        if (balance < -1 && data < root->right->data) {
            root->right = rotateRight(root->right);
            return rotateLeft(root);
        }
    
        return root;
    }
    
    void inOrder(Node* root) {
        if (root == NULL) return;
        inOrder(root->left);
        printf("%d ", root->data);
        inOrder(root->right);
    }
    
    int main() {
        Node* root = NULL;
    
        root = insert(root, 10);
        root = insert(root, 20);
        root = insert(root, 30);
        root = insert(root, 40);
        root = insert(root, 50);
        root = insert(root, 25);
    
        printf("Inorder traversal of AVL tree: ");
        inOrder(root);
        printf("\n");
    
        return 0;
    }

### 总结 ###

本篇博客深入探讨了树算法中的两个重要方面：二叉树遍历和平衡二叉树（AVL树）。通过C语言实现

的示例代码，您可以更好地理解这些算法的实际运行原理和用途。树算法在数据库、图形处理、编译器设计等领域都有着广泛的应用，掌握这些算法将有助于您解决各种实际问题。

希望本文对您学习树算法和C语言编程有所帮助！如果您有任何问题或建议，请随时在评论区留言。