数据基础及结构 3

第6章树和二叉树1问题导入：层次化数据的高效解决方案

现实中的层次数据实例文件系统目录、企业组织架构、网页DOM树等，均体现数据元素间逐层递进的层次关系。

线性结构的局限性线性表、数组难以高效存储多对多层次数据，导致存储效率低、操作复杂。

树结构的核心优势自然刻画“一个对象拥有多个子对象”关系，灵活表达层次化组织，操作（查找/插入等）效率高。

二叉树的典型应用凭借结构简洁性，广泛应用于编译原理、数据压缩、人工智能、数据库索引等领域。目录01.树的定义和基本术语02.二叉树的定义、性质与存储03.遍历二叉树04.线索二叉树05.树和森林06.应用案例6.1树的定义和基本术语树的定义定义树是n(n≥0)个结点的有限集。在一棵非空树中：1.有且仅有一个特定的称为根（root）的结点。2.当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，...，Tm，每个集合本身又是一棵树，并且称为根的子树。图示图：典型的树结构示例（节点A为根节点）

树的抽象数据类型定义

数据对象与数据关系数据对象D是具有相同特性的数据元素集合；数据关系R为二元关系，含唯一根结点，其余结点划分为互不相交的子树。

查找类基本操作包括求根结点（Root(T)）、当前结点值（Value(T，cur_e)）、双亲（Parent(T，cur_e)）、左孩子（LeftChild(T，cur_e)）、树深度（TreeDepth(T)）等。

插入与删除操作插入操作如InsertChild(T，p，i，c)（将树c插入为p的第i棵子树）；删除操作如DeleteChild(T，p，i)（删除p的第i棵子树）。

遍历与初始化操作遍历操作TraverseTree(T，Visit())按某种次序访问所有结点；初始化操作包括InitTree(T)（置空树）、CreateTree(T，definition)（按定义构造树）。树的基本术语（一）基本概念结点：包含数据元素及若干指向其子树的分支。结点的度：结点拥有的子树数目。例如，A的度为3。叶子（终端结点）：度为0的结点。例如，E，K，L，G，H，I，M。非终端结点（分支结点）：度不为0的结点。例如，A，B，C，D，F。树的度：树内所有结点度的最大值。此树的度为3。树的示例树的基本术语（二）基本概念孩子/双亲：结点子树的根称为该结点的孩子，该结点称为孩子的双亲。例如，D是A的孩子，A是D的双亲。兄弟：同一个双亲的孩子之间互称兄弟。例如，H，I，J互为兄弟。祖先：结点的祖先是从根到该结点所经分支上的所有结点子孙：某结点子树中的结点都是该结点的子孙层次：从根开始定义，根为第一层，其孩子为第二层，依此类推。深度（高度）：树中结点的最大层次。此树的深度为4。森林：m(m≥0)棵互不相交的树的集合。6.2二叉树二叉树的定义与基本形态二叉树的递归定义二叉树或为空树，或由一个根结点加上两棵互不相交的左子树和右子树组成，左、右子树本身也是二叉树。二叉树的5种基本形态包括：空二叉树、仅有根结点、根+左子树、根+右子树、根+左子树+右子树。二叉树与普通树的区别二叉树每个结点最多有2个子树且左右子树有序；普通树结点子树数无限制且子树无序。二叉树的五种基本形态形态说明空二叉树只有根结点的二叉树根结点只有左子树根结点只有右子树根结点既有左子树又有右子树图示二叉树的性质核心性质

二叉树的性质核心性质

二叉树的性质核心性质

特殊二叉树：满二叉树与完全二叉树满二叉树的定义与特点

完全二叉树的定义与特点与满二叉树前n个结点编号一一对应，叶子结点仅在最后两层，左子树深度≥右子树深度。满二叉树与完全二叉树的异同相同点：每层结点从左至右排列；不同点：满二叉树所有层结点数均满，完全二叉树最后一层可不满但需从左到右连续。二叉树的性质核心性质

二叉树的性质核心性质

二叉树的顺序存储二叉树的顺序存储示例存储原理顺序存储结构使用一组连续的存储单元来存放二叉树中的结点。通常是按照从上到下、从左到右的顺序对二叉树的结点进行编号，然后将结点存入数组中对应下标的位置。

