首页 书籍 深入浅出程序设计竞赛

# 二叉树的概念和建立

二叉树是数据结构中的一种，它是特殊形式的树状数据结构。在二叉树中，每个节点最多有两个子节点：通常称为左子节点和右子节点。二叉树的概念和建立是计算机科学中非常基础且重要的内容，广泛应用于各种算法和数据处理场景中。

# 二叉树的概念

  1. 节点：二叉树的基本单位，包含节点值及指向左子节点和右子节点的指针（或引用）。
  2. 根节点：二叉树最顶端的节点，是二叉树的起点。
  3. 父节点与子节点：如果一个节点含有子节点，则该节点称为其子节点的父节点；相应地，这些子节点是该节点的子节点。
  4. 叶子节点：没有子节点的节点称为叶子节点。
  5. 深度：从根节点到某一节点的最长路径的长度。
  6. 高度：从某一节点到叶子节点的最长路径的长度。
  7. 层：二叉树的一层由所有深度相同的节点组成。根节点位于第 0 层。

# 二叉树的类型

  • 完全二叉树：除了最底层外，每层都是满的，并且所有节点都尽可能地集中在左侧。
  • 满二叉树：一个高度为 h，并且由 2^h - 1 个节点构成的二叉树。
  • 平衡二叉树（AVL 树）：任一节点的两个子树的高度差不超过 1 的二叉树。
#include <iostream>
// 定义二叉树节点结构
class TreeNode {
public:
    int value; // 节点存储的值
    TreeNode* left; // 指向左子节点的指针
    TreeNode* right; // 指向右子节点的指针
    // 构造函数
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};
int main() {
    // 手动构建二叉树
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    // 使用二叉树
    // 注意：这里只是创建了二叉树，如果要进行遍历或其他操作，需要额外实现相关函数
    // 最后，不要忘记释放分配的内存
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;
    return 0;
}
# 题目：


# 二叉树的遍历


二叉树的遍历是指按照某种顺序访问二叉树中的每个节点，确保每个节点都被访问一次。主要有三种深度优先遍历方式：前序遍历、中序遍历和后序遍历，以及一种广度优先遍历方式：层序遍历。


# 深度优先遍历


    

  1. 前序遍历（Pre-order Traversal）

      

    • 访问根节点
      • 

    • 递归地对根节点的左子树进行前序遍历
      • 

    • 递归地对根节点的右子树进行前序遍历
      • 

    

    2. 

  2. 中序遍历（In-order Traversal）

      

    • 递归地对根节点的左子树进行中序遍历
      • 

    • 访问根节点
      • 

    • 递归地对根节点的右子树进行中序遍历
      • 

    

    3. 

  3. 后序遍历（Post-order Traversal）

      

    • 递归地对根节点的左子树进行后序遍历
      • 

    • 递归地对根节点的右子树进行后序遍历
      • 

    • 访问根节点
      • 

    

    4. 



# 广度优先遍历


    

  1. 

    层序遍历
    

    （Level-order Traversal）
    

      

    • 从根节点开始，逐层访问树中的每个节点，同一层的节点按照从左到右的顺序访问。
      • 

    

    2. 



#include <iostream>
#include <queue>
using namespace std;

class TreeNode {
public:
    int value;
    TreeNode *left, *right;
    TreeNode(int value) : value(value), left(nullptr), right(nullptr) {}
};

// 前序遍历
void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
}

// 后序遍历
void postorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->value << " ";
}

// 层序遍历
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();
        cout << current->value << " ";
        if (current->left != nullptr) q.push(current->left);
        if (current->right != nullptr) q.push(current->right);
    }
}

int main() {
    // 构建二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // 遍历二叉树
    cout << "前序遍历: ";
    preorderTraversal(root);
    cout << "\n中序遍历: ";
    inorderTraversal(root);
    cout << "\n后序遍历: ";
    postorderTraversal(root);
    cout << "\n层序遍历: ";
    levelOrderTraversal(root);

    // 清理
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}




# 题目：前中求后


# 二叉树的综合应用


# 题目：二叉搜索树


您需要写一种数据结构，来维护一些数（ 都是绝对值 10^9 以内的数字）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 q 不超过 104：


    

  1. 查询 x 数的排名（排名定义为比当前数小的数的个数 +1。若有多个相同的数，应输出最小的排名）。
    2. 

  2. 查询排名为 x 的数。
    3. 

  3. 求 x 的前驱（前驱定义为小于 x，且最大的数）。若未找到则输出 −2147483647。
    4. 

  4. 求 x 的后继（后继定义为大于 x，且最小的数）。若未找到则输出 2147483647。
    5. 

  5. 插入一个数 x。
    6. 



# 分析


# 代码


#include <iostream>
#include <map>
using namespace std;
class NumberSet {
private:
    map<int, int> nums; // 存储每个数及其出现次数
public:
    // 插入一个数 x
    void insert(int x) {
        nums[x]++;
    }
    // 查询 x 数的排名
    int rank(int x) {
        int cnt = 0;
        for (auto it = nums.begin(); it != nums.end(); ++it) {
            if (it->first >= x) break;
            cnt += it->second;
        }
        return cnt + 1;
    }
    // 查询排名为 x 的数
    int find_by_rank(int x) {
        int cnt = 0;
        for (auto it = nums.begin(); it != nums.end(); ++it) {
            cnt += it->second;
            if (cnt >= x) return it->first;
        }
        return -1; // 表示未找到
    }
    // 求 x 的前驱
    int predecessor(int x) {
        int result = -2147483647;
        for (auto it = nums.begin(); it != nums.end(); ++it) {
            if (it->first >= x) break;
            result = it->first;
        }
        return result;
    }
    // 求 x 的后继
    int successor(int x) {
        for (auto it = nums.begin(); it != nums.end(); ++it) {
            if (it->first > x) return it->first;
        }
        return 2147483647;
    }
};
int main() {
    NumberSet ns;
    ns.insert(5);
    ns.insert(3);
    ns.insert(8);
    ns.insert(3); // 插入重复元素
    cout << "Rank of 3: " << ns.rank(3) << endl;
    cout << "Number with rank 2: " << ns.find_by_rank(2) << endl;
    cout << "Predecessor of 4: " << ns.predecessor(4) << endl;
    cout << "Successor of 5: " << ns.successor(5) << endl;
    return 0;
}

      

          
          
      

  


   


    

  
    
      
    
    更新于