数据结构——树和二叉树 1/96

重点：二叉树的性质、遍历；二叉树与森林(树)的相互转换 难点：树和二叉树应用的算法设计 第六章 树和二叉树 重点：二叉树的性质、遍历；二叉树与森林(树)的相互转换 难点：树和二叉树应用的算法设计 2/96

第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 6.5 树与等价问题 6.7 回溯法与树的遍历 6.8 树的计数 3/96

6.1 树的定义和基本术语 树的定义(递归定义) 树是n(n≥0)个结点的有限集。若 n = 0，称为空树。 若 n > 0，则 有且仅有一个特定的称为根的结点； 当n > 1时，除根以外的其他结点划分为m(m>0) 个互不相交的有限集T1, T2,… Tm，其中每一个集合本身又是一棵树，并且称为根的子树。 A B C D E F G H I J K L A 4/96

(A(B(E, F(K,L)), C(G), D(H, I, J))) 6.1 树的定义-其他表示 树的其他表示 嵌套集合、广义表表示、凹入表示 A***************** B**************** E*************** F*************** K************** L************** C**************** G*************** D**************** H*************** I*************** J*************** G C A B D H I J E K F L (A(B(E, F(K,L)), C(G), D(H, I, J))) 5/96

6.1 树的定义-基本术语 基本术语 第1层 A B C D E F G H I J K L 第2层 高度为4 第3层 第4层 孩子 双亲 兄弟 祖先 子孙 堂兄弟 结点 结点的度 结点的层次 终端结点(叶子) 非终端结点(分支结点) 内部结点 树的度 树的深度/高度 有序树 无序树 森林 6/96

7/96

8/96

9/96

10/96

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()) 11/96

6.2 二叉树 二叉树的定义(递归定义) 特点：每个结点至多只有两棵子树，子树有左右之分 二叉树 vs 度不大于2的有序树 ADT BinaryTree 二叉树 有序树 12/96

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 13/96

6.2 二叉树-性质(2) 满二叉树：一棵深度为k且有2k –1个结点的二叉树 完全二叉树：对于深度为k的完全二叉树，则 1) 前k-1层为满二叉树； 2) 第k层结点依次占据最左边的位置； 3) 一个结点有右孩子，则它必有左孩子； 4) 度为1的结点个数为0或1 5) 叶子结点只可能在层次最大的两层上出现； 6) 对任一结点，若其右分支下的子孙的最大层次为l, 则其左分支下的子孙的最大层次必为l或l+1。 14/96

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以及完全二叉树的特征) 15/96

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叉树，结果会如何？ 16/96

6.2 二叉树-顺序存储结构(1) 二叉树的顺序存储结构 类型定义 typedef ElemType SqBiTree[MAX_TREE_SIZE]; //0号单元存储根结点 1) 依据性质5，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素； ——结点在存储区中的相对位置反映它们逻辑上的关系 2) 仅适用于完全二叉树 一般二叉树的顺序存储方法 通过补虚结点，将一般的二叉树变成完全二叉树 空间开销大！ 17/96

6.2 二叉树-顺序存储结构(2) 1 1 2 3 4 5 0 0 0 0 6 7 2 3 5 4 6 7 空间利用率问题： 在最坏情况下，一个深度为k且只有k个结点的单支树(树中不存在度为2的结点)，则需要长度为2k-1的一维数组。 18/96

6.2 二叉树-链式存储结构 二叉树的链式存储结构 引入辅助空间表示结点之间的关系：双亲-孩子 二叉链表(左、右孩子链域) 三叉链表(双亲及左、右孩子链域) 二叉链的类型定义(动态链表) typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 }BiTNode, *BiTree; 若有n个结点，则共有2n个链域；其中n-1不为空，指向孩子；另外n+1个为空链域 19/96

6.3 遍历二叉树和线索二叉树 遍历二叉树 基于先/中/后序遍历算法的应用 为什么强调使用函数调用的结果 层次遍历算法及其应用 二叉树的创建方法 线索二叉树 先/中/后序遍历的非递归算法 20/96

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 21/96

6.3 -遍历二叉树(2) 先/中/后序遍历的区别 如右图，三者经过的搜索路线是相同的；只是访问结点的时机不同。每一结点在整个搜索路线中会经过3次： 第一次进入到该结点 此时访问该结点，称为先序遍历 由左子树回溯到该结点 此时访问该结点，称为中序遍历 由右子树回溯到该结点 此时访问该结点，称为后序遍历 22/96

6.3 -遍历二叉树(3) 遍历算法的递归实现 二叉树的递归定义性质，决定了它的很多算法都可用递归实现，遍历算法就是其中之一。 对于二叉树的遍历，可以不去具体考虑各子问题(左子树、根、右子树)的遍历结果是什么，而去考虑如何由各子问题的求解结果构成原问题(二叉树)的遍历结果——递归规律的确定。必须注意的是，当二叉树小到一定程度，即空树时，应直接给出解答——递归结束条件及处理。 23/96

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; 24/96

