云大《数据结构》课程教学课件第6章 树和二叉树(147P)

第6章树和二叉树云南大学《数据结构》课程教学课件Contents本章内容概览数据结构·第6章树和二叉树01树的基本概念02二叉树及其性质03二叉树的遍历04线索二叉树05树和森林06哈夫曼树及其应用CHAPTER01树的基本概念理解树的定义、表示方法、基本术语与核心性质Chapter06·Tree&BinaryTree树的定义树是一种递归定义的非线性层次数据结构，由n(n≥0)个节点组成的有限集合。当n=0时为空树；当n>0时，有且仅有一个根节点，其余节点互不相交地分为若干子树，每个子树本身也是一棵树。01节点集合树是n(n≥0)个节点的有限集合，n=0时称为空树有限集02根节点非空树有且仅有一个根节点(Root)，没有前驱唯一性03子树划分其余节点可分为m个互不相交的有限集合互斥性04递归特性每个集合Ti本身又是一棵树，称为根的子树Subtree05层次表达适合表示层次关系数据，如文件系统、组织架构HierarchyChapter06·树和二叉树树的表示方法树可以通过多种方式表示：图形表示法直观展示层次结构；嵌套集合表示法体现集合包含关系；广义表表示法用括号表达层次；孩子兄弟表示法便于存储实现。选择表示方法需考虑具体应用场景。图形表示法用节点（圆圈）表示数据元素，用边（线段）表示节点间关系根节点位于顶层，子节点依次向下展开，直观展示层次结构节点·边嵌套集合表示法将每个节点视为一个集合，子节点作为子集合嵌套在父集合中如{A,{B,{D},{E}},{C,{F}}}，体现包含与层次关系{A,{B},…}广义表表示法用括号表示层次关系，如A(B(D,E),C(F,G))根节点在表头，子树用逗号分隔放在括号内，便于书写和阅读A(B,C)Chapter06·TreeTerminology树的基本术语掌握树的核心术语是理解树结构的基础：节点是基本单元，度描述分支数量，层次和深度描述位置关系，父子、兄弟描述节点间的关系。节点相关术语01节点(Node)：包含数据元素及指向子树的指针02度(Degree)：节点拥有的子树数量03叶子节点(Leaf)：度为0的节点，也称终端节点04分支节点：度不为0的节点，也称非终端节点Node层次相关术语01层次(Level)：根为第1层，其子树根为第2层，以此类推02深度/高度：树中节点的最大层次数03节点的深度：从根到该节点的路径长度04节点的高度：从该节点到最远叶子的路径长度Level关系相关术语01父与孩子：直接上下级关系02兄弟(Sibling)：具有相同父节点的节点03祖先(Ancestor)：从根到该节点路径上的所有节点04子孙(Descendant)：以该节点为根的子树中的所有节点RelationChapter6·TreeProperties树的基本性质树具有重要的数学性质：节点数等于总度数加1；度为m的树第i层至多有m^(i-1)个节点；高度为h的m叉树至多有(m^h-1)/(m-1)个节点。这些性质是分析树相关算法复杂度的理论基础。节点与度数节点数等于所有节点度数之和加1，除根外每个节点恰有一条边连向父节点N=Σdeg+1层节点上限度为m的树第i层至多有m^(i-1)个节点(i≥1)，这是树的分支上限m^(i−1)总节点上限高度为h的m叉树至多有(m^h-1)/(m-1)个节点，等号成立时为满m叉树满m叉树最小高度n个节点的m叉树最小高度为⌈log_m(n(m-1)+1)⌉，对应最平衡的情况⌈log_m⌉唯一路径任意两个节点之间有且仅有一条路径相连，这是树的连通性特征连通性Chapter02二叉树及其性质掌握二叉树的定义、重要性质与两种存储结构Chapter06·Tree&BinaryTree二叉树的定义二叉树是n(n≥0)个节点的有限集合，或为空集，或由根节点和两棵互不相交的左右子树组成，左右子树有严格区分。递归递归定义空集或由根节点加左子树与右子树组成，子树本身也是二叉树，形成递归结构≤2节点约束每个节点最多两个子节点，分别称为左孩子和右孩子，度不超过2有序有序性左右子树位置不可交换，是与普通无序树的核心区别，顺序具有语义5种基本形态空树、仅根、根加左、根加右、根加左右共五种基本形态满·完全特殊类型满二叉树每层节点达最大值，完全二叉树仅末层可不满且靠左对齐Properties二叉树的重要性质二叉树具有优美的数学性质：第i层至多2^(i-1)个节点；深度k至多2^k-1个节点；叶子节点数n0与度为2节点数n2满足n0=n2+1。这些性质是设计和分析二叉树算法的理论基础。逐层翻倍第i层(i≥1)至多2^(i-1)个节点，每层节点数是上一层的2倍2^(i-1)深度上界深度为k的二叉树至多2^k−1个节点，满二叉树时取等号2^k−1叶子等式叶子节点数n0=度为2的节点数n2+1，与度为1的节点数无关n0=n2+1对数深度n个节点的完全二叉树深度为⌊log₂n⌋+1，属于对数级别层数⌊log₂n⌋+1索引关系完全二叉树中节点i的父节点为⌊i/2⌋，左孩子2i，右孩子2i+12i/2i+1STORAGESTRUCTURE二叉树的存储结构二叉树可采用顺序存储或链式存储。顺序存储用数组实现，适合完全二叉树但空间利用率低。链式存储用二叉链表实现，空间灵活，是最常用的存储方式。SEQUENTIAL顺序存储结构一维数组存储，节点i的父节点在⌊i/2⌋，左孩子2i，右孩子2i+1适合完全二叉树；一般二叉树需补空节点，造成空间浪费随机访问快、无需指针；插入删除效率低，空间可能浪费LINKED链式存储结构二叉链表：每个节点含data数据域、lchild左指针、rchild右指针n个节点的二叉链表有n+1个空指针域，可存储其他信息空间灵活、插入删除方便；无法直接访问父节点，需额外指针CHAPTER03二叉树的遍历掌握前序、中序、后序、层序四种遍历算法及其应用Chapter6·Tree&BinaryTree二叉树遍历的概念二叉树遍历是按特定规则访问每个节点一次且仅一次的过程，本质是将非线性结构线性化。根据访问根的时机分为前序、中序、后序(深度优先)和层序(广度优先)四种方式。遍历是查找、统计、复制等操作的基础。遍历定义按某种策略访问树中每个节点，且每个节点仅被访问一次Traversal遍历目的将树形非线性结构转化为线性序列，便于处理和分析线性化深度优先沿树的深度方向优先访问，含前序、中序、后序DFS广度优先按层次从上到下、从左到右访问，即层序遍历BFS运算基础查找、插入、删除、统计、复制等运算的实现基础FoundationPreorderTraversal前序遍历(PreorderTraversal)前序遍历按"根-左-右"顺序访问节点：先访问根节点，再前序遍历左子树，最后前序遍历右子树。遍历顺序访问根节点→前序遍历左子树→前序遍历右子树，简称"根左右"顺序，是二叉树最自然的遍历方式之一。ROOT-L-R递归算法若树非空，访问根节点，递归遍历左子树，递归遍历右子树。代码简洁直观，易于理解和实现。RECURSIVE非递归实现使用栈辅助，根节点入栈，循环出栈访问并入右子节点入左子节点，直到栈为空结束遍历。STACK应用场景复制二叉树结构、生成前缀表达式（波兰式）、目录文件系统遍历、XML文档序列化等。波兰式·树复制复杂度时间复杂度O(n)访问每个节点一次，空间复杂度O(h)，h为树高，最坏情况下退化为O(n)。O(n)/O(h)TreeTraversal·二叉树遍历中序遍历(InorderTraversal)中序遍历按"左-根-右"顺序访问节点：先中序遍历左子树，再访问根节点，最后中序遍历右子树。对二叉搜索树进行中序遍历可得到有序序列，这是中序遍历最重要的应用特性。遍历顺序中序遍历左子树→访问根节点→中序遍历右子树，简称"左根右"左根右递归算法若树非空，递归遍历左子树，访问根节点，递归遍历右子树递归非递归实现使用栈，沿左链入栈，出栈访问，转向右子树，循环直到树空且栈空栈结构重要性质对二叉搜索树(BST)中序遍历，得到递增有序序列，用于排序和查找有序序列应用场景二叉搜索树排序、表达式中缀形式输出、有序数据提取排序·提取CHAPTER06·BINARYTREE后序遍历PostorderTraversal后序遍历按"左-右-根"顺序访问节点：先后序遍历左子树，再后序遍历右子树，最后访问根节点。其特点是根节点最后被访问，适合删除二叉树和计算后缀表达式。遍历顺序后序遍历左子树→后序遍历右子树→访问根节点，简称"左右根"左右根递归算法若树非空，递归遍历左子树，递归遍历右子树，最后访问根节点。递归实现简洁直观递归非递归实现需使用栈并记录访问状态，节点需两次入栈才能访问，首次标记已访问左子树双入栈重要应用释放二叉树空间（先删子树再删根）、计算后缀表达式（逆波兰式求值）逆波兰式树的重构前序+中序或后序+中序可唯一确定二叉树，但前序+后序不能唯一确定唯一确定BFS·Application·Reconstruction层序遍历与遍历应用层序遍历是二叉树按层级访问的核心算法，广泛应用于树的重建、最短路搜索与层次化数据分析核心概念层序遍历（Breadth-FirstSearch）按树的深度层级逐层访问节点，通常借助队列实现：①根节点入队，标记当前层节点数②逐层出队，子节点按左右顺序入队③记录每层节点值，形成层级序列Time:O(n)|Space:O(w)典型应用场景树的重建通过层序序列结合中序遍历，可唯一确定二叉树结构，实现序列化与反序列化最短路径在无权图中，BFS保证首次到达即为最短路径，适用于迷宫求解与网络路由层次分析按层统计节点数、计算树高、寻找最左/最右节点，支持组织架构与文件系统遍历关键实现要点队列管理使用双端队列或循环队列优化内存，避免频繁扩容带来的性能开销层级追踪通过当前层节点计数或队列长度变化，精确划分不同层级边界空节点处理序列化时需保留空节点占位（如null），确保重建时结构信息完整迭代优化递归实现易栈溢出，推荐迭代版本；可结合尾递归优化降低空间复杂度核心优势：层序遍历天然适合处理层级相关的问题，是理解树结构与图算法的重要基础，掌握其变形技巧（如之字形遍历、按层求和）可应对绝大多数面试与实际工程场景CHAPTER04线索二叉树理解线索化原理，掌握线索树的构建与遍历操作Chapter6·ThreadedBinaryTree线索二叉树的概念n个节点的二叉链表有n+1个空指针域。线索化利用这些空指针存储遍历序列中的前驱或后继信息，形成线索二叉树。线索化后可不借助栈和递归进行遍历，提高空间效率。EmptyPointersn+1空指针域数量TotalPointers2n指针域总数ChildPointersn−1指向孩子的指针01n个节点的二叉链表有2n个指针域，其中n−1个指向孩子，n+1个为空指针02线索（Thread）：将空指针改为指向遍历序列中前驱或后继的指针03前驱线索：左指针为空时指向遍历前驱；后继线索：右指针为空时指向遍历后继04节点结构增加LTag和RTag标志位：0表示指向孩子，1表示指向线索05线索化目的：利用空指针空间，实现无栈遍历，提高遍历的空间效率Chapter6·ThreadedBinaryTree中序线索二叉树的构建中序线索化在中序遍历过程中完成：维护前驱指针pre，当前节点左空则指向前驱，前驱右空则指向当前节点作为后继。构建完成后可通过线索直接找到前驱后继。01前驱指针线索化在中序遍历中完成，需维护前驱指针pre，初始为NULL，用于记录当前访问节点的前驱pre=NULL02前驱线索当前节点p左指针空时，p→lchild=pre，LTag=1，建立前驱线索，将空指针转化为线索LTag=103后继线索前驱pre右指针空时，pre→rchild=p，RTag=1，建立后继线索，完成双向线索连接RTag=104递归遍历每次访问后更新pre=p，递归处理右子树，直到遍历完成，确保所有节点都被线索化pre=p05直接访问构建后可在O(1)时间找到中序前驱和后继，无需递归和栈，大幅提升遍历效率O(1)TimeTRAVERSALALGORITHM线索二叉树的遍历操作在线索树中查找后继：若RTag=1则rchild即为后继；若RTag=0则后继为右子树最左下节点。查找前驱类似。遍历线索树从最左下节点开始，循环查找后继即可完成遍历，无需递归和栈，空间复杂度O(1)。查找中序后继若节点p的RTag=1，则p->rchild直接指向中序后继若RTag=0，后继为p右子树中"最左下"的节点（沿左链到底）时间复杂度：最坏O(h)，平均O(1)O(1)平均查找中序前驱若节点p的LTag=1，则p->lchild直接指向中序前驱若LTag=0，前驱为p左子树中"最右下"的节点（沿右链到底）对称于查找后继的算法LTag判定遍历线索树从根节点沿左链找到最左下节点（中序第一个节点）循环调用"查找后继"函数，直到后继为空无需递归和栈，空间复杂度O(1)，时间复杂度O(n)O(n)遍历CHAPTER05树和森林掌握树的存储结构及树、森林与二叉树的转换方法CHAPTER06·TREE&BINARYTREE树的存储结构树的存储方式包括双亲表示法、孩子表示法和孩子兄弟表示法，其中孩子兄弟表示法可将树转为二叉树形式，应用最广泛。双亲表示法用数组存储节点，每个节点包含data和parent（父节点下标）查找父节点O(1)；查找孩子需遍历整个数组适合频繁查询父节点的应用场景ARRAY+PARENTO(1)孩子表示法每个节点用头节点+孩子链表存储，链表节点记录孩子下标查找孩子方便；查找父节点需遍历所有链表可结合双亲表示法形成双亲孩子表示法HEADER+LIST链表孩子兄弟表示法每个节点含firstchild和nextsibling两个指针可将任意树转化为二叉树形式，统一存储结构树的链式存储中最常用的方法，便于统一处理DUALPOINTER最常用CHAPTER06·TREECONVERSION树与二叉树的转换树转二叉树规则：节点的第一个孩子作为左孩子，兄弟作为右孩子。转换后根节点无右子树，转换一一对应可逆还原。转换规则节点的第一个孩子变成左孩子，兄弟节点变成右孩子左孩右兄具体步骤加线（兄弟间）、断线（保留第一个孩子）、旋转调整层次加·断·转根节点特征转换后二叉树根节点右子树为空，因为根没有兄弟节点右子树空遍历对应树的前序对应二叉树前序，树的后序对应二叉树中序前↔前后↔中逆转换左孩子是第一个孩子，右孩子是兄弟，可还原原树结构可逆还原Chapter6·Tree&BinaryTree森林与二叉树的转换森林转二叉树：先将每棵树转为二叉树，再将第2棵起各二叉树的根依次作为前一棵根的右孩子连接。森林转二叉树①将森林中每棵树分别转换为二叉树②从第二棵起，将其根作为前一棵根的右孩子③依次连接得到完整二叉树，转换一一对应转换方法遍历对应关系森林先序=二叉树先序遍历森林中序=二叉树中序遍历可用二叉树遍历算法统一处理森林遍历等价实际应用文件系统目录结构通过转换统一处理XML/HTML的DOM树可用二叉树算法遍历统一树、森林与二叉树的数据结构体系工程落地CHAPTER06哈夫曼树及其应用掌握最优二叉树的构造方法与哈夫曼编码原理第六章·树和二叉树路径长度与带权路径长度路径长度是根到节点的边数；节点带权路径长度=权值×路径长度；树的带权路径长度WPL是所有叶子的带权路径长度之和。WPL最小的二叉树称为最优二叉树(哈夫曼树)，权值大的节点靠近根时WPL较小。01路径长度(PathLength)：从根节点到某节点经过的边数（或节点数−1）02节点的带权路径长度：该节点的权值×从根到该节点的路径长度03树的带权路径长度WPL：所有叶子节点的带权路径长度之和04公式：WPL=Σ(wᵢ×lᵢ)

