L6_01 树

一、树的基本概念

1.1 树的定义

树是一种非线性的数据结构，由节点和边组成，具有以下特点：

• 有且仅有一个根节点
• 除根节点外，每个节点有且仅有一个父节点
• 没有环（无回路）

1.2 树的基本术语

• 根节点(Root)：树的最顶层节点
• 叶子节点(Leaf)：没有子节点的节点
• 父节点(Parent)：有子节点的节点
• 子节点(Child)：被父节点直接连接的节点
• 兄弟节点(Sibling)：拥有相同父节点的节点
• 度(Degree)：节点拥有的子节点数量
• 深度(Depth)：从根节点到该节点的路径长度
• 高度(Height)：从该节点到最远叶子节点的路径长度

1.3 树的表示

struct TreeNode {
    int data;
    vector<TreeNode*> children;
    
    TreeNode(int val) : data(val) {}
};

二、哈夫曼树

2.1 哈夫曼树的定义

哈夫曼树（最优二叉树）是一种带权路径长度最短的二叉树。

2.2 哈夫曼树的构建

1. 将每个节点作为独立的树放入优先队列（最小堆）
2. 每次取出权值最小的两棵树
3. 创建新节点，权值为两棵树权值之和
4. 将新节点作为两棵树的父节点
5. 将新树放回优先队列
6. 重复步骤2-5，直到只剩一棵树

struct HuffmanNode {
    int weight;
    HuffmanNode *left, *right;
    HuffmanNode(int w) : weight(w), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};

HuffmanNode* buildHuffmanTree(vector<int>& weights) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    for (int w : weights) {
        pq.push(new HuffmanNode(w));
    }
    
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        HuffmanNode* parent = new HuffmanNode(left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

三、完全二叉树

3.1 完全二叉树的定义

完全二叉树是一种特殊的二叉树，除最后一层外，其他层的节点数都达到最大，且最后一层的节点都集中在左侧。

3.2 完全二叉树的性质

• 若节点编号为 i（从1开始），则：
  • 左子节点：2*i
  • 右子节点：2*i + 1
  • 父节点：i/2（向下取整）

3.3 完全二叉树的存储

完全二叉树通常用数组存储：

class CompleteBinaryTree {
private:
    vector<int> tree;
    
public:
    CompleteBinaryTree(int size) : tree(size + 1) {}
    
    int getLeftChild(int i) { return 2 * i; }
    int getRightChild(int i) { return 2 * i + 1; }
    int getParent(int i) { return i / 2; }
    void setValue(int i, int val) { tree[i] = val; }
    int getValue(int i) { return tree[i]; }
};

四、二叉排序树

4.1 二叉排序树的定义

二叉排序树（BST）是一种特殊的二叉树，满足以下性质：

• 左子树所有节点的值 < 根节点的值
• 右子树所有节点的值 > 根节点的值
• 左右子树也都是二叉排序树

4.2 二叉排序树的操作

4.2.1 插入操作

struct BSTNode {
    int data;
    BSTNode *left, *right;
    BSTNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

BSTNode* insert(BSTNode* root, int val) {
    if (root == nullptr) return new BSTNode(val);
    if (val < root->data) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}

4.2.2 查找操作

BSTNode* search(BSTNode* root, int val) {
    if (root == nullptr || root->data == val) return root;
    if (val < root->data) return search(root->left, val);
    return search(root->right, val);
}

4.2.3 删除操作

BSTNode* findMin(BSTNode* root) {
    while (root->left != nullptr) root = root->left;
    return root;
}

BSTNode* remove(BSTNode* root, int val) {
    if (root == nullptr) return nullptr;
    if (val < root->data) {
        root->left = remove(root->left, val);
    } else if (val > root->data) {
        root->right = remove(root->right, val);
    } else {
        if (root->left == nullptr) {
            BSTNode* temp = root->right;
            delete root;
            return temp;
        }
        if (root->right == nullptr) {
            BSTNode* temp = root->left;
            delete root;
            return temp;
        }
        BSTNode* temp = findMin(root->right);
        root->data = temp->data;
        root->right = remove(root->right, temp->data);
    }
    return root;
}

五、二叉树的遍历

5.1 前序遍历

void preorder(BSTNode* root) {
    if (root == nullptr) return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

5.2 中序遍历

void inorder(BSTNode* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

5.3 后序遍历

void postorder(BSTNode* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}