6.3 -基于先/中/后序遍历算法的应用 基于先/中/后序遍历的算法应用 基于先序遍历的二叉树(二叉链)的创建 统计二叉树中叶子结点的数目 释放二叉树的所有结点空间 删除并释放二叉树中以元素值为x的结点作为根的各子树 求位于二叉树先序序列中第k个位置的结点的值 分析问题本身的特征，选择合适的遍历次序！ 应用递归编写算法，简洁！ 注意：递归结束条件，用递归调用的结果 25/96

例1 基于先序遍历的二叉树(二叉链)的创建 26/96

例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 27/96

例2 统计二叉树中叶子结点的数目(1) 【本例特征】 如何通过全局变量、变参、返回值三种渠道返回处理结果？ 【思路】 在遍历二叉树时，对一些特殊的结点(无左右孩子)进行计数。可以将遍历算法的结点访问操作修改为对特殊结点的判定和计数过程，需要注意的是计数器的处理方式。 可以有以下几种计数处理： ·用遍历函数的返回值传出求得的叶子结点的数目； ·为遍历函数增加一个引用参数，用来传出指定二叉树的叶子结点数目。 ·引入全局的计数器，初始为0； 此处，遍历次序的选择对本算法没有太大影响。 28/96

例2 统计二叉树中叶子结点的数目(2) 【算法1 全局的计数器】 // n为叶子结点的计数器 int n=0; 【算法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; 29/96

例2 统计二叉树中叶子结点的数目(3) 【算法2 以函数返回值返回】 // 函数值为T的叶子结点数 int leaf(BiTree T) { 【算法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); 30/96

例2 统计二叉树中叶子结点的数目(4) 【算法3 通过引用参数返回】 // 引用参数n为T的叶子结点数 【算法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; } 31/96

例3 释放二叉树的所有结点空间 【思路】 ·二叉树为空时，不必释放； ·若T不为空，则先释放其左右子树的所有结点的空间，再释放根结点的空间——后序。 若在释放子树的空间前，先释放根结点的空间，则需要将子树的根结点的指针暂存到其他变量；否则，无法找到子树。 【算法】 void deleteBiTree(BiTree &T){ // 此处T应为引用参数 if ( T != NULL ){ deleteBiTree(T->lchild ); deleteBiTree(T->rchild ); // 访问结点->释放结点的空间 free(T); T = NULL; } 32/96

例4 删除并释放二叉树中以元素值为x的结点作为根的各子树 (1) 【本例特征】 如何选择二叉树的先序、中序、后序遍历来解决问题，它们对问题求解有何影响？ 【思路】 整个过程分为两个方面： ·遍历中查找元素值为x的结点 ·查到该结点时，调用例3的算法释放子树空间。 需要考虑的问题是： ·如何将全部的结点找到并释放？ ·外层查找采用的遍历次序对本算法有何影响？ 从以下3个算法中可以看出，利用先序遍历是最合适的；中序和后序，存在一定的多余操作。 33/96

例4 删除并释放二叉树中以元素值为x的结点作为根的各子树 (2) 【算法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); } 34/96

例4 删除并释放二叉树中以元素值为x的结点作为根的各子树 (3) 【算法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); } 35/96