，其中wᵢ是第i个叶子的权值，lᵢ是其路径长度05最优树思想：权值越大的叶子越靠近根，WPL越小，这就是构造最优二叉树的核心原则CHAPTER06·树和二叉树哈夫曼树的定义与构造哈夫曼树是WPL最小的二叉树(最优二叉树)。构造算法：从n个带权叶子开始，每次选两个最小权值节点合并为新父节点(权值为两者之和)，重复n-1次得到最终树。哈夫曼树有n个叶子则共有2n-1个节点，无度为1的节点。哈夫曼树定义01给定n个权值，构造有n个叶子的二叉树，使WPL最小的称为哈夫曼树02哈夫曼树是最优二叉树，同一组权值的哈夫曼树形态可能不唯一03n个叶子的哈夫曼树共有2n-1个节点，其中n-1个是内部节点哈夫曼算法1初始化：将n个带权节点视为n棵只有根的二叉树，组成森林2选择：从森林中选两棵根权值最小的树合并，新根权值为两者之和3重复：将新树加入森林，删除原两棵树，直到森林只剩一棵树4共执行n-1次合并，生成n-1个内部节点，最终得到哈夫曼树HuffmanEncoding哈夫曼编码哈夫曼编码是基于哈夫曼树的前缀编码：从根到叶子的路径，左分支标0右分支标1。任何字符编码都不是其他编码的前缀，保证解码唯一性。高频字符编码短、低频字符编码长，实现最优数据压缩。前缀编码任一字符编码不是其他字符编码