适用场景特别适合完全二叉树。对于完全二叉树，顺序存储可以充分利用存储空间，且通过简单的公式就能计算出父子节点的位置。二叉树的链式存储（二叉链表）存储原理链式存储结构用指针来表示结点之间的逻辑关系。最常用的是二叉链表，每个结点包含三个域：数据域(data)、左指针域(lchild)、右指针域(rchild)。//----二叉树的二叉链表表示----typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左、右孩子指针}BiTNode,*BiTree;图示与说明二叉链表结构灵活，可表示任意二叉树，存储空间利用率高。二叉树的链式存储（三叉链表）存储原理若需快速查找结点双亲,可增加一个指向其双亲结点的指针域,形成三叉链表。///----二叉树的三叉链表表示----typedefstructTriTNode{//结点结构TElemTypedata;structTriTNode*lchild,*rchild;//左、右孩子指针structTriTNode*parent;//双亲指针}TriTNode,*TriTree;图示与说明

二叉树的存储结构对比顺序存储结构使用一维数组按层次存储完全二叉树，编号为i的结点存于下标i处，适用于满二叉树和完全二叉树，空间利用率高。

链式存储结构：二叉链表每个结点含数据域、左孩子指针和右孩子指针，n个结点有n+1个空链域，适用于非完全二叉树，操作灵活。

链式存储结构：三叉链表在二叉链表基础上增加双亲指针域，可快速查找双亲结点，空间开销略增，适用于需频繁访问双亲的场景。

存储结构对比与适用场景顺序存储适合完全二叉树的紧凑存储；链式存储适合任意二叉树，尤其是频繁插入删除的场景。6.3遍历二叉树遍历的定义与意义遍历的概念与搜索路径

遍历二叉树是按某条搜索路径巡访每个结点，使每个结点被访问且仅被访问一次。访问含义广泛，如输出信息等，是获取树中信息的关键操作。按层次遍历路径

从上到下、从左到右按层次依次访问结点，是一种直观易懂的搜索路径。先左后右遍历路径

先遍历左子树，再遍历右子树，基于此有先序、中序、后序三种有效遍历组合。先右后左遍历路径

假如用L、D、R分别表示遍历左子树、访问根结点和遍历右子

树。先遍历右子树，再遍历左子树，有DRL、RDL、RLD等组合，应用场景相对较少。递归遍历算法：先序、中序、后序操作定义：若二叉树为空则空操作，否则先访问根结点，再递归先序遍历左子树，最后递归先序遍历右子树。算法实现通过递归调用完成。先序遍历递归定义与实现01操作定义：若二叉树为空则空操作，否则先递归中序遍历左子树，再访问根结点，最后递归中序遍历右子树。实现方式与先序类似，仅访问根结点时机不同。中序遍历递归定义与实现02操作定义：若二叉树为空则空操作，否则先递归后序遍历左子树，再递归后序遍历右子树，最后访问根结点。其递归实现体现了左右子树遍历完成后访问根的特点。后序遍历递归定义与实现03二叉树的遍历——先序遍历操作定义访问根结点。先序遍历左子树。先序遍历右子树。示例与结果ABCDEFGHK二叉树的遍历——先序遍历算法二叉树的遍历——中序中序遍历(LDR)1.中序遍历左子树。2.访问根结点。3.中序遍历右子树。BDCAHGKFE二叉树的遍历——后序中序遍历(LRD)1.后序遍历左子树。2.后序遍历右子树。3.访问根结点。DCBHKGFEA二叉树的遍历——层次遍历操作定义与思路层次遍历是指从上到下、从左到右依次访问二叉树的每一层节点。实现思路：通常借助队列（Queue）来实现。示例与结果遍历结果：A→B→C→D→E二叉树的遍历——非递归遍历算法算法思路利用栈模拟递归过程，从根结点开始，向左走到尽头并将结点入栈，栈顶元素出栈访问后，移动到其右孩子，重复操作直至栈空且指针为空。线性结构与树结构核心对比

