企业官网建设流程全解析

网站的电子地图怎么做,什么叫网站开发应用框架,wordpress获取用户名,留言页面设计模板一文搞懂二叉树 二叉树是计算机科学中最基础的树形数据结构#xff0c;也是面试、算法开发、工程应用#xff08;如表达式解析、搜索索引#xff09;的核心考点。本文从 概念→分类→存储→遍历→操作→应用 层层递进#xff0c;结合 C 代码示例#xff0c;让你彻底吃透二…一文搞懂二叉树二叉树是计算机科学中最基础的树形数据结构也是面试、算法开发、工程应用如表达式解析、搜索索引的核心考点。本文从概念→分类→存储→遍历→操作→应用层层递进结合 C 代码示例让你彻底吃透二叉树。一、二叉树的核心定义与术语1. 什么是二叉树二叉树是n(n≥0)个节点的有限集合满足空树n0非空树有且仅有一个根节点其余节点分为两个互不相交的子集分别称为左子树和右子树且左、右子树也都是二叉树。核心约束每个节点的子节点数量不超过2左孩子、右孩子顺序不能颠倒。2. 必备术语看图理解更快假设一棵简单二叉树结构1 根节点 / \ 2 3 2是1的左孩子3是1的右孩子2和3互为兄弟节点 / 4 4是2的左孩子4是叶子节点术语定义根节点树的最顶层节点没有父节点如节点1叶子节点没有左、右子节点的节点如节点3、4节点的度节点拥有的子节点数叶子节点度为0节点1度为2节点2度为1树的深度/高度从根节点到最远叶子节点的边数上图深度为2根节点深度为0层根节点在第0层其子节点在第1层以此类推上图节点4在第2层左/右子树以节点左/右孩子为根的子树节点1的左子树是{2,4}右子树是{3}二、二叉树的常见分类重点区分根据节点的排列规则二叉树分为普通二叉树和特殊二叉树特殊二叉树在工程中更常用。1. 满二叉树定义除了叶子节点每个节点的度都为2所有非叶子节点都有左、右两个孩子且所有叶子节点都在同一层。特点节点数公式2^(h1) - 1h为树的深度结构对称。2. 完全二叉树定义按层序遍历顺序给节点编号每个节点的编号都与对应的满二叉树节点编号一致最后一层的叶子节点靠左排列。特点满二叉树是特殊的完全二叉树适合用数组存储无需额外存储指针节省内存父节点与子节点的索引关系若父节点索引为i左孩子为2i1右孩子为2i2。3. 二叉搜索树BSTBinary Search Tree工程中最常用的二叉树核心是有序性定义左子树的所有节点值 根节点值 右子树的所有节点值且左、右子树也都是二叉搜索树。核心特性中序遍历结果是严格递增的有序序列。优势查找、插入、删除的平均时间复杂度为O(logn)类似二分查找。4. 平衡二叉树定义任意节点的左、右子树的高度差的绝对值 ≤ 1避免二叉搜索树退化成链表。常见类型AVL树严格平衡、红黑树近似平衡工程中更常用如 Cmap/set的底层实现。优势保证查找、插入、删除的最坏时间复杂度为O(logn)。三、二叉树的存储结构C 实现二叉树有两种存储方式分别适用于不同场景。1. 链式存储最常用灵活用指针连接节点每个节点包含值、左孩子指针、右孩子指针。#include iostream #include vector #include queue #include memory // 智能指针避免内存泄漏 using namespace std; // 二叉树节点结构体C 推荐用智能指针管理内存 struct TreeNode { int val; unique_ptrTreeNode left; // 左孩子智能指针 unique_ptrTreeNode right; // 右孩子智能指针 // 构造函数 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };优势支持动态插入/删除节点适合不规则二叉树劣势需要额外存储指针内存开销略高。2. 顺序存储数组存储适合完全二叉树用数组存储节点利用完全二叉树的索引关系定位父/子节点。根节点存在arr[0]节点arr[i]的左孩子arr[2i1]右孩子arr[2i2]节点arr[i]的父节点arr[(i-1)/2]整数除法。示例完全二叉树[1,2,3,4]的数组存储数组索引0123节点值1234优势无需指针内存利用率高劣势非完全二叉树会浪费大量空间不支持灵活插入/删除。四、二叉树的核心操作遍历必须掌握遍历是指按一定顺序访问二叉树的所有节点且每个节点仅访问一次。二叉树的遍历分为深度优先遍历DFS和广度优先遍历BFS两大类其中 DFS 又分为 3 种顺序。1. 深度优先遍历DFS递归迭代实现核心思想先深后广优先遍历子树再遍历兄弟节点。1前序遍历根 → 左 → 右访问顺序先访问根节点 → 递归遍历左子树 → 递归遍历右子树。递归实现最简单void preOrder(TreeNode* root) { if (root nullptr) return; cout root-val ; // 1. 访问根节点 preOrder(root-left.get()); // 2. 遍历左子树 preOrder(root-right.get()); // 3. 遍历右子树 }迭代实现用栈模拟递归工程常用void preOrderIter(TreeNode* root) { if (root nullptr) return; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); cout node-val ; // 访问根节点 // 栈是“先进后出”先压右孩子再压左孩子 if (node-right) st.push(node-right.get()); if (node-left) st.push(node-left.get()); } }2中序遍历左 → 根 → 右访问顺序递归遍历左子树 → 访问根节点 → 递归遍历右子树。核心特性二叉搜索树的中序遍历结果是递增有序序列。递归实现void inOrder(TreeNode* root) { if (root nullptr) return; inOrder(root-left.get()); // 1. 遍历左子树 cout root-val ; // 2. 访问根节点 inOrder(root-right.get()); // 3. 遍历右子树 }迭代实现栈指针关键是“左链入栈”void inOrderIter(TreeNode* root) { if (root nullptr) return; stackTreeNode* st; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { // 左链全部入栈 while (cur ! nullptr) { st.push(cur); cur cur-left.get(); } cur st.top(); st.pop(); cout cur-val ; // 访问根节点 cur cur-right.get(); // 遍历右子树 } }3后序遍历左 → 右 → 根访问顺序递归遍历左子树 → 递归遍历右子树 → 访问根节点。递归实现void postOrder(TreeNode* root) { if (root nullptr) return; postOrder(root-left.get()); // 1. 遍历左子树 postOrder(root-right.get()); // 2. 遍历右子树 cout root-val ; // 3. 访问根节点 }迭代实现标记法区分节点是否已访问void postOrderIter(TreeNode* root) { if (root nullptr) return; stackpairTreeNode*, bool st; // 节点, 是否已访问 st.push({root, false}); while (!st.empty()) { auto [node, visited] st.top(); st.pop(); if (visited) { cout node-val ; // 已访问子树访问根节点 } else { st.push({node, true}); // 标记为待访问 // 栈先进后出根 → 右 → 左 if (node-right) st.push({node-right.get(), false}); if (node-left) st.push({node-left.get(), false}); } } }2. 广度优先遍历BFS层序遍历核心思想按层访问从上到下、从左到右遍历每一层的节点。实现工具队列先进先出代码实现void levelOrder(TreeNode* root) { if (root nullptr) return; queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); // 当前层的节点数 // 遍历当前层的所有节点 for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); cout node-val ; // 下一层节点入队 if (node-left) q.push(node-left.get()); if (node-right) q.push(node-right.get()); } cout endl; // 每层换行 } }遍历结果示例对如下二叉树1 / \ 2 3 / 4前序遍历1 2 4 3中序遍历4 2 1 3后序遍历4 2 3 1层序遍历1 → 2 3 → 4五、二叉搜索树BST的常见操作插入/删除/查找二叉搜索树的有序性决定了其操作的规律以下是核心操作的 C 实现。1. 查找节点核心逻辑类似二分查找根据节点值与根节点的大小关系递归/迭代查找左/右子树。// 查找值为target的节点返回节点指针 TreeNode* searchBST(TreeNode* root, int target) { if (root nullptr || root-val target) { return root; } // 小值查左大值查右 return target root-val ? searchBST(root-left.get(), target) : searchBST(root-right.get(), target); }2. 插入节点核心逻辑空树直接新建节点作为根非空树根据值的大小找到左/右子树的空位置插入不破坏有序性。// 插入值为val的节点返回新树的根 unique_ptrTreeNode insertBST(unique_ptrTreeNode root, int val) { if (root nullptr) { return make_uniqueTreeNode(val); // 空位置插入新节点 } if (val root-val) { root-left insertBST(move(root-left), val); // 插入左子树 } else if (val root-val) { root-right insertBST(move(root-right), val); // 插入右子树 } // 已存在该值直接返回避免重复 return root; }3. 删除节点最复杂分3种情况核心逻辑找到目标节点后根据节点的子节点数量分情况处理情况1目标节点是叶子节点 → 直接删除情况2目标节点只有一个子节点 → 用子节点替换目标节点情况3目标节点有两个子节点 → 用右子树的最小节点或左子树的最大节点替换目标节点再删除该最小节点。// 找到右子树的最小节点中序后继 TreeNode* findMin(TreeNode* root) { while (root-left ! nullptr) { root root-left.get(); } return root; } // 删除值为val的节点返回新树的根 unique_ptrTreeNode deleteBST(unique_ptrTreeNode root, int val) { if (root nullptr) return root; // 1. 找到目标节点 if (val root-val) { root-left deleteBST(move(root-left), val); } else if (val root-val) { root-right deleteBST(move(root-right), val); } else { // 2. 找到目标节点分情况处理 // 情况12无左孩子 或 无右孩子 if (root-left nullptr) { return move(root-right); // 右孩子替换 } else if (root-right nullptr) { return move(root-left); // 左孩子替换 } // 情况3有两个孩子找右子树最小节点 TreeNode* minNode findMin(root-right.get()); root-val minNode-val; // 替换值 // 删除右子树的最小节点 root-right deleteBST(move(root-right), minNode-val); } return root; }六、二叉树的工程应用场景数据搜索与排序二叉搜索树支持动态的插入、删除、查找适合频繁更新的数据集平衡二叉树红黑树Cstd::map/std::set的底层实现保证O(logn)时间复杂度。表达式解析表达式树叶子节点是操作数非叶子节点是运算符前序遍历对应前缀表达式后序遍历对应后缀表达式逆波兰表达式。哈夫曼树用于数据压缩如 Huffman 编码智驾场景中可压缩传感器采集的点云/图像数据减少存储和传输开销。决策树机器学习中的分类模型每个非叶子节点是一个特征判断叶子节点是分类结果用于目标检测的后处理分类。路径规划树形结构的遍历思想可用于智驾中的局部路径搜索如 A* 算法的状态树遍历。七、核心总结遍历是二叉树的基础前序/中序/后序DFS、层序BFS的递归迭代实现必须熟练中序遍历是二叉搜索树的关键。二叉搜索树的核心是有序性中序遍历有序插入/删除/查找都是基于有序性的二分思想。工程中优先用平衡二叉树避免二叉搜索树退化成链表时间复杂度退化为O(n)。C 实现注意内存管理推荐用unique_ptr/shared_ptr管理节点避免野指针和内存泄漏。八、实战小练习用本文的代码构建一棵二叉搜索树[5,3,7,2,4,6,8]分别输出前序、中序、后序、层序遍历结果删除节点3再输出中序遍历结果验证是否仍有序。