数据结构 树和二叉树 第六章树和二叉树 主讲：张昱 重点：二叉树的性质、遍历；二叉树 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 , 有 ∈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,有∈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.1L, /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 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 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;
例2统计二叉树中叶子结点的数目(3) 例2统计二叉树中叶子结点的数目(4-1) 【算法2以函数返回值返回】 【算法3通过引用参数返回】 ∥函数值为T的叶子结点数 ∥引用参数和为T的叶子结点数，方法一 int leaf(BiTree T) void leaf(BiTree T.int &n) ∥利用二叉树的中序遗历，为局部变量 ∥利用二叉树的后序遭历 n■0； n=0; if(T:-NULL) if(T!-NULL) n=leaf(T->lchild)片 leaf (T->lchild,nl); ∥访问结点>叶子结点的判定和计数 leaf(T->rchild,n2): if (T->lchild-=-NULL &T->rchild--NULL )n++; ∥访问结点>叶子结点的判定和计数 n+=leaf(T->rchild); if (T->lchild=-NULL &T->rchild=-NULL )n++; n■n1+n2: return(n); 回 图 例2统计二叉树中叶子结点的数目(4-2) 【算法3通过引用参数返回】 ∥引用参数如等同于全局变量，方法二 为什么强调使用函数调用的结果？(1) ∥把T所指向的二叉树中的叶子结点数暴加到 ∥注意：在调用leaf(T,m)之前要先执行“n=0:” ·—算法/程序的健壮性！ void leaf(BiTree T,int &n) ,对于每算法/程序的任何输入，期望不异常终止 ,养成一种编程的习惯！ ∥利用二叉树的后序遮历 if(T!-NULL) ·例1 leaf (T->lchild,n); ,接口 leaf (T->rchild,n); ∥判断枝是否为空，返回TRUE/FALSE ∥访问结点>叶子结点的判定和计敷数 Status StackEmpty(Stack S); if T->lchild=-NULL &T->rchild=-NULL )n++; ∥出核（道通对战是否为空的判断） ∥若找为空，返回ERROR,否则返回OK Status Pop(Stack &S,ElemType &e); 3311Ue 图 34/106 为什么强调使用函数调用的结果？(2) 为什么强调使用函数调用的结果？(3) ,基于出栈的应用问题 ,基于出栈的应用问题 ∥方素1 Ⅱ方案2 if(StackEmpty(S)) if(Pop(S,e)==ERROR) 栈为空的一些处理 战为空的一些处理 else【 else{ Pop(S,e:I出楼出楼前楼一定非空 .已..发不为空，使用出找获得的元套 .e. 说明：此处直接使用Pop(S,e)的返回值，因为该 说明：此处不用Pop(S,e)的返回值，是因为它的 操作蕴福对栈为空的判断。在调用它后，其返回 返回值在该上下文下是唯一的，即永远为真 值有OK和ERROR两种可能！ 35/106 36/106 回
31/106 例2 统计二叉树中叶子结点的数目(3) 【算法2 以函数返回值返回】 // 函数值为T的叶子结点数 int leaf(BiTree T) { // 利用二叉树的中序遍历, n为局部变量 n = 0; if ( T != NULL ){ n = leaf ( T->lchild ); // 访问结点->叶子结点的判定和计数 if ( T->lchild==NULL && T->rchild==NULL )n++; n += leaf(T->rchild); } return (n); } 32/106 例2 统计二叉树中叶子结点的数目(4-1) 【算法3 通过引用参数返回】 // 引用参数n为T的叶子结点数，方法一 void leaf(BiTree T, int &n) { // 利用二叉树的后序遍历 n = 0; if ( T != NULL ){ leaf (T->lchild, n1); leaf (T->rchild, n2); // 访问结点->叶子结点的判定和计数 if ( T->lchild==NULL && T->rchild==NULL )n++; n = n1+n2; } } 33/106 例2 统计二叉树中叶子结点的数目(4-2) 【算法3 通过引用参数返回】 // 引用参数n等同于全局变量，方法二 // 把T所指向的二叉树中的叶子结点数累加到n // 注意：在调用leaf(T,n)之前要先执行“n＝0;” void leaf(BiTree T, int &n) { // 利用二叉树的后序遍历 if ( T != NULL ){ leaf (T->lchild, n); leaf (T->rchild, n); // 访问结点->叶子结点的判定和计数 if ( T->lchild==NULL && T->rchild==NULL )n++; } } 34/106 为什么强调使用函数调用的结果？(1) ——算法/程序的健壮性！ 对于每算法/程序的任何输入，期望不异常终止 养成一种编程的习惯！ 例1 接口 // 判断栈是否为空，返回TRUE/FALSE Status StackEmpty(Stack S); // 出栈（蕴涵对栈是否为空的判断） // 若栈为空，返回ERROR，否则返回OK Status Pop(Stack &S, ElemType &e); 35/106 为什么强调使用函数调用的结果？(2) 基于出栈的应用问题 // 方案1 if (StackEmpty(S) ) … //栈为空的一些处理 else { Pop(S, e); //出栈---出栈前栈一定非空 …e… } 说明：此处不用Pop(S, e)的返回值，是因为它的 返回值在该上下文下是唯一的，即永远为真 36/106 为什么强调使用函数调用的结果？(3) 基于出栈的应用问题 // 方案2 if ( Pop(S, e) ==ERROR) … //栈为空的一些处理 else { …e… //栈不为空，使用出栈获得的元素 } 说明：此处直接使用Pop(S, e)的返回值，因为该 操作蕴涵对栈为空的判断。在调用它后，其返回 值有OK和ERROR两种可能！
为什么强调使用函数调用的结果？(4) 为什么强调使用函数调用的结果？（⑤） ,例2 printf()的使用 。例3教材P131算法6.4 Status CreateBiTree(BiTree &T){ 。接口 int printf(const char *format [ if (I(T=(...)malloc(...))exit(OVERFLOW); ag®8nt].,,）: CreateBiTree(T->Ichild); CreateBiTree(T->rchild); Returns the number of characters printed,or a negative value if an error occurs. (from MSDN-Microsoft Developer Network) Why? ,遭常的使用 1)malloc失败，调用exit退出程序的执行 printf(“Helo,world!\n”y 2)返回只有一种值：0K→ Wy?一般的应用不关心输出的字符数 调用CreateBiTree时无须判断1 37106 回 38/106 图 例3释放二叉树的所有结点空间 例4副除并释放二叉树中以元素值为x的结点作为根的各子树(1) 【思略】 【本例特征】 ,二叉树为空时，不必释放： 若T不为空，则先释放其左右子树的所有结点的空间，再释放 如何选择二叉树的先序、中序、后序遗历来解决问题，它们 根结点的空间一后序。 对问题求解有何影申？ 若在释放子树的空间前，先释放根结点的空间，则需要将子 【思路】 树的根结点的指针暂存到其他变量：否则，无法找到子树。 整个过程分为两个方面： 【算法门 ·请历中查找元素值为x的结点 void deleteBiTree(BiTree&T){∥此处T应为引用参数 ·查到该结点时，调用例3的算法释放子树空间。 if(T!-NULL) deleteBiTree(T->lchild ) 需要考忠的问愿是： deleteBiTree(T->rchild ) ·如何将全部的结点找到并释放？ ∥访问结点>释放结点的空间 ·外层查找采用的墙历次序对本算法有何影响？ free(T); T■NULL 从以下3个算法中可以看出，利用先序遭历是最合适的：中序和 后序，存在一定的多余操作。 图 40/106 回 例4删除并释放二叉树中以元素值为x的结点作为根的各子树(2) 例4删除并释放二叉树中以元素值为x的结点作为根的各子树(3) 【算法1】 【算法2】 void deleteXTree(BiTree &T,ElemType x) void deleteXTree(BiTree &T,ElemType x) ∥基于先序的查找 ∥基于中序的查找 if(T!-NULL) if (T!-NULL) ∥访问结点>判断是否为指定结点>释放树空间 ∥若T->data■x,则此步骤多余 if(T->data=■x）deleteBiTree(T)i deleteXTree(T->lchild,x): else ∥访问结点>判断是否为指定结点>释放树空间 ∥此处else不能省略 if (T->data=-x) deleteXTree(T->child,x); deleteBiTree(T); deleteXTree(T->rchild,x); else deleteXTree(T->rchild,x); 图 图
37/106 为什么强调使用函数调用的结果？(4) 例2 printf( )的使用 接口 int printf( const char *format [, argument]... ); Returns the number of characters printed, or a negative value if an error occurs. (from MSDN—Microsoft Developer Network) 通常的使用 printf(“Hello, world!\n”) Why? 一般的应用不关心输出的字符数 38/106 为什么强调使用函数调用的结果？(5) 例3 教材P131 算法6.4 Status CreateBiTree(BiTree &T){ … if ( !(T=(…)malloc(…) ) ) exit(OVERFLOW); CreateBiTree(T->lchild); CreateBiTree(T->rchild); … } Why? 1) malloc失败，调用exit退出程序的执行 2) 返回只有一种值：OK Æ 调用CreateBiTree时无须判断！ 39/106 【思路】 ·二叉树为空时，不必释放； ·若T不为空，则先释放其左右子树的所有结点的空间，再释放 根结点的空间——后序。 若在释放子树的空间前，先释放根结点的空间，则需要将子 树的根结点的指针暂存到其他变量；否则，无法找到子树。 【算法】 void deleteBiTree(BiTree &T){ // 此处T应为引用参数 if ( T != NULL ){ deleteBiTree(T->lchild ); deleteBiTree(T->rchild ); // 访问结点->释放结点的空间 free(T); T = NULL; } } 例3 释放二叉树的所有结点空间 40/106 例4 删除并释放二叉树中以元素值为x的结点作为根的各子树 (1) 【本例特征】 如何选择二叉树的先序、中序、后序遍历来解决问题，它们 对问题求解有何影响？ 【思路】 整个过程分为两个方面： ·遍历中查找元素值为x的结点 ·查到该结点时，调用例3的算法释放子树空间。 需要考虑的问题是： ·如何将全部的结点找到并释放？ ·外层查找采用的遍历次序对本算法有何影响？ 从以下3个算法中可以看出，利用先序遍历是最合适的；中序和 后序，存在一定的多余操作。 41/106 【算法1】 void deleteXTree(BiTree &T, ElemType x) { // 基于先序的查找 if ( T != NULL ){ // 访问结点->判断是否为指定结点->释放树空间 if ( T->data== x ) deleteBiTree(T); else{ // 此处else不能省略 deleteXTree(T->lchild, x); deleteXTree(T->rchild, x); } } } 例4 删除并释放二叉树中以元素值为x的结点作为根的各子树 (2) 42/106 【算法2】 void deleteXTree(BiTree &T, ElemType x) { // 基于中序的查找 if ( T != NULL ){ // 若T->data== x，则此步骤多余 deleteXTree(T->lchild, x); // 访问结点->判断是否为指定结点->释放树空间 if ( T->data== x) deleteBiTree(T); else deleteXTree(T->rchild, x); } } 例4 删除并释放二叉树中以元素值为x的结点作为根的各子树 (3)
例4刷除并释放二叉树中以元素值为x的结点作为根的各子树(4) 例5求位于二叉树先序序列中第k个位置的结点的值(1) 【算法3】 【本例特征】 void deleteXTree(BiTree &T,ElemType x) 如何处理多个返回结果？ 【思路】 待查结点的存在性： ∥基于后序的查找 当二叉树为空河，或者k非法时，待查结点不存在 if (T!-NULL) 函数应返回特查结点是否存在的状态指示：TRUE或FALSE ∥若T->data■x,则此步骤多余 当待查找的结点存在时，需进一步返回该结点的值 deleteXTree(T->lchild,x); ∥若T->data■x,则此步骤多余 问题1：该算法需要返回多个值，如何处理？ 答：一种做法是用返回值返回存在性，用变参返回值。 deleteXTree(T->rchild,x); ∥访问结点>判断是否为指定结点>释放树空间 问题2：该算法可以基于二叉树的先序遍历的递归算法来构 if (T->data-x)deleteBiTree(T); 造，如向知道当前访问的结点是先序序列中的第几个结点？ 答：引入计数器，对于该计数器可以采用全局变量来存储， 也可以通过变参来处理。 44/106 图 例5求位于二叉树先序序列中第k个位量的结点的值(2) 【算法】 Status PreorderKnode(BiTree T,int k,ElemType &e.int &count){ ∥输入：T为二叉链表示的二叉树，k为特查找的结点在先序序列中的位序 ∥输出：TRUE,特查找的结点存在：FALSE:特查找的结点不存在 6.3-先序遍历的非递归算法(1) 一当特查点存在时， 该储点的值通过带回 中间变生：0二记录当前己经访间过的结点个最 ·思路 if(T==NULL)return FALSE: 假设：T指向要造历的二叉树的根，若T!=NULL count++; ∥访间结点→对已访问的结点进行计戴 对于非道归算法，引入找棋拟递白工作找初始找为空。 i道(count-=k){ )判断该地点是否是待查找的德点 问题：如何用提来保存信息，使得在先序墙历过左子树 e=T>data: 后，能利用找顶信息获取T的右子树的根指针？ return TRUE; ∥查到，则设置e,并返回TRUE 方法1：访间T->data后，将T入提，德历左子树：地历先 】else if(count> return FALSE:∥计数悬count已经超出k当kchild.k,e,count)=FALSE∥在左子树中查找 方法2：访问T->data后，将T->rchild.入機，遍历左子 return P rderKnode(T->rchild,.k,coumt;)∥在右子满中查找 树，海历亮左子树返回时，棱顶元素应为T->rchild,出 return TRUE; 找，墙历以该指针指向的结点为根的子芳。 45/106 图 46/106 图 6.3-先序遍历的非递归算法(2) 6.3-先序遍历的非递归算法(3) ·算法1 ·算法2 oid-PreOrder(BiTreeT,gas(气Vist)包em发c》 (+仆基于方法二，流程图如右，当型造环 O InitStack(S) InitStack⑤： whuile TI-NULL StackEmptv(S)H wlile TI=NULLStackEmpty(S) 置拔8为空 while (T=NULL 置枝3为空 te(T-NU山j sT->d城a) Visit(T->data) 丁为空 T-T-uld. Push(S.T-relild):. T为空， T-T-lchild; 扶空 IN. 访问根结点 金StackEnpty(s) 栈S空 防问根结点， Pop(S.T. i(StackEmpty(S) T-T-Xchald Pop(S T T=T->reldd Push(S.T->rchik T=T-lchilde Pop(S,TX Pop(ST, T-T->rchild 47/106 48/106
43/106 【算法3】 void deleteXTree(BiTree &T, ElemType x) { // 基于后序的查找 if ( T != NULL ){ // 若T->data== x，则此步骤多余 deleteXTree(T->lchild, x); // 若T->data== x，则此步骤多余 deleteXTree(T->rchild, x); // 访问结点->判断是否为指定结点->释放树空间 if ( T->data == x ) deleteBiTree(T); } } 例4 删除并释放二叉树中以元素值为x的结点作为根的各子树 (4) 44/106 【本例特征】 如何处理多个返回结果？ 【思路】 ·待查结点的存在性： 当二叉树为空树，或者k非法时，待查结点不存在 Î 函数应返回待查结点是否存在的状态指示：TRUE或FALSE ·当待查找的结点存在时，需进一步返回该结点的值 问题1：该算法需要返回多个值，如何处理？ 答：一种做法是用返回值返回存在性，用变参返回值。 问题2：该算法可以基于二叉树的先序遍历的递归算法来构 造，如何知道当前访问的结点是先序序列中的第几个结点？ 答：引入计数器，对于该计数器可以采用全局变量来存储， 也可以通过变参来处理。 例5 求位于二叉树先序序列中第k个位置的结点的值 (1) 45/106 【算法】 Status PreorderKnode(BiTree T, int k, ElemType &e, int &count){ // 输入：T为二叉链表示的二叉树，k为待查找的结点在先序序列中的位序 // 输出：TRUE：待查找的结点存在；FALSE：待查找的结点不存在 // e—当待查结点存在时，该结点的值通过e带回 // 中间变量：count—记录当前已经访问过的结点个数 if ( T==NULL) return FALSE; count++; // 访问结点Æ对已访问的结点进行计数 if (count==k ){ // Æ判断该结点是否是待查找的结点 e = T->data; return TRUE; // 查到，则设置e，并返回TRUE }else if (count > k) return FALSE; // 计数器count已经超出k(当klchild, k, e, count)==FALSE) // 在左子树中查找 return PreorderKnode(T->rchild, k, e, count); // 在右子树中查找 return TRUE; } } 例5 求位于二叉树先序序列中第k个位置的结点的值 (2) 46/106 6.3 –先序遍历的非递归算法(1) 思路 假设：T指向要遍历的二叉树的根，若T != NULL 对于非递归算法，引入栈模拟递归工作栈，初始栈为空。 问题：如何用栈来保存信息，使得在先序遍历过左子树 后，能利用栈顶信息获取T的右子树的根指针？ 方法1：访问T->data后，将T入栈，遍历左子树；遍历完 左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右 子树。 方法2：访问T->data后，将T->rchild入栈，遍历左子 树；遍历完左子树返回时，栈顶元素应为T->rchild，出 栈，遍历以该指针指向的结点为根的子树。 47/106 6.3 –先序遍历的非递归算法(2) 算法1 48/106 6.3 –先序遍历的非递归算法(3) 算法2
6.3-中序遍历的非递归算法 6.3-后序遍历的非递归算法(1) ·思路 ·思略 。T是指向要速历的二叉树 。T指向要遍历的二叉树的根，后序造历要求在墙历光左 的根。中序速历要求在塘 历完在子后，访问液， 黄核5为空 右于树后，再访问根。高要判断根结点的左右子树是否 均历过： 再速历右子树。 ,可采用标记法，结点入栈时，配一个标喜ag一同入找 。问题：如何用枝来保存信 T为空 (0:惠历左子树前的现场保护，1：遍历右子树前的现 使得在中序德历过左 IN. 扬保护)。 子树后，能 利用顶信惠 Push(S.T) 。首先将T和t妇g(为0)入机，遗历左子树：返回后，修放 获取T指针 IN. ,方法：先将T入棱，藏历 -T-Xchil 找顶tag为1，速历右子树：量后访问根结点。 子满： 历完 子树 typedef struct T=T->rchld Bitre 出找，访问T->data,再 中序薄历T的右子树 49106 s0/106 图 6.3-后序遍历的非递归算法(2) 6.3-层次遍历算法及其应用 ,层次遍历算法及其应用 置栈5为空 ,二叉树的层次清历算法 ·先访问的结点，其孩子结点必然也先访问 T为空 队列 机5空 Push(S.T.O).. ,基于层次遍历算法的应用 T=T->lchild ·判断一棵二叉榭是否为完全二叉抛 技顶标记为1 。找出距粉定结点最近或最远的叶子子孙 栈记置1 Pop( .T.tag) ,找出指定层中含有的叶子/度为2/度为1的结点 T=T->rchald. 访问T->data. 51/106 固 52/106 图 例6二叉树的层次遍历(1) 例6二叉树的层次遍历(2) 【思略 ”从队列中取已被访问的、但其左右孩子尚未访问的结点指针 先访问的结点，其孩子储点必然也先访问。引入队列存储已被访月的 ∥访问其孩子 但其左右孩子尚未访问的结赢的指针。若使用链队列，其元素可定义为： while(QueueEmpty(O){W队不为空.则尚有来访问其孩子的结点 typedef struet QNodef ∥DeQueue()为出队函戴，它将原队头元素作为返回值蓝回 Bitree data: ∥指向二叉树结点的指针 struct QNode *next: ”时狗法我群0 if p->lchild !NULL){ }QNode,*QueuePtr: if (!Visit(p->lchild>data )return ERROR; 【算法】 EnQueue(Q,p->lchild片 StatusLevelTraverse(BiTree T,Status (*Visit)(ElemType e)) ∥访句右孩子 Ⅱ初始化队列，队列的元豪为二叉树的结点指针 if(p->rchild !NULL ) if (!Visit(p->rehild->data )return ERROR; if(T!=NULL) EnQueue(Q,p->rehild ) Ⅲ访问根 if (!Visit(T->data))return ERROR; ∥EnQueue()为入队函兼，T为特入队的元素 return OK; EnQueue(Q.T): 图 图
49/106 6.3 –中序遍历的非递归算法 思路 T是指向要遍历的二叉树 的根，中序遍历要求在遍 历完左子树后，访问根， 再遍历右子树。 问题：如何用栈来保存信 息，使得在中序遍历过左 子树后，能利用栈顶信息 获取T指针？ 方法：先将T入栈，遍历 左子树；遍历完左子树返 回时，栈顶元素应为T， 出栈，访问T->data，再 中序遍历T的右子树。 50/106 6.3 –后序遍历的非递归算法(1) 思路 T指向要遍历的二叉树的根，后序遍历要求在遍历完左 右子树后，再访问根。需要判断根结点的左右子树是否 均遍历过。 可采用标记法，结点入栈时，配一个标志tag一同入栈 (0：遍历左子树前的现场保护，1：遍历右子树前的现 场保护)。 首先将T和tag(为0)入栈，遍历左子树；返回后，修改 栈顶tag为1，遍历右子树；最后访问根结点。 typedef struct stackElement{ Bitreedata; char tag; }stackElemType; 51/106 6.3 –后序遍历的非递归算法(2) 52/106 6.3 –层次遍历算法及其应用 层次遍历算法及其应用 二叉树的层次遍历算法 先访问的结点，其孩子结点必然也先访问 ——队列 基于层次遍历算法的应用 判断一棵二叉树是否为完全二叉树 找出距指定结点最近或最远的叶子子孙 找出指定层中含有的叶子/度为2/度为1的结点 53/106 【思路】 先访问的结点，其孩子结点必然也先访问。引入队列存储已被访问的、 但其左右孩子尚未访问的结点的指针。若使用链队列，其元素可定义为： typedef struct QNode{ Bitree data; // 指向二叉树结点的指针 struct QNode *next; } QNode, *QueuePtr; 【算法】 StatusLevelTraverse (BiTree T, Status ( *Visit ) (ElemType e) ) { // 初始化队列，队列的元素为二叉树的结点指针 InitQueue(Q); if ( T != NULL ){ // 访问根 if ( !Visit( T->data ) ) return ERROR; // EnQueue( )为入队函数，T为待入队的元素 EnQueue(Q, T); 例6 二叉树的层次遍历(1) 54/106 // 从队列中取已被访问的、但其左右孩子尚未访问的结点指针 // 访问其孩子 while( !QueueEmpty(Q) ){ // 队不为空,则尚有未访问其孩子的结点 // DeQueue( )为出队函数，它将原队头元素作为返回值返回 p = DeQueue (Q); // 访问左孩子 if ( p->lchild != NULL ) { if ( !Visit( p->lchild ->data )) return ERROR; EnQueue(Q, p->lchild ); } // 访问右孩子 if( p->rchild != NULL ) { if ( !Visit( p->rchild ->data )) return ERROR; EnQueue(Q, p->rchild ); } } } return OK; } 例6 二叉树的层次遍历(2)
例7判断一棵二叉树是否为完全二叉树(1) 例7判断一棵二叉树是否为完全二叉树(2) 【思略】 whe(:Que▣eEmp的Q){∥队不为空，则尚有来访问其孩于的的点 p-DeOueue(O): 由光全二叉树的定义，对全二叉树按层次速历应浦足： bFlag --FALSE) 1)若某结点没有左孩子则它一定无右孩子； “前驱结点峡左改子，则若该岫点有改子，则此树率亮全二又树 2)若某结点缺孩子，则其后鳗无孩子， if p->lchild:-NULL p>rchild!-NULL)return FALSE: 利用层次遍历，需要附加一个标志量bFe反映是否已扫描过的结点均有 lelse if p->lchild--NULL) 左右毯子，在事一文通到孩子的结点时，可将为FS正，此时存在 :第一次通到结点缺左孩子 以下两种情况： bFlag -FALSE; 若它滴足1)，需要缝峡扫描后壁结点，以判断是否满足2)， Ⅱ若有右孩子，不调足1)，则排亮全二又树 若不满足1)，则说明不是光全二叉树， if p->rchild !-NULL return FALSE; 【算法】 lelse if p->lchild !NULL) 业若有左娄子，刚入队 BOOL: EnQueue(Q,p>lchild片 #define FALSE 0 一次省左子，峡右孩于 BOOL JudgeCBT(BiTree T) bFlag FALSE: else EnQueue(Q,p>rchild): InitQueue (Q): bFlag=TRUE; if (T!=NULL) EnQueue(Q,T): return TRUE:∥T为空，也是先全二叉树 55/1Ue 回 图 6.3-层次遍历算法及其应用 6.3-二叉树的创建方法 ,灵活运用：问题的延伸与解决 ·二叉树（链式存储）的创建方法 ·找出距结点x量近的叶子子孙 输入序列与二叉树的映射关系： ,求距结点x最近的叶子子孙到x的距高 如何获得距离信息？ ,完全二叉树的顺序映射 。方法1：扩晨队列元素的类型，增加距高城 通过补皮站点，将一般的二叉树转变成完全二叉 。方法2：交普使用两个队列，以获得结点的层次 树，再对域完全二叉树的结点按自上而下、自左 ,方法3：在每一层末尾增加一个虚结点， 至右进行精入， 统计距结点x最近的叶子子孙的数目 ,二叉树的先序请历 。输出距结点x最近的所有叶子子孙 通过补虚结点，使二叉树中各实际站点均具有左 ,输出距结点x最近的叶子子孙到x的略径 右孩子，再对该二又树状先序遍历进行输入， 。出队时不则除元素，元素类型中增加结点的双亲在队 ,二叉树的两种遭历序列：先序+中序，后序+中序 列中的位置1 58/106 图 6.3线索二叉树 6.3-线索二叉树类型定义 。线索二叉树 -二叉树的结构扩展 。候案链表：包含战家的链表 ·二又树的遗历：非线性结构的线性化 /Link==0:指t,Thread==l:城常 typedef enum Link,Thread)PointerTag 。问题：在二叉树的能式存储中，如何快速找到某站点 typedef struct BiThrNode( 在某一序列（先序/后序/中序）中的直接前驱本直接后 ElemType data; 婊？ /川左右孩子湘针转家 ·为每一结点增加fwd和bkwd指针域 struct BiThrNode *Ichild,*rchild; —降低存储密度 /川左右标速 PointerTag Itag,rtag; ,利用二叉链中的空链域(n个结点有+1个空链域) >BiThrNode,*BiThrTree; 标识链城的含义：葉子？线素（指向结底前驱和 ,能案二叉树：加上线球的二叉树 后继的指针)？ 。线康化：对二叉树以某种次序速历使其变为线寒二叉树的过程. 59/106 图 60/106 图
55/106 【思路】 由完全二叉树的定义，对完全二叉树按层次遍历应满足： 1）若某结点没有左孩子，则它一定无右孩子； 2）若某结点缺孩子，则其后继必无孩子。 利用层次遍历，需要附加一个标志量bFlag反映是否已扫描过的结点均有 左右孩子。在第一次遇到缺孩子的结点时，可将bFlag置为FALSE；此时存在 以下两种情况： ·若它满足1），需要继续扫描后继结点，以判断是否满足2）； ·若不满足1），则说明不是完全二叉树。 【算法】 typedef char BOOL; #define TRUE 1 #define FALSE 0 BOOL JudgeCBT(BiTree T) { InitQueue (Q); bFlag = TRUE; if ( T != NULL ){ EnQueue(Q, T); 例7 判断一棵二叉树是否为完全二叉树(1) 56/106 while ( !QueueEmpty(Q) ){ // 队不为空，则尚有未访问其孩子的结点 p = DeQueue(Q); if ( bFlag == FALSE ) { // 前驱结点缺左孩子，则若该结点有孩子，则此树非完全二叉树 if ( p->lchild!=NULL || p->rchild!=NULL ) return FALSE; }else if ( p->lchild == NULL ) { // 第一次遇到结点缺左孩子 bFlag = FALSE; // 若有右孩子，不满足1），则非完全二叉树 if ( p->rchild != NULL ) return FALSE; }else if ( p->lchild != NULL ) { // 若有左孩子，则入队 EnQueue(Q, p->lchild ); if ( p->rchild == NULL ) // 第一次遇到结点有左孩子，缺右孩子 bFlag = FALSE; else EnQueue(Q, p->rchild ); } } } return TRUE; // T为空，也是完全二叉树 } 例7 判断一棵二叉树是否为完全二叉树(2) 57/106 6.3 –层次遍历算法及其应用 灵活运用:问题的延伸与解决 找出距结点 x 最近的叶子子孙 求距结点 x 最近的叶子子孙到 x 的距离 如何获得距离信息? 方法1:扩展队列元素的类型,增加距离域 方法2:交替使用两个队列,以获得结点的层次 方法3:在每一层末尾增加一个虚结点,… 统计距结点 x 最近的叶子子孙的数目 输出距结点 x 最近的所有叶子子孙 输出距结点 x 最近的叶子子孙到 x 的路径 出队时不删除元素,元素类型中增加结点的双亲在队 列中的位置域 58/106 6.3 –二叉树的创建方法 二叉树(链式存储)的创建方法 输入序列与二叉树的映射关系： 完全二叉树的顺序映射 通过补虚结点，将一般的二叉树转变成完全二叉 树，再对该完全二叉树的结点按自上而下、自左 至右进行输入。 二叉树的先序遍历 通过补虚结点，使二叉树中各实际结点均具有左 右孩子，再对该二叉树按先序遍历进行输入。 二叉树的两种遍历序列：先序+中序，后序+中序 59/106 6.3 –线索二叉树 线索二叉树——二叉树的结构扩展 二叉树的遍历：非线性结构的线性化 问题：在二叉树的链式存储中，如何快速找到某结点 在某一序列(先序/后序/中序)中的直接前驱和直接后 继？ 为每一结点增加fwd和bkwd指针域 ——降低存储密度 利用二叉链中的空链域(n个结点有n+1个空链域) ——标识链域的含义: 孩子？线索(指向结点前驱和 后继的指针)？ 60/106 6.3 –线索二叉树类型定义 线索链表: 包含线索的链表 // Link== 0 :指针,Thread==1: 线索 typedef enum { Link, Thread} PointerTag; typedef struct BiThrNode{ ElemType data; // 左右孩子指针/线索 struct BiThrNode *lchild, *rchild; // 左右标志 PointerTag ltag, rtag; }BiThrNode, *BiThrTree; 线索二叉树: 加上线索的二叉树 线索化:对二叉树以某种次序遍历使其变为线索二叉树的过程