结构关系线性结构：元素仅含单一前驱/后继（一对一）；树结构：结点可含多个子结点（一对多），呈现“根-子-孙”层级。

存储与复杂度线性结构：存储为顺序/链式，简单易实现；树结构：非线性嵌套，支持递归定义，操作复杂度更高但表达更灵活。

访问与遍历线性结构：通过索引/指针顺序访问（如栈LIFO、队列FIFO）；树结构：遍历方式多样（前序/中序/后序/层次），适配复杂逻辑关系。

典型应用线性结构：表达式计算、任务调度（强顺序性场景）；树结构：目录索引、XML文档、AI决策树（层次化数据场景）。

遍历算法的应用01统计叶子结点个数先序遍历二叉树，遍历过程中判断结点是否为叶子（左右孩子均为空），若是则计数器增1。算法6-4通过递归实现该功能。

02求二叉树深度基于后序遍历，先分别求左、右子树深度，二叉树深度为左右子树深度最大值加1。算法6-5体现了这一递归求解过程。

03复制二叉树后序遍历待复制二叉树，先复制左、右子树，再创建当前结点副本并连接子树。算法6-6通过递归完成二叉树的复制操作。

04遍历是二叉树操作的基础遍历可用于求结点双亲、孩子，判定层次等操作，也可在遍历中生成结点建立存储结构，是实现二叉树各种操作的核心基础。6.4线索二叉树线索二叉树的概念与作用问题背景：传统二叉链表的局限二叉链表存储结构中，仅能直接获取结点的左、右孩子信息，无法直接得知其前驱和后继。n个结点的二叉链表存在n+1个空链域，造成空间浪费。核心思路：利用空链域存储线索通过修改空指针域，存储结点在遍历序列中的前驱和后继信息，将非线性结构线性化，实现高效访问。基本定义：线索与线索二叉树线索：指向结点前驱或后继的指针；线索链表：增加标志域（LTag/RTag）的二叉链表；线索二叉树：加上线索的二叉树，可实现快速遍历。

线索二叉树的存储结构结点结构：标志域与指针域结点包含lchild（左指针）、LTag（左标志）、data（数据）、RTag（右标志）、rchild（右指针）。LTag/RTag为0表示指针指向孩子，为1表示指向线索。

标志域的含义LTag=0：lchild指向左孩子；LTag=1：lchild指向前驱。RTag=0：rchild指向右孩子；RTag=1：rchild指向后继。二叉树线索化对二叉树进行某种次序遍历并转换为线索二叉树的过程称为线索化中序线索二叉树

对应的中序序列为B

D

C

AHGKF

E建立线索链表线索化本质二叉链表空指针改造为前驱/后继线索，通过遍历过程动态修改空指针实现。

中序线索化关键指针遍历时维护pre（刚访问结点）与p（当前结点），pre始终指向p的前驱结点。

线索化核心目标利用空指针存储遍历顺序关系，解决传统二叉链表仅存父子关系、无法直接获取前驱后继的问题。

