当前位置：首页 > news >正文

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

news 2025/7/8 9:18:04

探索树算法：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 Caseif (balance > 1 && data < root->left->data) {return rotateRight(root);}// Right Right Caseif (balance < -1 && data > root->right->data) {return rotateLeft(root);}// Left Right Caseif (balance > 1 && data > root->left->data) {root->left = rotateLeft(root->left);return rotateRight(root);}// Right Left Caseif (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;
}