例4 删除并释放二叉树中以元素值为x的结点作为根的各子树 (4) 【算法3】 void deleteXTree(BiTree &T, ElemType x) { // 基于后序的查找 if ( T != NULL ){ // 若T->data== x，则此步骤多余 deleteXTree(T->lchild, x); deleteXTree(T->rchild, x); // 访问结点->判断是否为指定结点->释放树空间 if ( T->data == x ) deleteBiTree(T); } 36/96

例5 求位于二叉树先序序列中第k个位置的结点的值 (1) 【本例特征】 如何处理多个返回结果？ 【思路】 ·待查结点的存在性： 当二叉树为空树，或者k非法时，待查结点不存在  函数应返回待查结点是否存在的状态指示：TRUE或FALSE ·当待查找的结点存在时，需进一步返回该结点的值 问题1：该算法需要返回多个值，如何处理？ 答：一种做法是用返回值返回存在性，用变参返回值。 问题2：该算法可以基于二叉树的先序遍历的递归算法来构造，如何知道当前访问的结点是先序序列中的第几个结点？ 答：引入计数器，对于该计数器可以采用全局变量来存储，也可以通过变参来处理。 37/96

例5 求位于二叉树先序序列中第k个位置的结点的值 (2) 【算法】 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(当k<0时)，则直接返回FALSE else { if (PreorderKnode(T->lchild, k, e, count)==FALSE) // 在左子树中查找 return PreorderKnode(T->rchild, k, e, count); // 在右子树中查找 return TRUE; } 38/96

6.3 –层次遍历算法及其应用 层次遍历算法及其应用 二叉树的层次遍历算法 先访问的结点，其孩子结点必然也先访问 ——队列 基于层次遍历算法的应用 判断一棵二叉树是否为完全二叉树 找出距指定结点最近或最远的叶子子孙 找出指定层中含有的叶子/度为2/度为1的结点 39/96

例6 二叉树的层次遍历(1) 【思路】 先访问的结点，其孩子结点必然也先访问。引入队列存储已被访问的、但其左右孩子尚未访问的结点的指针。若使用链队列，其元素可定义为： typedef struct QNode{ Bitree data; // 指向二叉树结点的指针 struct QNode *next; } QNode, *QueuePtr; 【算法】 Status LevelTraverse (BiTree T, Status ( *Visit ) (ElemType e) ) { // 初始化队列，队列的元素为二叉树的结点指针 InitQueue(Q); if ( T != NULL ){ // 访问根 if ( !Visit( T->data ) ) return ERROR; // EnQueue( )为入队函数，T为待入队的元素 EnQueue(Q, T); 40/96

例6 二叉树的层次遍历(2) // 从队列中取已被访问的、但其左右孩子尚未访问的结点指针 // 访问其孩子 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; 41/96

例7 判断一棵二叉树是否为完全二叉树(1) if ( T != NULL ){ EnQueue(Q, T); 【思路】 由完全二叉树的定义，对完全二叉树按层次遍历应满足： 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); 42/96

例7 判断一棵二叉树是否为完全二叉树(2) return TRUE; // T为空，也是完全二叉树 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 ) // 第一次遇到结点有左孩子，缺右孩子 else EnQueue(Q, p->rchild ); } return TRUE; // T为空，也是完全二叉树 43/96

6.3 –二叉树的创建方法 二叉树(链式存储)的创建方法 输入序列与二叉树的映射关系： 完全二叉树的顺序映射 通过补虚结点，将一般的二叉树转变成完全二叉树，再对该完全二叉树的结点按自上而下、自左至右进行输入。 二叉树的先序遍历 通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍历进行输入。 二叉树的两种遍历序列：先序+中序，后序+中序 44/96

6.3 –线索二叉树 线索二叉树——二叉树的结构扩展 二叉树的遍历：非线性结构的线性化 问题：在二叉树的链式存储中，如何快速找到某结点在某一序列(先序/后序/中序)中的直接前驱和直接后继？ 为每一结点增加fwd和bkwd指针域 ——降低存储密度 利用二叉链中的空链域(n个结点有n+1个空链域) ——标识链域的含义(孩子？线索？) 45/96

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; 46/96

6.3 –中序线索二叉树(1) 中序线索二叉树——结构对称 在中序线索二叉树上找结点的(直接)后继/前驱？ 第一个结点：最左下的结点； 最后一个结点：最右下的结点 某结点的后继： a) 若该结点有右孩子，其后继 为其右子树中最左下的结点； b) 若该结点无右孩子，其后继 由rchild指向。 其后继为满足以下条件的最小子 树的根r：该结点为r的左子树中 最右下的结点。 1 2 3 4 5 6 7 47/96

6.3 –中序线索二叉树(2) 在中序线索二叉树上遍历 在二叉树的线索链表上添加一个头结点，令其lchild域指向二叉树的根—Link，rchild域指向中序遍历时访问的最后一个结点—Thread；中序序列中的第一个结点的lchild域和最后一个结点的rchild域均指向头结点。 算法见教材 二叉树的中序线索化 二叉树中序遍历算法的应用 算法见教材 thrt 0 1 1 0 1 0 0 2 0 1 3 1 1 4 1 0 5 1 1 6 1 1 7 1 48/96

6.3 –中序线索二叉树(3) 49/96

6.3 –中序线索二叉树(4) 50/96

6.3 –后序线索二叉树 vs 先序线索二叉树(1) 后序线索二叉树 与 先序线索二叉树 互为对称 1 2 3 5 4 6 1 2 3 5 后序线索二叉树 第一个结点：未必是树中最左下的结点，但一定是叶结点； 最后一个结点：根结点 1 2 3 5 4 6 1 2 3 5 4 6 后序线索二叉树 先序线索二叉树 51/96

6.3 –后序线索二叉树 vs 先序线索二叉树(2) 如何在后序线索二叉树上找结点的前驱？ a) 若该结点无左孩子，则其前驱由lchild指向。 b) 若该结点有左孩子且有右孩子，则其前驱为其右孩子； c) 若该结点有左孩子且无右孩子，则其前驱为其左孩子。 1 2 3 5 4 6 1 2 3 4 5 6 7 52/96

6.3 –后序线索二叉树 vs 先序线索二叉树(3) 如何在先序线索二叉树上找结点的后继？ a) 若该结点无右孩子，则其后继由rchild指向。 b) 若该结点有右孩子且有左孩子，则其前驱为其左孩子； c) 若该结点有右孩子且无左孩子，则其前驱为其右孩子。 1 2 3 5 4 6 1 2 3 4 5 6 7 53/96

6.3 –先序遍历的非递归算法(2) 算法1 54/96

6.3 –先序遍历的非递归算法(3) 算法2 55/96

6.3 –中序遍历的非递归算法 思路 T是指向要遍历的二叉树的根，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。 56/96

6.3 –后序遍历的非递归算法(1) 思路 T指向要遍历的二叉树的根，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。 可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。 首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。 typedef struct stackElement{ Bitree data; char tag; }stackElemType; 57/96

6.3 –后序遍历的非递归算法(2) 58/96