36_C数据结构树（待完善）

好的按照你的规范要求我为你罗列一个关于“树”的技术博客大纲结构清晰严格遵循标题编号与缩进规则。一、树的基本概念1. 树的定义(1) 树的逻辑结构a. 非线性结构i. 具有层次关系的数据结构⓵ 有且仅有一个根节点2. 树的基本术语(1) 节点相关a. 根节点b. 父节点与子节点i. 兄弟节点⓵ 叶子节点⓶ 内部节点(2) 树的属性a. 节点的度b. 树的度i. 深度与高度⓵ 层数二、树的数学表示1. 树的递归定义(1) 形式化表示KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…其中rrr为根节点FFF为子树的森林2. 树的遍历表示(1) 前序遍历序列(2) 后序遍历序列(3) 层序遍历序列三、二叉树的定义与性质1. 二叉树的定义(1) 每个节点最多有两个子树a. 左子树与右子树i. 左右子树严格区分2. 二叉树的性质(1) 第iii层最多节点数KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…(2) 深度为hhh的二叉树最多节点数KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…(3) 叶子节点与度为222的节点关系KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…3. 特殊二叉树(1) 满二叉树a. 所有非叶子节点度均为222(2) 完全二叉树a. 除最后一层外其他层节点数达到最大i. 最后一层节点靠左排列四、二叉树的存储结构1. 顺序存储(1) 基于数组实现a. 适用于完全二叉树i. 节点iii的左孩子2i2i2i⓵ 节点iii的右孩子2i12i12i1⓶ 节点iii的父节点⌊i/2⌋\lfloor i/2 \rfloor⌊i/2⌋2. 链式存储(1) 二叉链表/** Allman 风格*/KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…(2) 三叉链表a. 增加指向父节点的指针五、二叉树的遍历1. 深度优先遍历(1) 前序遍历a. 访问根节点b. 遍历左子树i. 遍历右子树(2) 中序遍历a. 遍历左子树b. 访问根节点i. 遍历右子树(3) 后序遍历a. 遍历左子树b. 遍历右子树i. 访问根节点2. 广度优先遍历(1) 层序遍历a. 使用队列辅助i. 从上到下、从左到右访问六、二叉树的常见变体1. 二叉搜索树(1) 定义与性质a. 左子树所有节点值小于根节点b. 右子树所有节点值大于根节点(2) 基本操作a. 查找O(log⁡n)O(\log n)O(logn)平均b. 插入O(log⁡n)O(\log n)O(logn)平均i. 删除O(log⁡n)O(\log n)O(logn)平均2. 平衡二叉树(1) AVL 树a. 平衡因子∣hL−hR∣≤1|h_L - h_R| \leq 1∣hL​−hR​∣≤1i. 左旋与右旋操作(2) 红黑树a. 节点颜色约束b. 近似平衡3. 堆(1) 最大堆a. 每个节点值大于等于子节点(2) 最小堆a. 每个节点值小于等于子节点4. 哈夫曼树(1) 带权路径长度最小a. 哈夫曼编码i. 前缀编码七、树的存储结构1. 双亲表示法(1) 数组存储节点a. 每个节点记录父节点下标2. 孩子表示法(1) 每个节点维护子节点链表3. 孩子兄弟表示法(1) 二叉树表示树a. 左指针指向第一个孩子b. 右指针指向下一个兄弟八、树的应用场景1. 文件系统(1) 目录结构a. 根目录为根节点2. 数据库索引(1) B 树与 B 树a. 多路搜索树i. 适用于磁盘存储3. 编译器设计(1) 抽象语法树a. 表示程序的结构4. 人工智能(1) 决策树(2) 博弈树5. 网络路由(1) 生成树协议a. 防止网络环路