数据结构 树和二叉树 第六章树和二叉树 主讲：张昱 重点：二叉树的性质、遍历；二叉树 yuzhang@ustc.edu 与森林（树）的相互转换 0551-3603804 难点：树和二叉树应用的算法设计 1/106 2/106 第六章树和二叉树 6.1树的定义和基本术语 6.1树的定义和基本术语 ■树的定义（递归定义） 6.2二叉抛 树是(n≥0)个结点（元素）的有限桌， 6.3遍历二叉树和线索二叉树 若n=0,称为空树。 若n>0,则 6.4树和森林 。有且仅有一个特定的称为根的结点「oot; 6.6赫夫曼树及其应用 ·当n>1时，除根以外的其他结燕划分为州m>0)个互 6.5树与等价问题 不相交的有限果T, 12 其中 一个廉合本身又是 一棵树，并且称为根的子树。 6.7回溯法与树的遍历 6.8树的计数 且对老≥沿磅元楚特离关原集 3/106 4/106 图 6.1树的定义和基本术语 6.1树的定义-其他表示 ■树的表示 ■树的其他表示 嵌囊集合、广义表表示、凹入表示 且击古★古★★女女女女★★南女古★出 百唐★★★★击★量★★★★★金★量 E女★★★女金金金★★南女击在击 B 工女击击女量业量击★★女女女量 E C★大★南击★量量重古★★★★南重 ★女者★★量业量击★★★★★量 D去齿齿南南女金金金齿齿去南在南金 工★★★★者重量量★者★者★而重 J古南者者者击出者★者南者南击 (A(B(E,F(K,L)).C(G).D(H L J))) 5/106 图 6/106 图
1/106 数据结构——树和二叉树 主讲：张昱 yuzhang@ustc.edu 0551-3603804 2/106 重点：二叉树的性质、遍历；二叉树 与森林(树)的相互转换 难点：树和二叉树应用的算法设计 第六章 树和二叉树 3/106 第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 6.5 树与等价问题 6.7 回溯法与树的遍历 6.8 树的计数 4/106 6.1 树的定义和基本术语 树的定义(递归定义) 树是n(n≥0)个结点(元素)的有限集。 若 n=0，称为空树。 若 n > 0，则 有且仅有一个特定的称为根的结点root； 当n > 1时，除根以外的其他结点划分为m(m>0) 个互 不相交的有限集T1, T2,… Tm，其中每一个集合本身又是 一棵树，并且称为根的子树。 且对任意的i(m≥i≥1), Ti 存在惟一的结点xi , 有 <root, xi >∈H H为树中元素之间的二元关系集 5/106 6.1 树的定义和基本术语 树的表示 A A B C D E F G H I J K L 6/106 6.1 树的定义-其他表示 树的其他表示 嵌套集合、广义表表示、凹入表示 G C A B D H I J E K F L (A(B(E, F(K,L)), C(G), D(H, I, J))) A***************** B**************** E*************** F*************** K************** L************** C**************** G*************** D**************** H*************** I*************** J***************
ADT Tree 轰据对象：D-∈mSet,i1,2n,n≥0； 6.1树的定义-基本术语 数据关系：若D为空集，则称为空树； 若D仅含一个数据元素，则R为空集，否则R=田，H是如下二元 。基本术语 关系： 第1层 1)在D中存在难-的称为根的数据元素r0ot,它在关系H下无丽 第2层 高度为4 2)者D红oot≠中，则存在D-红a0t的一个刻分D1,D2,,D ®自@面①①第3层 mP0)(D表示构成第i保子树的结点集，对任煮j手k1≤jk≤ 令结点 ®① m)有D;门Dx=中，且对任煮的i1≤i≤m,唯一存在数据元素均∈ 孩子 一第4层 D,有<00此，>∈H(H表示结点之间的父子关系方 结点的度 ”丸亲 ◆树的度 )对应于D-红ot的分，Hro0t,P,,00t2有唯-的 令结点的层次 ◆兄弟 ◆树的深度/高度 一个划分H,压。，Hnm0)(氏表示第i探子树中的父子关系， 令终增结点（叶子） 祖先 有序树 对任意j≠k1jk≤m)有HH,=中，且对任意0≤i≤m,H是 冬非终墙结点（分支结点） 令子开 ◆无序树 D:上的二元关系，①，H)是一霖符合本定义的树，称为根r0ot的 必内部结点 ◆堂兄弟 令森林 子树。 71106 回 图 基本操作： InitTree(&T) 操作结果：构造空树T Value(T,cur_e) DestroyTree(&T) 初始条件：树T已存在，cre是T中某个结点 初始条件：树T已存在 操作结果：返回cur_e的值 操作结果：销毁树T Assign(T,&cur_e,value) ClearTree(&T) 初始条件：树T已存在，cre是T中某个结点 初始条件：树T已存在 操作结果：结点cure赋值为aue 操作结果：将树T清为空树 Parent(T,cur e) TreeEmpty(T) 初始条件：树T已存在，cre是T中某个结点 初始条件：树T已存在 操作结果：若ce是T的非根结点，则返国它的双亲，否则函数值 操作结果：若T为空树，则返回TRU亚，否则返回FALSE 为“空” CTreeDepth(T) LeftChild(T,cur e) 初始条件：树T已存在 初始条件：树T已存在，cure是T中某个结点 操作结果：返回树T的深度 操作结果：若cre是T的非叶子结点，则返回它的最左孩子，否则 Root(T 返国“空” 初始条件：树T已存在 操作结果：返回T的根 图 10/106 图 RightSibling(T,cur e) 初条传：树T已存在，re是T中某个结点 操作结果：着cm_e有右兄弟，则返回它的右兄弟，否则返回“空” 6.1树的定义-ADT Tree InsertChild(&T p,i,c) 初始条作：树T已存在，p指舟T中某个结点，1≤1≤p所指结点的度 ADT Tree +上，非空树c与T不相交 操作结果：插入c为T中p所指结点的第1根子树， ·查找：Parent(T,cur_e)LeftChild(T,cur_e) DeleteChild(&T,p,i) Rightsibling(T,cur_e) 初衡承作：树T已存在印指向T中某个结点，1i≤p所指结点的度 ,插入：InsertChild(&T,&p,i,c) 操作结果：测除T中p所指结点的第1樱子树· TraverseTree(T,visit() ,则除：DeleteChild(&T,&p,i) 初始条传：树T已存在，是州结点操作的应用函数 ,通历：TraverseTree(T,Visit()) 操作结果：技某种次序对T的每个结点调用函数is()一次且至多一 次。一且s()失败，则操作失数 JADT Tree 1/106 图 12/106 图
7/106 结点 结点的度 结点的层次 终端结点(叶子) 非终端结点(分支结点) 内部结点 6.1 树的定义-基本术语 基本术语 A B C D E F G H I J K L 第1层 第2层 第3层 第4层 高度为4 孩子 双亲 兄弟 祖先 子孙 堂兄弟 树的度 树的深度/高度 有序树 无序树 森林 8/106 9/106 10/106 11/106 12/106 6.1 树的定义-ADT Tree ADT Tree 查找：Parent(T,cur_e) LeftChild(T, cur_e) RightSibling(T, cur_e) 插入：InsertChild(&T, &p, i, c) 删除：DeleteChild(&T, &p, i) 遍历：TraverseTree(T, Visit())
6.2二叉树 6.2二叉树-性质(1) ■二叉树的定义（递归定义） 。二叉树的性质 ·特点：毒个结点重多只有两暴子批，子树有左友之分 ,性质1：二叉树的第层至多有21个结点（≥1） ·二叉树v5度不大于2的有序树 ·性质2：深度为h的二叉树至多有2-1个结点(h≥) .ADT BinaryTree 思考：性质1和性质2推广到k见树，结果会如何？ (-1)/-1) ,性质3：m。一2+1 结点总数n+西十m 分支数m-1■m1+2n2 思考：若包含有个结点的树中只有叶子结点和度为店 的站点，则过树中有多少叶子站点？ 二叉树 有序树 囵 n■。+ng广1■kng>H。■-(0-1)Vk 13/106 147106 图 6.2二叉树-性质(2) 主6.2二又树-性质(3) ,满二叉树：一棵深度为k且有2-1个结点的二叉树 ·性质4：具有m个结点的完全二叉树的深度为Llog,n小+1 (k≥0) 由性质221.1<n≤21或2-5n<2 ,完全二义树：对于深度为的完全二叉树，则 )前层为满二树： 于是k-1≤og2n<k 2)幕k层站燕依次占据最左边的位置： 3)一个站燕有右棋于，则它必有左孩子： 例：若一个完全二又树有1450个站点，则度为1的结点 4)度为1的结点个散为0成1 个数为1，度为2的结点个数为724，叶子结点的个 5)叶子结点只可能在层次最大的两层上出现： 数为725，有725个结点有左抗于，有724个结点 若其右分支下的于孙的最大层次为弘则 有右就子；被树的高度为1山。（性质3、性质4以及完 其左分支下的于孙的最大层次必为成+1，Q 全二叉树的特征) 15/106 圆 16/106 图 6.2二叉树-性质(4) 6.2二叉树-顺序存储结构(1) ,性质5：如果对一棵有个结点的完全二叉树的结点按层 ,二叉树的顺序存储结构 序编号（从第1层到第10g2n+1层，每层从左到右），则 ,类型定义 对任一结点i(1SiSm),有 typedef ElemType SqBiTree[MAX_TREE_SIZE]; (1)如果1，则结点i是二又树的根，无双亲；如果i>L, /0号单元存情根结点 则其双亲是结点山/2： 1)依帮性质5，用一组地址连埃的存储草元依次自上而 (2)如果2i>m,则结点无左孩于（结点为叶于结燕）否 下、自左至右存储完全二叉树上的结点元素； 则其左孩于是结燕2i: —结点在存储区中的相时位置反映它们辽辑上的关系 (3)如果21+1>n,则站点无右就子；否则其右雅子是 2)仅道用于完全二又抛 结点2i+1. ·一般二叉树的顺序存储方法 思考：性质5推广到k又树，站果会如何？ 通过补应站点，将一敝的二义树变成完全二义树 图 空间开铺大！ 17/106 18/106 图
13/106 6.2 二叉树 二叉树的定义(递归定义) 特点：每个结点至多只有两棵子树，子树有左右之分 二叉树 vs 度不大于2的有序树 ADT BinaryTree 二叉树 有序树 14/106 6.2 二叉树-性质(1) 二叉树的性质 性质1：二叉树的第i层至多有2i-1个结点(i≥1) 性质2：深度为h的二叉树至多有2h –1个结点(h≥1) 思考：性质1和性质2推广到k叉树，结果会如何？ 性质3：n0 = n2 + 1 结点总数 n = n0 + n1 + n2 分支数 n-1 = n1 + 2n2 思考：若包含有n个结点的树中只有叶子结点和度为k 的结点，则该树中有多少叶子结点？ ki-1 (kh-1)/(k-1) n = n0+nk, n-1 = knk => n0 = n-(n-1)/k 15/106 6.2 二叉树-性质(2) 满二叉树：一棵深度为k且有2k –1个结点的二叉树 (k≥0) 完全二叉树：对于深度为k的完全二叉树，则 1) 前k-1层为满二叉树； 2) 第k层结点依次占据最左边的位置； 3) 一个结点有右孩子，则它必有左孩子； 4) 度为1的结点个数为0或1 5) 叶子结点只可能在层次最大的两层上出现； 6) 对任一结点，若其右分支下的子孙的最大层次为l, 则 其左分支下的子孙的最大层次必为l或l+1。 16/106 6.2 二叉树-性质(3) 性质4：具有n个结点的完全二叉树的深度为 由性质2 2k-1-1 < n ≤ 2k-1 或 2k-1 ≤ n < 2k 于是 k-1 ≤ log2n < k 例：若一个完全二叉树有1450个结点，则度为1的结点 个数为 1 ，度为2的结点个数为 724 ，叶子结点的个 数为 725 ，有 725 个结点有左孩子，有 724 个结点 有右孩子；该树的高度为 11 。(性质3、性质4以及完 全二叉树的特征) ⎣log2 n⎦ +1 17/106 6.2 二叉树-性质(4) 性质5：如果对一棵有n个结点的完全二叉树的结点按层 序编号(从第1层到第 层，每层从左到右)，则 对任一结点i (1 ≤ i ≤ n)，有 (1) 如果i=1，则结点i是二叉树的根，无双亲；如果i >1, 则其双亲是结点 ； (2) 如果2i > n，则结点i无左孩子(结点i为叶子结点)；否 则其左孩子是结点2i ； (3) 如果2i + 1> n，则结点i无右孩子；否则其右孩子是 结点2i + 1。 思考：性质5推广到k叉树，结果会如何？ ⎣ ⎦ log2 n +1 ⎣ ⎦ i / 2 18/106 6.2 二叉树-顺序存储结构(1) 二叉树的顺序存储结构 类型定义 typedef ElemType SqBiTree[MAX_TREE_SIZE]; //0号单元存储根结点 1) 依据性质5，用一组地址连续的存储单元依次自上而 下、自左至右存储完全二叉树上的结点元素； ——结点在存储区中的相对位置反映它们逻辑上的关系 2) 仅适用于完全二叉树 一般二叉树的顺序存储方法 通过补虚结点，将一般的二叉树变成完全二叉树 空间开销大！
6.2二叉树-顺序存储结构(2) 6.2二叉树-链式存储结构 ·二叉燃的链式在储结控 ③ 2345000067 ·引入辅助空间表示结点之间的关系：双亲-孩子 二又能表（左、右孩于链城） 三又链表（双亲及左、右城子链规） ·二叉链的类型定义（动态链表） ⑥ ⑦ typedef struct BiTNode{ ElemType data; 。空间利用率问愿： 川左右孩子指针 在最杯情况下，一个深度为k且只有k个结点的单 struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 支树树中不存在度为2的站点)，则需要长废为21的 若有n个结点，则共有2n个梵提：其中m-1不为空，指向 一维数组， 孩于；男外+1个为空能城 19/106 回 20/106 图 6.3遍历二叉树和线索二叉树 6.3遍历二叉树1) ·遍历二叉树 。遍历二叉树 。基于先/中后序遍历算法的应用 按一定的搜索路径对树中的每一结点访问且仅访问一次 ,塘历时的搜案路线（的定，先左后右，D-根，L~左子树，R-右子树） ■为什么强调使用函数调用的结果 ·先（根）序遭历：1245673(DLR) ■先/中后序遍历的非递归算法 ① ·中（根）序德历：4265713(LDR) ■层次遍历算法及其应用 ■二叉树的创建方法 ·后（报）序浦历：46Z5231(LRD ■线索二又树 ,层次地历，1234567 2L/106 回 22/106 6.3-遍历二叉树(2) 6.3-遍历二叉树(3) ·先/中/后序速历的区别 端历路径 ,遍历算法的递归实现 如右图，三者经过的捷寒略线 是相同的：只是访问结点的时 。二叉树的递归定义性质，决定了它的很多算法都可用 先序访问 递归实现，遗历算法就是其中之一。 机不同。每一结点在整个搜索 路线中会经过3次： 。对于二叉树的遗历，可以不去具体考虑各子问题（左 。第一次进入到该轴点 子树、根、右子树)的遭历结果是什么，而去考虑如 此时访问该结点，称为先序遭历 何由各子问题的求解结果构成原问题（二叉树）的薄历 。由左子树回测到该结点 a 结果—递归规律的确定。必须注意的是，当二叉树 此时访问该结点，称为中序遍历 小到一定程度，即空树时，应直接给出解答—递归 由右子树回测到该结点 结束条件及处理。 此时访问该结点，称为后序遗历 中序访问后序访问 23/106 图 24/106 图
19/106 6.2 二叉树-顺序存储结构(2) 空间利用率问题： 在最坏情况下，一个深度为k且只有k个结点的单 支树(树中不存在度为2的结点)，则需要长度为2k-1的 一维数组。 1 2 3 4 5 6 7 1 2 3 4 5 0 0 0 0 6 7 20/106 6.2 二叉树-链式存储结构 二叉树的链式存储结构 引入辅助空间表示结点之间的关系：双亲-孩子 二叉链表(左、右孩子链域) 三叉链表(双亲及左、右孩子链域) 二叉链的类型定义(动态链表) typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 }BiTNode, *BiTree; 若有n个结点，则共有2n个链域；其中n-1不为空，指向 孩子；另外n+1个为空链域 21/106 6.3 遍历二叉树和线索二叉树 遍历二叉树 基于先/中/后序遍历算法的应用 为什么强调使用函数调用的结果 先/中/后序遍历的非递归算法 层次遍历算法及其应用 二叉树的创建方法 线索二叉树 22/106 6.3 -遍历二叉树(1) 遍历二叉树 按一定的搜索路径对树中的每一结点访问且仅访问一次 遍历时的搜索路线(约定：先左后右，D-根,L-左子树,R-右子树) 先(根)序遍历：1 2 4 5 6 7 3 (DLR) 中(根)序遍历：4 2 6 5 7 1 3 (LDR) 后(根)序遍历：4 6 7 5 2 3 1 (LRD) 层次遍历：1 2 3 4 5 6 7 1 2 3 4 5 6 7 23/106 6.3 -遍历二叉树(2) 先/中/后序遍历的区别 如右图，三者经过的搜索路线 是相同的；只是访问结点的时 机不同。每一结点在整个搜索 路线中会经过3次： 第一次进入到该结点 此时访问该结点，称为先序遍历 由左子树回溯到该结点 此时访问该结点，称为中序遍历 由右子树回溯到该结点 此时访问该结点，称为后序遍历 24/106 6.3 -遍历二叉树(3) 遍历算法的递归实现 二叉树的递归定义性质，决定了它的很多算法都可用 递归实现，遍历算法就是其中之一。 对于二叉树的遍历，可以不去具体考虑各子问题(左 子树、根、右子树)的遍历结果是什么，而去考虑如 何由各子问题的求解结果构成原问题(二叉树)的遍历 结果——递归规律的确定。必须注意的是，当二叉树 小到一定程度，即空树时，应直接给出解答——递归 结束条件及处理
6.3-遍历二叉树(4) 6.3-基于先中后序遍历算法的应用 ·先序速历 ,基于先/中/后序遍历的算法应用 Status PreOrderTraverse(BiTree T, Status (*Visit )(ElemType e)X ,基于先庄遭历的二又攒（二又链）的创建 if(TI=NULLX ,统计二叉榭中叶子结点的数目 if(Visit(T->data） ,整放二叉榭的所有结点空间 if PreOrderTraverse(T>lchild,Visit ) ,副除并程放二叉树中以元靠值为x的结点作为根的 if PreOrderTraverse(T->rchild,Visit)) 各子城 return OK; 银设二叉树中结点数为山高度为山 return ERROR: ,求位于二叉抛先庄序列中第k个位置的结点的值 则Ta,h=Om,sn,h)=Ob) Log:nJ+15h <n 分析问题本身的特征，选择合道的遍历次序！ else return OK; 应用递归编写算法，简洁！ 25/106 回 注意：递归站来泰洗%用遂归调用的站果 图 例1基于先序遍历的二叉树（二叉链）的创建 例1基于先序遵历的二叉树（二叉链）的创建 【本例梅证】。 如何基于二又相的先序、中序、后序遍历的速归算法进行问超解？， Status CreateBiTree(BiTree &T){ 【思路】， 按先序次序输入二叉树中结点的值（一个字特） 先序满历hO1dav 的建CreateBfTr 川空格字特表示空树，构造二叉链表表示的二叉树T 入 二叉体表示的二叉树的头指什T了带痘话点的先开序列山 scanf(&ch); 前人的表成方式 数 由输人设盆输人脚( if ch==)T=NULL: 时蓝占的有6害里 二义表示的三树的针T else 希出的表现方式 由出备希出 if (!(T=(BiTNode*)malloc(sizeof(BiTNode)))) 2国（日南）的 T-NUIL 小一ND DATA(表示虚结点的值 桑件及处理， exit(OVERFLOW); 直模求附 T-NULL T->data=ch; 根点的可问 CreateBiTree(T->lchild): Visit(T-data 于网”直墙束霸 T-dats =ch CreateBiTree(T->rchild); 年道 使用谜调用的解 return OK: )/CreateBiTree 使用速阳调用的解) PreOrder Tranerse(T-reuld CreateBiTree(T-tell) 27/106 28/106 图 例2统计二叉树中叶子结点的数目(1) 例2统计二叉树中叶子结点的数目(2) 【本例特征】 【算法1全局的计数悬】 如何通过全局变量、变参、返回值三种渠道返回处理结果？ ∥n为叶子结点的计数器 【思路】 int n=0; void leaf(BiTree T) 在遗历二叉树时，对一些特殊的结点（无左右孩子）进行计 敷。可以将遗历算法的结点访问操作修政为对特殊结点的判定和 ∥利用二叉树的先序速历 计数过程，需要注意的是计数器的处理方式。 if (T!-NULL) 可以有以下几种计数处理： ∥访问结点>叶子的判定和计数 ·用遭历函数的返回值传出求得的叶子结点的数目： if(T->lchild=-NULL &T->rchild=-NULL )n++; leaf(T->lchild); ·为遭历函数增加一个引用参数，用来传出指定二叉树的叶子 leaf(T->rchild): 结点数目。 ·引入全局的计数器，初始为0： ∥调用结束，即可由获得二叉树T的叶子结点数目 此处，遵历次序的选择对本算法没有太大影响。 需注意每次调用前须执行-0： 29/106 图 30/106 回
25/106 6.3 -遍历二叉树(4) 先序遍历 Status PreOrderTraverse( BiTree T, Status ( *Visit ) (ElemType e) ){ if ( T != NULL ){ if ( Visit(T->data) ) if ( PreOrderTraverse( T->lchild, Visit ) ) if ( PreOrderTraverse( T->rchild, Visit ) ) return OK; return ERROR; } else return OK; } 假设二叉树中结点数为n,高度为h, 则T(n,h)=O(n), S(n,h) = O(h) log2n + 1≤h ≤n 26/106 6.3 -基于先/中/后序遍历算法的应用 基于先/中/后序遍历的算法应用 基于先序遍历的二叉树(二叉链)的创建 统计二叉树中叶子结点的数目 释放二叉树的所有结点空间 删除并释放二叉树中以元素值为x的结点作为根的 各子树 求位于二叉树先序序列中第k个位置的结点的值 分析问题本身的特征，选择合适的遍历次序！ 应用递归编写算法，简洁！ 注意：递归结束条件，用递归调用的结果 27/106 例1 基于先序遍历的二叉树(二叉链)的创建 28/106 例1 基于先序遍历的二叉树(二叉链)的创建 Status CreateBiTree(BiTree &T) { //按先序次序输入二叉树中结点的值(一个字符) //空格字符表示空树,构造二叉链表表示的二叉树T scanf(&ch); if ( ch==' ') T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; } // CreateBiTree 29/106 例2 统计二叉树中叶子结点的数目(1) 【本例特征】 如何通过全局变量、变参、返回值三种渠道返回处理结果？ 【思路】 在遍历二叉树时，对一些特殊的结点(无左右孩子)进行计 数。可以将遍历算法的结点访问操作修改为对特殊结点的判定和 计数过程，需要注意的是计数器的处理方式。 可以有以下几种计数处理： ·用遍历函数的返回值传出求得的叶子结点的数目； ·为遍历函数增加一个引用参数，用来传出指定二叉树的叶子 结点数目。 ·引入全局的计数器，初始为0； 此处，遍历次序的选择对本算法没有太大影响。 30/106 例2 统计二叉树中叶子结点的数目(2) 【算法1 全局的计数器】 // n为叶子结点的计数器 int n=0; void leaf(BiTree T) { // 利用二叉树的先序遍历 if (T != NULL ){ // 访问结点->叶子的判定和计数 if( T->lchild==NULL && T->rchild==NULL ) n++; leaf(T->lchild); leaf(T->rchild); } }// 调用结束，即可由n获得二叉树T的叶子结点数目 需注意每次调用前须执行n=0;