【25届秋招备战C++】数据结构篇-二叉树

【25届秋招备战C++】数据结构篇-二叉树

• 一、定义
• • 树的基础知识
  • 特殊二叉树
  • • 满二叉树
    • 完全二叉树
    • 二叉搜索树
    • 二、二叉树的存储结构
    • • 顺序存储
      • 链式存储
      • 三、二叉树的遍历-深度优先搜索（DFS）和广度优先搜索
      • • 深度优先遍历的实现-递归法
        • • 前序遍历（Preorder Traversal）
          • 中序遍历（Inorder Traversal）
          • 后序遍历（Postorder Traversal）
          • 深度优先遍历的实现-迭代法
          • 层序遍历的实现
          • 四、二叉树的重建
          • • 由前序和中序重建二叉树
            • 由中序和后序重建二叉树
            • 五、二叉搜索树的基础操作
            • • 1. 插入（Insert）
              • 2. 删除（Delete）
              • 3. 查找（Search）
              • 4. 更新（Update）
              • ��、参考

                一、定义

                由 n≥0 个节点与节点之间的关系组成的有限集合。当 n=0 时称为空树，当 n>0 时称为非空树。

                （）

                树的基础知识

                树的节点：由一个数据元素和若干个指向其子树的树的分支组成。

                节点的度：一个节点所含有的子树个数。

                （）

                叶子节点（终端节点）：度为 0 的节点。

                分支节点（非终端节点）：度不为 0 的节点。

                树的度：树中节点的最大度数。

                孩子节点（子节点）：一个节点含有的子树的根节点称为该节点的子节点。

                父亲节点（父节点）：如果一个节点含有子节点，则这个节点称为其子节点的父节点。

                兄弟节点：具有相同父节点的节点互称为兄弟节点。

                节点的层次：从根节点开始定义，根为第 1 层，根的子节点为第 2 层，以此类推。

                树的深度（高度）：所有节点中最大的层数。

                堂兄弟节点：父节点在同一层的节点互为堂兄弟。、

                路径：树中两个节点之间所经过的节点序列。、

                路径长度：两个节点之间路径上经过的边数。、

                节点的祖先：从该节点到根节点所经过的所有节点，被称为该节点的祖先。

                节点的子孙：节点的子树中所有节点被称为该节点的子孙。

                有序树与无序树：如果将树中节点的各个子树看做是从左到右是依次有序的（即不能互换），则称该树为 「有序树」。反之，如果节点的各个子树可以互换位置，则成该树为 「无序树」。

                二叉树（Binary Tree）：树中各个节点的度不大于 2 个的有序树，称为二叉树。通常树中的分支节点被称为 「左子树」 或 「右子树」。二叉树的分支具有左右次序，不能随意互换位置。

                特殊二叉树

                满二叉树

                满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

                完全二叉树

                完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。

                二叉搜索树

                1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

                2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

                3.它的左、右子树也分别为二叉排序树

                平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

                二、二叉树的存储结构

                顺序存储

                二叉树的顺序存储结构使用一维数组来存储二叉树中的节点，节点存储位置则采用完全二叉树的节点层次编号，按照层次从上至下，每一层从左至右的顺序依次存放二叉树的数据元素。在进行顺序存储时，如果对应的二叉树节点不存在，则设置为「空节点」。完全二叉树或满二叉树适合采用顺序存储结构。

                链式存储

                二叉树采用链式存储结构时，每个链节点包含一个用于数据域 val，存储节点信息；还包含两个指针域 left 和 right，分别指向左右两个孩子节点，当左孩子或者右孩子不存在时，相应指针域值为空。

                三、二叉树的遍历-深度优先搜索（DFS）和广度优先搜索

                1.深度优先搜索

                前序遍历：根节点-左子树-右子树

                中序遍历：左子树-根节点-右子树

                后序遍历：左子树-右子树-根节点

                2.广度优先搜索

                层序遍历：按照层次从上至下，每一层从左至右

                深度优先遍历的实现-递归法

                前序遍历（Preorder Traversal）

                步骤：

                访问根节点。

                递归地对左子树进行前序遍历。

                递归地对右子树进行前序遍历。

                C++ 实现：

                #include #include struct TreeNode {    int value;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}};void preorder(TreeNode* root, std::vector& result) {    if (root == nullptr) return;    result.push_back(root->value); // 访问根节点    preorder(root->left, result);    // 遍历左子树    preorder(root->right, result);   // 遍历右子树}void printPreorder(TreeNode* root) {    std::vector result;    preorder(root, result);    for (int val : result) {        std::cout     if (root == nullptr) return;    inorder(root-left, result);    // 遍历左子树    result.push_back(root-value); // 访问根节点    inorder(root-right, result);   // 遍历右子树}void printInorder(TreeNode* root) {    std::vector result;    inorder(root, result);    for (int val : result) {        std::cout     if (root == nullptr) return;    postorder(root-left, result);    // 遍历左子树    postorder(root-right, result);   // 遍历右子树    result.push_back(root-value); // 访问根节点}void printPostorder(TreeNode* root) {    std::vector result;    postorder(root, result);    for (int val : result) {        std::cout     int value;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}};void iterativePreorder(TreeNode* root) {    std::stack        // 访问当前节点        if (current != nullptr) {            std::cout             // 弹出栈顶元素            current = stack.top();            stack.pop();            current = current-right; // 访问右子树        }    }    std::cout     std::stack        if (current != nullptr) {            // 将当前节点及其所有左子节点入栈            stack.push(current);            current = current-left;        } else {            // 弹出栈顶元素并访问            current = stack.top();            stack.pop();            std::cout     std::stack        if (current != nullptr) {            stack.push(current);            current = current-left; // 先访问左子树        } else {            TreeNode* node = stack.top();            if (node-right != nullptr && lastVisited != node-right) {                // 如果右子树未被访问，访问右子树                current = node->right;            } else {                // 访问当前节点                std::cout value     int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};void levelOrder(TreeNode* root) {    if (root == nullptr) return;    std::queue        TreeNode* node = queue.front();        queue.pop();        std::cout right) queue.push(node->right);    }    std::cout     int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};// 辅助函数，用于从给定的前序和中序遍历序列中构建二叉树TreeNode* buildTree(const std::vector    if (preorder.empty() || inorder.empty()) return nullptr;    // 前序遍历的第一个元素是根节点    int rootVal = preorder[0];    TreeNode* root = new TreeNode(rootVal);    // 在中序遍历序列中找到根节点的位置    int rootIndex = 0;    for (int val : inorder) {        if (val == rootVal) {            rootIndex = inorder.indexOf(val);            break;        }    }    // 递归构建左子树和右子树    root-left = buildTree(preorder, inorder, 0, rootIndex);    root->right = buildTree(preorder, inorder, rootIndex + 1, inorder.size() - rootIndex - 1);    return root;}// 重载构建函数，接受前序和中序遍历序列的子序列TreeNode* buildTree(const std::vector& preorder, const std::vector& inorder, int start, int end) {    if (start > end) return nullptr;    // 前序遍历的第一个元素是当前子树的根节点    int rootVal = preorder[start];    TreeNode* root = new TreeNode(rootVal);    // 在中序遍历序列中找到根节点的位置    int rootIndex = 0;    for (int i = start; i         if (inorder[i] == rootVal) {            rootIndex = i;            break;        }    }    // 计算左子树和右子树的前序遍历序列的索引    int leftSize = rootIndex - start;    int rightSize = end - rootIndex + 1;    // 递归构建左子树和右子树    root-left = buildTree(preorder, inorder, start + 1, start + leftSize);    root->right = buildTree(preorder, inorder, start + leftSize + 1, start + leftSize + rightSize);    return root;}//由中序和后序重建二叉树#include #include struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};// 辅助函数，用于从给定的后序和中序遍历序列中构建二叉树TreeNode* buildTree(const std::vector& postorder, const std::vector& inorder) {    if (postorder.empty() || inorder.empty()) return nullptr;    // 后序遍历的最后一个元素是根节点    int rootVal = postorder.back();    TreeNode* root = new TreeNode(rootVal);    postorder.pop_back(); // 移除根节点    // 在中序遍历序列中找到根节点的位置    int rootIndex = std::find(inorder.begin(), inorder.end(), rootVal) - inorder.begin();    // 递归构建左子树和右子树    // 左子树的中序遍历序列长度为 rootIndex，右子树的中序遍历序列长度为 inorder.size() - rootIndex - 1    root->left = buildTree(postorder, inorder, 0, rootIndex);    root->right = buildTree(postorder, inorder, rootIndex + 1, inorder.size() - 1);    return root;}

                五、二叉搜索树的基础操作

                二叉搜索树（BST）是一种特殊的二叉树，其中每个节点都满足以下性质：对于任意节点node，其左子树中的所有节点的值都小于node的值，其右子树中的所有节点的值都大于node的值。这使得二叉搜索树非常适合进行增删改查操作。以下是二叉搜索树的基本操作的C++实现：

                1. 插入（Insert）

                插入操作需要维护BST的性质。新节点将被插入到树中适当的位置。

                struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};TreeNode* insert(TreeNode* root, int val) {    if (root == nullptr) return new TreeNode(val);    if (val val) root->left = insert(root->left, val);    else if (val > root->val) root->right = insert(root->right, val);    return root;}

                2. 删除（Delete）

                删除操作稍微复杂，需要考虑三种情况：删除的节点是叶子节点、有一个子节点、有两个子节点。如果节点有两个子节点，需要找到其右子树的最小节点（或左子树的最大节点）来替换它。

                TreeNode* minValueNode(TreeNode* node) {    TreeNode* current = node;    while (current && current->left != nullptr) {        current = current->left;    }    return current;}TreeNode* deleteNode(TreeNode* root, int key) {    if (root == nullptr) return root;    if (key val) root->left = deleteNode(root->left, key);    else if (key > root->val) root->right = deleteNode(root->right, key);    else {        if (root->left == nullptr) {            TreeNode* temp = root->right;            delete root;            return temp;        } else if (root->right == nullptr) {            TreeNode* temp = root->left;            delete root;            return temp;        }        TreeNode* temp = minValueNode(root->right);        root->val = temp->val;        root->right = deleteNode(root->right, temp->val);    }    return root;}

                3. 查找（Search）

                查找操作是从根节点开始，根据值的大小向左或向右遍历树。

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

                4. 更新（Update）

                更新操作类似于查找操作，首先找到要更新的节点，然后更改其值。

                void updateNode(TreeNode* root, int key, int new_val) {    if (root == nullptr) return;    if (key == root->val) {        root->val = new_val;        return;    }    if (key val) updateNode(root->left, key, new_val);    else updateNode(root->right, key, new_val);}

                六、参考

                算法通关手册

                代码随想录