voidInThreading(BiThrTreep){if(p){//对以p为根的非空二叉树进行线索化InThreading(p->lchild);//左子树线索化if(!p->lchild)//建立前驱线索{p->LTag=Thread;p->lchild=pre;}if(!pre->rchild)//建立后继线索{pre->RTag=Thread;pre->rchild=p;}pre=p;//保持pre指向p的前驱InThreading(p->rchild);//右子树线索化}}//InThreading建立线索链表StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//中序遍历二叉树T,并将其中序线索化,Thrt指向头结点Thrt=newBiThrNode();//创建头结点if(!Thrt)returnerror;//内存分配失败返回错误Thrt->LTag=Link;Thrt->RTag=Thread;//建立头结点Thrt->rchild=Thrt;//右指针回指if(!T){Thrt->lchild=Thrt;//若二叉树空,则左指针回指}else{Thrt->lchild=T;pre=Thrt;InThreading(T);//中序遍历进行线索化pre->rchild=Thrt;//最后一个结点线索化pre->RTag=Thread;Thrt->rchild=pre;}returnOK;}线索二叉树遍历

遍历高效性：无需栈辅助线索二叉树遍历时间复杂度为O(n)，通过线索直接访问前驱/后继，避免递归或栈空间开销，适用于频繁遍历场景。

双向线索链表的优势添加头结点，左指针指向根，右指针指向中序最后一个结点；首结点左线索和尾结点右线索均指向头结点，支持双向遍历（从首结点顺后继或从尾结点顺前驱）。StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向头结点,头结点的左链lchild指向根结点,可参见线索化算法//中序遍历二叉线索树T的非递归算法,对每个数据元素调用函数Visit()p=T->lchild;//p指向根结点while(p!=T){//空树或遍历结束时,p==Twhile(p->LTag==Link)p=p->lchild;//找到第一个结点if(!Visit(p->data))returnerror;//访问其左子树为空的结点while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//访问后继结点}p=p->rchild;//p进至其右子树根}returnok;}6.5树和森林树的存储结构（一）：双亲表示法定义与思想双亲表示法是一种顺序存储结构，用一组连续的存储空间来存储树的结点。每个结点包含两个域：数据域和双亲域。数据域存储结点的数据信息，双亲域存储该结点的双亲在数组中的位置。结构定义与图示#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;//数据域intparent;//双亲位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intr,n;}PTree;数组中每个元素代表一个节点，parent值为-1表示根节点。树的存储结构（二）：孩子表示法定义与思想孩子表示法是将每个结点的孩子结点排列起来，以单链表作为存储结构，称为孩子链表。n个结点共有n个孩子链表（叶子结点的单链表为空），然后将n个结点的数据和n个孩子链表的头指针组成一个顺序表。结构定义与图示//-----树的孩子链表存储表示-----typedefstructCTNode{//孩子结点intchild;structCTNode*next;}*ChildPtr;typedefstruct{Elemdata;ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根结点的位置}CTree;每个节点作为一个表头，其后链接的是它所有的孩子节点。树的存储结构（三）：孩子兄弟表示法定义与思想孩子兄弟表示法又称二叉树表示法，或二叉链表表示法。即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟结点。结构定义与图示typedefstructCSNode{TElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;每个节点有两个指针，一个指向它的第一个孩子，另一个指向它的下一个兄弟。

树的存储结构双亲表示法以连续空间存储树的结点，每个结点包含数据域和指示双亲位置的指示器。优点是便于查找双亲结点，缺点是求孩子结点需遍历整个结构。

孩子表示法将每个结点的孩子结点排列成单链表，头指针组成顺序存储的线性表。优点是便于涉及孩子的操作，可与双亲表示法结合使用。

孩子兄弟表示法每个结点包含数据域、指向第一个孩子的指针和指向下一个兄弟的指针。能有效反映树的层次结构和结点关系，便于实现树的各种操作。树转换为二叉树：核心思想与步骤核心思想将树的孩子关系转换为二叉树的左孩子关系，将树的兄弟关系转换为二叉树的右孩子关系。这是树转二叉树的本质。转换三步骤加线：在所有兄弟结点之间加一条连线。抹线：对树中每个结点，只保留它与第一个孩子结点的连线。旋转：顺时针旋转整棵树，调整结构。森林与二叉树的转换

转换对应关系森林与二叉树存在一一对应关系，树的二叉链表表示与二叉树的存储结构相同，只是解释不同，森林的第一棵树子树森林对应二叉树左子树，剩余树对应右子树。森林转换为二叉树转换步骤1.将森林中的每一棵树分别转换为二叉树。2.将第一棵二叉树作为结果二叉树的根。3.将第二棵二叉树的根节点作为第一棵二叉树根节点的右孩子。4.依次类推，将后续二叉树连接为前一棵树的右子树。核心思想森林中的树与树之间是兄弟关系，因此在转换为二叉树时，它们依次作为前一棵树的右子树，从而将整个森林串联成一棵完整的二叉树。二叉树转换为森林转换步骤1.若二叉树B为空，则转换的森林F为空。2.若二叉树B非空，F首棵树根为二叉树B的根；首棵树的子树森林由B的左子树转换而成的森林，剩余森林由B右子树转换

树和森林的遍历树的遍历先根遍历：先访问根结点，再依次先根遍历各子树；后根遍历：先依次后根遍历各子树，再访问根结点；按层次遍历：自上而下、自左至右访问每个结点。

森林的遍历先序遍历：访问第一棵树的根，先序遍历其根的子树森林，再先序遍历剩余树的森林；中序遍历：中序遍历第一棵树根的子树森林，访问根，再中序遍历剩余树的森林。

与二叉树遍历的关系树的先根、后根遍历分别对应二叉树的先序、中序遍历；森林的先序、中序遍历即为其对应二叉树的先序、中序遍历。

树的计数基本概念相似二叉树指结构相同但结点数据不同；等价二叉树要求结构和数据都相同。树的计数问题是求具有n个结点的不同形态树的数目。

二叉树的计数

树的计数推导

6.6应用案例

哈夫曼树及其应用01哈夫曼树的定义与关键概念哈夫曼树（最优二叉树）是带权路径长度最短的二叉树，权值越大的结点离根越近。路径是结点间的路线，路径长度为边的数量，带权路径长度（WPL）是所有叶子结点权值与路径长度乘积之和。

02哈夫曼算法步骤1.初始化：将n个权值构造成n棵单根结点二叉树；2.选择与合并：选取权值最小的两棵树作为左右子树，构造新树，根权值为两子树权值之和；3.更新集合：将新树加入集合，删除原两棵树；4.重复操作至集合只剩一棵树。

03哈夫曼树构造实例以权值{7，5，2，4}为例，构造过程：先合并2和4得6，再合并5和6得11，最后合并7和11得18，最终WPL=7×1+5×2+4×3+2×3=35，为最优结构。

04哈夫曼编码在数据压缩中的应用以字符出现频率为权值构建哈夫曼树，左分支赋0、右分支赋1，从根到叶子路径形成前缀编码。高频字符编码短，低频字符编码长，实现数据压缩，且解码唯一无歧义。

哈夫曼树及其应用01哈夫曼树的定义与关键概念哈夫曼树（最优二叉树）是带权路径长度最短的二叉树，权值越大的结点离根越近。路径是结点间的路线，路径长度为边的数量，带权路径长度（WPL）是所有叶子结点权值与路径长度乘积之和。

02哈夫曼算法步骤1.初始化：将n个权值构造成n棵单根结点二叉树；2.选择与合并：选取权值最小的两棵树作为左右子树，构造新树，根权值为两子树权值之和；3.更新集合：将新树加入集合，删除原两棵树；4.重复操作至集合只剩一棵树。

03哈夫曼树构造实例以权值{7，5，2，4}为例，构造过程：先合并2和4得6，再合并5和6得11，最后合并7和11得18，最终WPL=7×1+5×2+4×3+2×3=35，为最优结构。

04哈夫曼编码在数据压缩中的应用以字符出现频率为权值构建哈夫曼树，左分支赋0、右分支赋1，从根到叶子路径形成前缀编码。高频字符编码短，低频字符编码长，实现数据压缩，且解码唯一无歧义。01哈夫曼编码的实现哈夫曼树的存储结构采用动态数组存储哈夫曼树结点，每个结点含权值、双亲及左右孩子指针typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码表02从叶子到根逆向求编码算法从叶子结点出发，通过双亲指针逆向追溯至根，左孩子记0、右孩子记1，将编码存入工作空间，最后复制到编码表。需动态分配编码空间，时间复杂度O(n²)。03从根遍历求编码算法（无栈非递归）利用结点状态标志（0：未访问，1：左子树访问，2：右子树访问），遍历哈夫曼树，左分支加0、右分支加1，遇到叶子结点时登记编码。无需栈辅助，空间效率更高。04编码与解码过程分析编码：根据字符权值构建哈夫曼树，生成前缀编码；解码：从根开始，按编码序列（0左1右）遍历树，直至叶子结点得到字符，实现无歧义解码。哈夫曼树无度为1的结点，含n个叶子时共有2n-1个结点。人工智能中的决策树决策树的概念与构建过程决策树是树结构，分支结点表示特征测试，叶子结点代表类别或决策结果。构建从根开始，选择最优特征划分数据，递归划分至满足停止条件（如最大深度、样本