数据结构--树

树（Tree）是一种非线性分层数据结构，由节点（Node）和边（Edge）组成，具有以下核心特性：

1. 有且仅有一个根节点（Root）
2. 除根节点外，每个节点有且仅有一个父节点
3. 节点间不存在环路
4. 节点间通过边连接，表示层级关系

核心概念图解（使用 Mermaid）

关键术语：

常见树结构详解与C语言实现

1. 二叉树（Binary Tree）

特点：每个节点最多有两个子节点（左/右子节点）

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

// 二叉树节点结构
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode) {
        newNode->data = value;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    return newNode;
}

// 先序遍历
void preorderTraversal(TreeNode* root) {
    if (root) {
        printf("%d ", root->data);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

// 示例用法
int main() {
    // 构建示例二叉树
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);

    printf("先序遍历: ");
    preorderTraversal(root); // 输出: 1 2 4 5 3 6
    
    return 0;
}

2. 二叉搜索树（BST）

特点：左子树所有值 < 根节点值 < 右子树所有值

// 二叉搜索树插入
TreeNode* insertBST(TreeNode* root, int value) {
    if (!root) return createNode(value);
    
    if (value < root->data) {
        root->left = insertBST(root->left, value);
    } else if (value > root->data) {
        root->right = insertBST(root->right, value);
    }
    return root;
}

// 二叉搜索树查找
TreeNode* searchBST(TreeNode* root, int key) {
    if (!root || root->data == key) 
        return root;
    
    if (key < root->data) 
        return searchBST(root->left, key);
    
    return searchBST(root->right, key);
}

// 示例用法
int main() {
    TreeNode* root = NULL;
    int values[] = {8, 3, 10, 1, 6, 14, 4, 7, 9};
    
    for (int i = 0; i < 9; i++) {
        root = insertBST(root, values[i]);
    }
    
    TreeNode* found = searchBST(root, 6);
    if (found) printf("找到节点: %d\n", found->data); // 输出: 6
}

3. AVL树（平衡二叉树）

特点：任意节点左右子树高度差 ≤ 1

// AVL树节点
typedef struct AVLNode {
    int data;
    int height;
    struct AVLNode* left;
    struct AVLNode* right;
} AVLNode;

// 计算节点高度
int height(AVLNode* node) {
    return node ? node->height : 0;
}

// 获取平衡因子
int balanceFactor(AVLNode* node) {
    return height(node->left) - height(node->right);
}

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

    // 旋转
    x->right = y;
    y->left = T2;

    // 更新高度
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));

    return x;
}

// 左旋操作（类似右旋，方向相反）
AVLNode* leftRotate(AVLNode* x) {
    /* 实现类似右旋 */
    return x; // 简化示例
}

// AVL插入（需配合平衡操作）
AVLNode* insertAVL(AVLNode* node, int value) {
    /* 标准BST插入 */
    if (!node) return createAVLNode(value);
    
    if (value < node->data)
        node->left = insertAVL(node->left, value);
    else if (value > node->data)
        node->right = insertAVL(node->right, value);
    else 
        return node; // 重复值
    
    /* 更新高度和平衡 */
    return node;
}

4. 红黑树

特点：通过颜色规则保持平衡

// 红黑树节点
typedef enum { RED, BLACK } Color;

typedef struct RBNode {
    int data;
    Color color;
    struct RBNode* left;
    struct RBNode* right;
    struct RBNode* parent;
} RBNode;

// 红黑树插入
void RBInsert(RBNode** root, int value) {
    RBNode* z = createRBNode(value);
    RBNode* y = NULL;
    RBNode* x = *root;
    
    // 标准BST插入
    while (x) {
        y = x;
        x = (z->data < x->data) ? x->left : x->right;
    }
    
    z->parent = y;
    if (!y) {
        *root = z;
    } else if (z->data < y->data) {
        y->left = z;
    } else {
        y->right = z;
    }
    
    z->left = z->right = NULL;
    z->color = RED; // 新节点总是红色
    
    // 红黑树修复（需实现）
    fixViolation(root, z);
}

5. B树（多路平衡查找树）

特点：每个节点可包含多个键和多个子节点

#define M 3 // B树的阶

// B树节点
typedef struct BTreeNode {
    int keys[M-1];     // 关键字数组
    struct BTreeNode* children[M]; // 子节点指针数组
    int key_count;     // 当前关键字数量
    int is_leaf;      // 是否为叶子节点
} BTreeNode;

// B树查找
BTreeNode* BTreeSearch(BTreeNode* root, int key) {
    int i = 0;
    while (i < root->key_count && key > root->keys[i])
        i++;
    
    if (i < root->key_count && key == root->keys[i])
        return root;
    
    if (root->is_leaf)
        return NULL;
    
    return BTreeSearch(root->children[i], key);
}

树的操作复杂度

注：平衡树（AVL/红黑树/B树）最坏复杂度保持 O(log n)

应用场景

1. 文件系统：目录树结构（N叉树）
2. 数据库索引：B/B+树（高效磁盘访问）
3. 路由算法：决策树（二叉树）
4. AI决策：博弈树（多叉树）
5. 数据压缩：哈夫曼树（带权二叉树）
6. DNS解析：域名解析树（字典树）

// 哈夫曼树节点示例
typedef struct HuffmanNode {
    char character;
    int frequency;
    struct HuffmanNode* left;
    struct HuffmanNode* right;
} HuffmanNode;