中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）第6章树和二叉树.pdf_大学文库

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 图

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; 线索二叉树: 加上线索的二叉树线索化:对二叉树以某种次序遍历使其变为线索二叉树的过程

中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）第6章 树和二叉树

中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）第6章树和二叉树