数据结构教案
第六章 树与二叉树
数据结构教案 第6章 树与二叉树
目 录
6.1 树的定义和基本术语 ............................................................................................................. 1 6.2 二叉树 ..................................................................................................................................... 2
6.2.1 二叉树的定义 .............................................................................................................. 2 6.2.2 二叉树的性质 .............................................................................................................. 4 6.2.3 二叉树的存储结构 ...................................................................................................... 5 6.3 树和森林 ................................................................................................................................. 6 6.4 二叉树的先|中|后序遍历算法 ................................................................................................ 7 6.5 先|后|中序遍历的应用扩展 .................................................................................................... 9
6.5.1 基于先序遍历的二叉树(二叉链)的创建 .................................................................... 9 6.5.2 统计二叉树中叶子结点的数目 .................................................................................. 9 6.5.3 求二叉树的高度 ........................................................................................................ 10 6.5.4 释放二叉树的所有结点空间 .................................................................................... 11 6.5.5 删除并释放二叉树中以元素值为x的结点作为根的各子树 ................................. 12 6.5.6 求位于二叉树先序序列中第k个位置的结点的值 ................................................. 12 6.5.7 线索二叉树 ................................................................................................................ 13 6.5.8 树和森林的遍历 ........................................................................................................ 14 6.6 二叉树的层次遍历 ............................................................................................................... 16 6.7 判断一棵二叉树是否为完全二叉树 ................................................................................... 16 6.8 哈夫曼树及其应用 ............................................................................................................... 18
6.8.1 最优二叉树(哈夫曼树) .............................................................................................. 18 6.8.2 哈夫曼编码 ................................................................................................................ 19 6.9 遍历二叉树的非递归算法 ................................................................................................... 19
6.9.1 先序非递归算法 ........................................................................................................ 19 6.9.2 中序非递归算法 ........................................................................................................ 20 6.9.3 后序非递归算法 ........................................................................................................ 21
数据结构教案 第6章 树与二叉树
第6章 二叉树和树
6.1 树的定义和基本术语
1、树的递归定义
1）结点数n=0时，是空树 2）结点数n>0时
有且仅有一个根结点、m个互不相交的有限结点集——m棵子树
2、基本术语
结点： 叶子(终端结点)、根、内部结点（非终端结点、分支结点）； 树的规模：结点的度、树的度、结点的层次、树的高度(深度) 结点间的关系：双亲(1)—孩子(m)，祖先—子孙，兄弟，堂兄弟 兄弟间是否存在次序：无序树、有序树 去掉根结点
非空树 森林 引入一个根结点 3、树的抽象数据类型定义
树特有的操作：
查找：双亲、最左的孩子、右兄弟 结点的度不定，给出这两种操作可以查找到一个结点的全部孩子 插入、删除：孩子
遍历：存在一对多的关系，给出一种有规律的方法遍历(有且仅访问一次)树中的结点 ADT Tree{
数据对象：D={ai | ai∈ElemSet, i=1,2,…,n, n≥0} 数据关系：若D为空集，则称为空树；
若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系：
(1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠Ф，则存在D-{root}的一个划分D1, D2, …, Dm (m>0)
（Di 表示构成第i棵子树的结点集），对任意j≠k (1≤j, k≤m) 有Dj∩Dk=Ф，且对任意的i (1≤i≤m)，唯一存在数据元素xi∈Di, 有 (3) 对应于D-{root}的划分，H-{ 意j≠k(1≤j,k≤m)有Hj∩Hk=Ф，且对任意i(1≤i≤m)，Hi是Di上的二元关系，(Di, {Hi})是一棵符合本定义的树，称为根root的子树。 基本操作： InitTree(&T) 操作结果：构造空树T DestroyTree(&T) 初始条件：树T已存在 操作结果：销毁树T ClearTree(&T) 初始条件：树T已存在 1 数据结构教案 第6章 树与二叉树 操作结果：将树T清为空树 TreeEmpty(T) 初始条件：树T已存在 操作结果：若T为空树，则返回TRUE，否则返回FALSE TreeDepth(T) 初始条件：树T已存在 操作结果：返回树T的深度 Root(T) 初始条件：树T已存在 操作结果：返回T的根 Value(T, cur_e) 初始条件：树T已存在，cur_e是T中某个结点 操作结果：返回cur_e的值 Assign(T, &cur_e, value) 初始条件：树T已存在，cur_e是T中某个结点 操作结果：结点cur_e赋值为value Parent(T, cur_e) 初始条件：树T已存在，cur_e是T中某个结点 操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为 “空” LeftChild(T, cur_e) 初始条件：树T已存在，cur_e是T中某个结点 操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返 回“空” RightSibling(T, cur_e) 初始条件：树T已存在，cur_e是T中某个结点 操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回“空” InsertChild(&T, p, i, c) 初始条件：树T已存在，p指向T中某个结点，1≤i≤p所指结点的度 +1，非空树c与T不相交 操作结果：插入c为T中p所指结点的第i棵子树。 DeleteChild(&T, p, i) 初始条件：树T已存在,p指向T中某个结点，1≤i≤p所指结点的度 操作结果：删除T中p所指结点的第i棵子树。 TraverseTree(T, visit( ) ) 初始条件：树T已存在，visit是对结点操作的应用函数 操作结果：按某种次序对T的每个结点调用函数visit( )一次且至多一次。 一旦visit( )失败，则操作失败 }ADT Tree 6.2 二叉树 一般树的度不定，直接考虑其操作比较困难，故首先考虑度为二的树。这里引入二叉树。 6.2.1 二叉树的定义 1、二叉树的特殊性 ·0≤度≤2 ·子树有左右之分（子树的个数 = 1 或2时） 注意：0≤度≤2的有序树≠二叉树 2 数据结构教案 第6章 树与二叉树 当某个结点只有一棵子树时，不存在序的概念 2、二叉树的抽象数据类型定义 二叉树相对树的特殊性： 最左的孩子、右兄弟 左孩子、右孩子 遍历的规律性： L(左子树)、D(根)、R(右子树)的排列上 限定为L在R前访问(有对称关系的，只须考虑其中的一种) ADT BinaryTree{ 数据对象：D={ai | ai∈ElemSet, i=1,2,…,n, n≥0} 数据关系：若D为空集，则称为空树； 若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠Ф，则存在D-{root}的一个划分DL, DR（左、右子树的结点集），且DL∩DR=Ф； (3) 若DL≠Ф，则DL中存在唯一元素xL, 有 中存在唯一元素xR, 有 基本操作： InitBiTree(&T) 操作结果：构造空二叉树T DestroyBiTree(&T) 初始条件：二叉树T已存在 操作结果：销毁二叉树T ClearBiTree(&T) 初始条件：二叉树T已存在 操作结果：将二叉树T清为空树 BiTreeEmpty(T) 初始条件：二叉树T已存在 操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE BiTreeDepth(T) 初始条件：二叉树T已存在 操作结果：返回二叉树T的深度 Root(T) 初始条件：二叉树T已存在 操作结果：返回T的根 Value(T, cur_e) 初始条件：二叉树T已存在，cur_e是T中某个结点 操作结果：返回cur_e的值 Assign(T, &cur_e, value) 初始条件：二叉树T已存在，cur_e是T中某个结点 操作结果：结点cur_e赋值为value Parent(T, cur_e) 初始条件：二叉树T已存在，cur_e是T中某个结点 操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为 “空” 3 数据结构教案 第6章 树与二叉树 LeftChild(T, cur_e) 初始条件：二叉树T已存在，cur_e是T中某个结点 操作结果：若cur_e是T的非叶子结点，则返回它的左孩子，否则返回 “空” RightChild(T, cur_e) 初始条件：二叉树T已存在，cur_e是T中某个结点 操作结果：若cur_e有右孩子，则返回它的右孩子，否则返回“空” LeftSibling(T, cur_e) 初始条件：二叉树T已存在，cur_e是T中某个结点 操作结果：返回cur_e的左兄弟，若cur_e是T的左孩子或无左兄弟， 则返回“空” RightSibling(T, cur_e) 初始条件：二叉树T已存在，cur_e是T中某个结点 操作结果：返回cur_e的右兄弟，若cur_e是T的右孩子或无右兄弟， 则返回“空” InsertChild(&T, p, LR, c) 初始条件：二叉树T已存在，p指向T中某个结点，LR为0或1，非空 二叉树c与T不相交 操作结果：插入c为T中p所指结点的左或右子树。p所指结点的原有 左或右子树则成为c的右子树 DeleteChild(&T, p, LR) 初始条件：二叉树T已存在，p指向T中某个结点，LR为0或1 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。 PreOrderTraverse( T, visit( )) 初始条件：二叉树T已存在，visit是对结点操作的应用函数 操作结果：先序遍历T，对每个结点调用函数visit()一次且仅一次。一旦 visit()失败，则操作失败 InOrderTraverse( T, visit( )) 初始条件：二叉树T已存在，visit是对结点操作的应用函数 操作结果：中序遍历T，对每个结点调用函数visit( )一次且仅一次。一 旦visit( )失败，则操作失败 PostOrderTraverse( T, visit( )) 初始条件：二叉树T已存在，visit是对结点操作的应用函数 操作结果：后序遍历T，对每个结点调用函数visit( )一次且仅一次。一 旦visit( )失败，则操作失败 LevelOrderTraverse( T, visit( )) 初始条件：二叉树T已存在，visit是对结点操作的应用函数 操作结果：层序遍历T，对每个结点调用函数visit( )一次且仅一次。一 旦visit( )失败，则操作失败 }ADT BinaryTree 6.2.2 二叉树的性质 1、性质1：第i层至多有2i-1个结点（由每个结点最多只有2个孩子推出） 2、性质2：深度为k的二叉树至多有2k-1个结点（由性质1，将各层最多的结点数累加，再结合等比数列的求和得出） 思考：深度为k的二叉树至少有多少个结点？( k个 ) 深度为k的b叉树至多/至少有多少个结点？( (bk-1)/(b-1)，k) 3、性质3：n0=n2+1 (ni表示二叉树中度为i的结点个数) 4 数据结构教案 第6章 树与二叉树 从两个角度考虑：二叉树中结点的构成（根据度）n = n0 + n1 + n2 二叉树中充当其余结点的孩子的结点数n-1(去掉根) = n1+2×n2 满二叉树：达到性质1,2中所述的最大值情况 完全二叉树：去掉最下一层的结点，其余结点形成一棵满二叉树；叶子集中在最下2层(或1层)，最下一层的结点总是尽可能地占满左边的位置 logn14、性质4：具有n个结点的完全二叉树的深度为 25、性质5：结点间的编号关系 考虑二叉树的顺序映像问题，寻求一种将二叉树映像为向量的方法： 对完全二叉树从上至下，从左至右，从根开始依次编号(1..n)。 求双亲 求孩子 求左兄弟 求右兄弟 孩子编号 i 左：2*i( #define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */ typedef ElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点 */ 必须引入特殊符号表示虚结点的值 上述类型定义的缺陷：未指明实际二叉树占用的长度，可改进为： typedef struct{ ElemType elem[MAX_TREE_SIZE+1]; /* 1号单元存储根结点 */ int length; }SqBiTree; 3) 不足：空间的利用率不高 如：若深度为5且仅含有5个结点的二叉树，必须要占用24~25-1空间。 5 数据结构教案 第6章 树与二叉树 2、二叉树的链式存储结构 1) 引入辅助空间表示结点间的相对关系 双亲(1)——孩子(2) (如右图) lchild data rchild parent lchild data rchild 二叉链表 三叉链表 若需要找指定结点的双亲，则用三叉链表可在O(1)时间内获得某 parent data lchild rchild 结点的双亲；而用二叉链表则需从根开始，采用一定的巡查方法进行搜索。 2) 二叉链表的类型定义 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; 3) 二叉链表的链域 若有n个结点，则共有2n个链域；其中n-1不为空，指向孩子。 4) 二叉树(链式存储)的创建 输入序列与二叉树的映射关系 (1) 完全二叉树的顺序映射 通过补虚结点，将一般的二叉树转变成完全二叉树，再对该完全二叉树的结点按自上而下、自左至右进行输入。 (2) 二叉树的先序遍历 通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍历进行输入。 (3) 二叉树的两种遍历序列：先序+中序，后序+中序 /* 左右孩子指针 */ 6.3 树和森林 1、树的存储结构 1) 双亲表示法 针对每一结点，附设指示其双亲位置的数据域。采用顺序表（非顺序映像）。 #define MAX_TREE_SIZE 100 /* 树的最大结点数 */ typedef struct PTNode{ ElemType data; int parent; }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int n; /* 结点数 */ }PTree; 2) 孩子表示法 各结点的孩子数是不定的，用顺序表表示必须给出树的度的最大值，以及每一结点的实际度数，空间浪费大。故以链表存储每一结点的所有孩子的位置信息。 typedef struct CTNode{ /* 孩子结点 */ int child; /* 孩子结点的位置编号*/ struct CTNode *next; /* 下一个孩子结点 */ }*ChildPtr; typedef struct{ 6 数据结构教案 第6章 树与二叉树 TElemType ChildPtr }CTBox; typedef struct{ CTBox int }CTree; 3) 孩子兄弟法 data; firstchild; /* 孩子链表的头指针 */ nodes[MAX_TREE_SIZE]; n, r; /* 结点数和根的位置 */ 二叉链表表示。针对每一结点，引入其第一个孩子和下一个右兄弟的位置域。 typedef struct CSNode{ ElemType data; struct CSNode *firstchild, *nextsibling; /* 第一个孩子、下一个兄弟指针 */ }CSNode, *CSTree; 2、森林与二叉树的转换 森林用孩子兄弟法表示，形成二叉链表，可以将它理解为一个二叉树的二叉链表； 二叉树用二叉链表表示，可以将该二叉链表理解为孩子兄弟链表，从而获得森林。 6.4 二叉树的先|中|后序遍历算法 1、遍历 ·对于二叉树中的结点，有且仅访问一次 ·遍历的规律性： L(左子树)、D(根)、R(右子树)的排列上 限定L在R前访问(有对称关系的，只须考虑其中的一种) ·先(根)序遍历 DLR ·中(根)序遍历 LDR ·后(根)序遍历 LRD 2、二叉树遍历的递归实现 遍历路径 二叉树的递归定义性质，决定了它的很多算法都可用递归实现，- 遍历就是其中之一。 先序访问 对于二叉树的遍历，可以不去具体考虑各子问题(左子树、根、右 c * 子树)的遍历结果是什么，而去考虑如何由各子问题的求解结果构成原问题(二叉树)的遍历结果——递归规律的确定。必须注意的是，当二 b a 叉树小到一定程度，即空树时，应直接给出解答——递归结束条件及 处理。 三种遍历的区别(右图)：所经过的搜索路线是相同的；只是访问中序访问 后序访问 结点的时机不同。每一结点在整个搜索路线中会经过3次（第一次进入到该结点、由左子树回溯到该结点、由右子树回溯到该结点），如在第一次遇到时就访问该结点，那么称之为先序；第二次经过时访问为中序；第三次经过时访问则为后序。 1) 先序遍历 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; } 7 数据结构教案 第6章 树与二叉树 else return OK; } 2) 后序遍历 Status PostOrderTraverse( BiTree T, Status ( *Visit ) (ElemType e) ){ if ( T != NULL ){ if ( PostOrderTraverse( T->lchild, Visit ) ) if ( PostOrderTraverse( T->rchild, Visit ) ) if ( Visit(T->data) ) return OK; return ERROR; } else return OK; } 3) 中序遍历 Status InOrderTraverse( BiTree T, Status ( *Visit ) (ElemType e) ){ if ( T != NULL ){ if ( InOrderTraverse( T->lchild, Visit ) ) if ( Visit(T->data) ) if ( InOrderTraverse( T->rchild, Visit ) ) return OK; return ERROR; } else return OK; } 8 数据结构教案 第6章 树与二叉树 6.5 先|后|中序遍历的应用扩展 利用二叉树的遍历算法，适当修改访问结点操作的内容，可以得到求解许多问题的算法。 二叉树的创建（基于先序遍历） 二叉树的线索化 查找指定结点：在访问结点时，判断当前访问的结点是否是指定的结点，若是则返回 该结点位置，否则继续遍历； 查找位于某种遍历次序中的第k位的结点：遍历前，引入一计数器，用来统计已访问 过的结点数，初值为0；在访问结点时，将该计数器增1，并看是否达到k，……； 求叶子结点的数目：遍历前，引入叶子结点计数器，初值为0；访问结点时，将该计 数器增1；遍历结束，则计数器中的值即为所求解； 判断二叉树中是否仅包含有度为2和0的结点：访问结点时，判断该结点孩子的有无 情况，…… 求指定结点的层次：孩子结点的层次比其双亲结点层次多一； 求二叉树的高度：二叉树的高度 = max(左子树的高度, 右子树的高度) +1 6.5.1 基于先序遍历的二叉树(二叉链)的创建 【本例特征】 如何基于二叉树的先序、中序、后序遍历的递归算法进行问题求解？ 【思路】 先 序 遍 历PreOrderTraverse 创 建CreateBiTree 带虚结点的先序序列ch 由输入设备输入scanf( &ch ) 二叉链表示的二叉树的头指针T 变参 ch == END_DATA（表示虚结点的值） T = NULL T = ( BiTree)malloc( sizeof( BiTNode )) T->data = ch CreateBiTree( T->lchild ) CreateBiTree( T->rchild ) 输入 二叉链表示的二叉树的头指针T 输入的表现方式 参数 输出 对结点的访问结果 输出的表现方式 由输出设备输出 空树（递归结束）的T == NULL 条件及处理 空 (直接求解) 根结点的访问 Visit( T->data ) (子问题直接求解) 左子树 PreOrderTraverse( T->lchild ) (使用递归调用的解) 右子树 PreOrderTraverse( T->rchild ) (使用递归调用的解) 【算法】见《数据结构(C语言版)》P131算法6.4。 6.5.2 统计二叉树中叶子结点的数目 【本例特征】 如何通过全局变量、变参、返回值三种渠道返回处理结果？ 【思路】 在遍历二叉树时，对一些特殊的结点(无左右孩子)进行计数。可以修改遍历算法的结点访问操作为对特殊结点的判定和计数过程，需要注意的是计数器的处理方式。可以有以下几种计数处理： ·用遍历函数的返回值传出求得的叶子结点的数目； 9 数据结构教案 第6章 树与二叉树 ·为遍历函数增加一个引用参数，用来传出指定二叉树的叶子结点数目。 ·引入全局的计数器，初始为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; 【算法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); } 【算法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; } } 6.5.3 求二叉树的高度 【思路】 ·二叉树为空时，高度为0； ·若T不为空，则其高度应为其左右子树高度的最大值再加1。 可以有以下几种处理高度值的方法： ·用遍历函数值返回指定二叉树的高度； 10 数据结构教案 第6章 树与二叉树 ·遍历函数增加一个引用参数，用来传出指定二叉树的高度。 【算法1】 // 函数值为T的高度 int high(BiTree T) { if ( T == NULL ) return ( 0 ); else return( max ( high (T->lchild ), high (T->rchild) ) +1 ) ; } 【算法2】 // 引用参数h为T的高度 void high(BiTree T, int &h) { // 利用二叉树的后序遍历 if ( T == NULL ) h=0; else { high(T->lchild, h1); high(T->rchild, h2); h = max(h1, h2)+1; } } 6.5.4 释放二叉树的所有结点空间 【思路】 ·二叉树为空时，不必释放； ·若T不为空，则先释放其左右子树的所有结点的空间，再释放根结点的空间——后序。 若在释放子树的空间前，先释放根结点的空间，则需要将子树的根结点的指针暂存到其他变量；否则，无法找到子树。 【算法1】 // 此处T应为引用参数，因为经过本函数处理后，T的值发生了变化 void deleteBiTree(BiTree &T) { if ( T != NULL ){ deleteBiTree(T->lchild ); deleteBiTree(T->rchild ); // 访问结点->释放结点的空间 free(T); T = NULL; } } 【算法2】 void deleteBiTree(BiTree &T) { if ( T != NULL){ // 先序遍历，暂存孩子结点指针 T1 = T->lchild; T2 = T->rchild; // 访问结点->释放结点的空间 free(T); T = NULL; deleteBiTree(T1); deleteBiTree(T2); } 11 数据结构教案 第6章 树与二叉树 } 6.5.5 删除并释放二叉树中以元素值为x的结点作为根的各子树 【本例特征】 如何选择二叉树的先序、中序、后序遍历来解决问题，它们对问题求解有何影响？ 【思路】 整个过程分为两个方面： ·遍历中查找元素值为x的结点 ·查到该结点时，调用6.5.3的算法释放子树空间。 需要考虑的问题是：如何将全部的结点找到并释放？外层查找采用的遍历次序对本算法有何影响？从以下3个算法中可以看出，利用先序遍历是最合适的；中序和后序，存在一定的多余操作。 【算法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); } } } 【算法2】 void deleteXTree(BiTree &T, ElemType x) { // 基于中序的查找 if ( T != NULL ){ deleteXTree(T->lchild, x); // 若T->data== x，则此步骤多余 // 访问结点->判断是否为指定结点->释放树空间 if ( T->data== x) deleteBiTree(T); else deleteXTree(T->rchild, x); } } 【算法3】 void deleteXTree(BiTree &T, ElemType x) { // 基于后序的查找 if ( T != NULL ){ deleteXTree(T->lchild, x); // 若T->data== x，则此步骤多余 deleteXTree(T->rchild, x); // 若T->data== x，则此步骤多余 // 访问结点->判断是否为指定结点->释放树空间 if ( T->data == x ) deleteBiTree(T); } } 6.5.6 求位于二叉树先序序列中第k个位置的结点的值 【本例特征】 多个返回结果如何处理？ 12 数据结构教案 第6章 树与二叉树 【思路】 ·待查找的结点的存在性：当二叉树为空树，或者k非法时，待查找的结点是不存在的 函数应返回待查找的结点是否存在的状态指示：TRUE-存在，FALSE-不存在 ·当待查找的结点存在时，需进一步返回该结点的值 问题1：该算法需要返回多个值，如何处理？ 答：一种做法是用返回值返回存在性，用变参返回值。 问题2：该算法可以基于二叉树的先序遍历的递归算法来构造，如何知道当前访问的结点是先序序列中的第几个结点？ 答：引入计数器，对于该计数器可以采用全局变量来存储，也可以通过变参来处理。 【算法】 Status PreorderKnode(BiTree T, int k, ElemType &e, int &count) // 输入：T为二叉链表示的二叉树，k为待查找的结点在先序序列中的位序(1≤k≤n，假设n // 为二叉树T中的结点个数 // 输出：返回值—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; } } 【调用示意】 int c=0; … if ( PreorderKnode(T, k, e, c)==TRUE ) … 6.5.7 线索二叉树 1、线索二叉树的基本概念 1） 二叉树的遍历结果为一个线性序列； 2） 有n个结点的二叉树的二叉链表中，有n+1个空链域； 3） 扩展二叉链，利用空链域存放结点在某种遍历次序下的直接前驱和直接后继信息 4） 扩展二叉链的结点： lchild ltag data rtag rchild ltag : 0—结点的左孩子； 1—结点的直接前驱 rtag : 0—结点的右孩子； 1—结点的直接后继 5） 名词：线索链表、线索、线索二叉树、线索化 13 数据结构教案 第6章 树与二叉树 6） 类型定义 typedef enum { Link, Thread} PointerTag; // Link==0:指针，Thread==1: 线索 typedef struct BiThrNode{ ElemType data; struct BiThrNode *lchild, *rchild; // 左右孩子指针 PointerTag ltag, rtag; // 左右标志 }BiThrNode, *BiThrTree; 为二叉树的线索链表增加一个头结点，令其lchild域指向二叉树的根结点，rchild域指向中(前/后)序遍历时访问的最后一个结点；中序序列中的第一个结点的lchild域和最后一个结点的rchild域指向头结点。 2、在线索树上进行遍历（P133） 3、中序线索化二叉树（二叉树的中序遍历算法的应用） InOrderThreading(BiThrTree &thrt, BiThrTree T) 过程：分配头结点、头结点域的赋值、调用InThreading( )线索化、填充头结点的rchild域 引入全局指针pre保留中序遍历时刚刚访问过的结点，这样便于处理pre指向的结点与当前要访问的结点中的链，使这两个结点满足前驱-后继的关系。 InThreading( )用来递归地进行二叉链的中序线索化，故pre的初始化不应在InThreading( )中进行，而可以放在InOrderThreading( )中进行。 输入 输入的表现方式 输出 输出的表现方式 空树（递归结束）的条件及处理 (直接求解) 左子树 (使用递归调用的解) 中 序 遍 历InOrderTraverse 二叉链表示的二叉树的头指针T 参数 对结点的访问结果 由输出设备输出 T == NULL 空 InOrderTraverse( T->lchild ) 中序线索化二叉树InThreading 线索二叉链表示的二叉树的头指针p 参数 修改p指向的结点的链域 参数 p == NULL 空 InThreading( p->lchild ) if ( p->lchild== NULL ) { p->ltag = Thread; p->lchild = pre; } if ( pre->rchild== NULL ) { pre->rtag = Thread; pre->rchild = p; } pre = p; InThreading( p->rchild ) 根结点的访问 (子问题直接求解) Visit( T->data ) 右子树 PreOrderTraverse( T->rchild ) (使用递归调用的解) 6.5.8 树和森林的遍历 树：先序、后序，不提中序。 用孩子-兄弟法表示后，可以对该二叉链表进行先序遍历和中序遍历，获得相应树的先序和后序遍历结果。 树的一些问题可以借鉴二叉树的一些处理方法来解决。 14 数据结构教案 第6章 树与二叉树 1、统计树(森林)中叶子结点的个数 孩子-兄弟法：每个结点包含一个指向第一个孩子和一个指向下一个右兄弟的指针域 叶子结点的特征：结点的firstchild为空 统计叶子结点的个数→在遍历的过程中统计firstchild域为空的结点的个数。 【算法】 // n为叶子结点的计数器 int n=0; void CSleaf(CSTree T) { // 利用树的先序遍历 if ( T != NULL ){ // 访问结点->叶子结点的判定和计数 if ( T->firstchild == NULL ) n++; CSleaf(T->firstchild); CSleaf(T->nextsibling); } } // 调用结束，即可由n获得树T的叶子结点数目，需注意下次调用前须n = 0; 2、求树的高度 孩子-兄弟法表示的树： 树的高度 = max(相应左子树的高度+1，右子树的高度) 【算法】 // 引用参数h为T的高度 void CShigh(CSTree T, int &h) { // 利用二叉链表的后序遍历 if ( T == NULL ) h = 0; else { CShigh(T->firstchild, h1); CShigh(T->nextsibling, h2); h = max(h1+1, h2); } } 3、求树的度 【算法】 // degree表示表示树的度 void CSDegree(CSTree T, int °ree) { // 利用二叉树的先序遍历 // d表示T指向的结点的度 if ( T == NULL ) degree = 0; else{ if ( T->firstchild == NULL ) d = 0; else{ d = 1; p = T->firstchild; while ( p->nextsibling != NULL ){ p = p->nextsibling; d++; } } CSDegree (T->firstchild, d1); CSDegree (T->nextsibling, d2 ); 15 数据结构教案 第6章 树与二叉树 degree = max (d1, d2, d ); } } 6.6 二叉树的层次遍历 【思路】 先访问的结点，其孩子结点必然也先访问。引入队列存储已被访问的、但其左右孩子尚未访问的结点的指针。若使用链队列，其元素可定义为： 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); // 从队列中取已被访问的、但其左右孩子尚未访问的结点指针，访问其孩子 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; } 【算法应用】 利用层次遍历，可以求解： ·找出距指定结点最近或最远的叶子子孙； ·找出指定层的所有(叶子、2度、1度)结点； ·判断二叉树是否为完全二叉树、满二叉树； ·一般树的层次遍历（树用孩子-兄弟法表示） 6.7 判断一棵二叉树是否为完全二叉树 【思路】 由完全二叉树的定义，对完全二叉树按层次遍历应满足： 16 数据结构教案 第6章 树与二叉树 1） 若某结点没有左孩子，则它一定无右孩子； 2） 若某结点缺孩子，则其后继必无孩子。 利用层次遍历，需要附加一个标志量bFlag反映是否已扫描过的结点均有左右孩子。在第一次遇到缺孩子的结点时，可将bFlag置为FALSE；此时存在以下两种情况： ·若它满足1），需要继续扫描后继结点，以判断是否满足2）； ·若不满足1），则说明不是完全二叉树。 【算法】 typedef char BOOL; #define TRUE 1 #define FALSE 0 BOOL JudgeCBT(BiTree T) { // 初始化队列和标志量bFlag InitQueue (Q); bFlag = TRUE; if ( T != NULL ){ EnQueue(Q, 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 ) // 第一次遇到结点有左孩子，缺右孩子 bFlag = FALSE; else EnQueue(Q, p->rchild ); } } } return TRUE; // T为空，也是完全二叉树 } 【思考】 上述算法在每一种完全二叉树不成立时，即返回FALSE；请修改算法，使得用统一的return返回判断结果。（提示：引入另一标志量，保存当前的扫描是否符合完全二叉树的判断条件） 17 数据结构教案 第6章 树与二叉树 6.8 哈夫曼树及其应用 6.8.1 最优二叉树(哈夫曼树) 1、基本概念 结点间的路径长度、树的路径长度(根到其余结点的路径长度之和) 完全二叉树是树的路径长度最短的二叉树 证明： 图 具有不同路径长度的二叉树 对图（a），PL＝0+1+1+2+2+2+2+3＝13 对图（b），PL＝0+1+1+2+2+2+3+3＝14 显然，前者的路径长度短。 回忆二叉树的性质，第i层的结点个数最多2i-1，而第i层结点到根的路径长度为i-1。由此可知，到根结点的路径长度为m的结点最多2m个。 如图(a)所示的完全二叉树，二叉树的路径长度是以下数列前n项的和： 0，1，1，2，2，2，2，3，3，3，3，3，3，3，3，4，4，… 而图(b)所示的一般二叉树，虽然也是8个结点，但所取路径长度不是上面数列前的和，而是向后跳着取的：0，1，1，2，2，2，3，3，因而其路径长度就比较大，由此可得到以下结论：n个结点的二叉树的路径长度不小于前述数列前n项的和，即 PLlog2(i1) i0n1其路径长度最小者为 PLlog2(i1) i0n1完全二叉树的长度就满足这个要求。 当然，除了完全二叉树外，只要满足上述要求的二叉树都具有最小路径长度。一般来说，若一颗n个结点的高度为k的二叉树，若前k-1层为满二叉树，其余的结点可分布在第k层的任何一个位置上。 结点的带权路径长度(结点到根的路径程度与结点的权的乘积) 树的带权路径长度(树中所有叶子结点的带权路径长度之和) 哈夫曼树(最优二叉树)：树的带权路径长度最小的二叉树。 2、应用 ·各种条件分支的最优位置安排，如何使执行频度高的分支尽快找到(放在靠前的条件判断上处理) ·非等概率下的最优编码(平均码长最短)问题 3、哈夫曼算法 18 数据结构教案 第6章 树与二叉树 已知：n个权值wi (0 1） 初始：n个权值—>n棵二叉树集合F，Ti∈F，Ti只含带权为wi的根结点 2） 从F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且新 的二叉树的根结点的权值是其左、右子树上根结点的权值之和； 3） 在F中删除这两棵树，同时将新得到的二叉树加入F中； 4） 重复2）和3），直至F只含一棵树为止。 哈夫曼树的性质： ·不含1度结点； ·一组权值，可能生成多种形态的哈夫曼树 ·叶子结点数为n，则哈夫曼树中的结点数为2n-1。 6.8.2 哈夫曼编码 1、基本概念 前缀编码：任一字符的编码都不是另一字符的编码的前缀。 哈夫曼编码：在已知各种字符的出现概率下，为各字符提供一种不等长的平均码长(li为第i个字符的编码长度，pi为第i个字符的出现概率)最短的编码方案 2、哈夫曼编码 1) 哈夫曼树的存储 结点：权值，双亲(编码用)，左孩子、右孩子(解码)——三叉链表 2) 哈夫曼编码的存储 每一编码对应一字符串，故采用二级字符指针存储。 3) 过程 ·建哈夫曼树(由于结点数确定2n-1，故可以一次分配全部结点的空间) ·编码过程(从叶子到根的逆向求编码。需要知道结点的双亲信息，因此要用三叉链表) ·译码方法(从根开始，根据编码值0/1，决定走左分支还是右分支，逐个匹配，直至到达叶子结点，此时可以译得一个字符；从下一个未匹配的编码值开始，重新从根开始继续译码过程) lp, iii6.9 遍历二叉树的非递归算法 编写的方法：根据树中结点的遍历规律及顺序直接写出其非递归算法。 6.9.1 先序非递归算法 【思路】 假设：T是要遍历树的根指针，若T != NULL 对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。 问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？ 方法1：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 方法2：访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。 【算法1】 19 数据结构教案 第6章 树与二叉树 void PreOrder(BiTree T, Status ( *Visit ) (ElemType e)) { // 基于方法一，流程图如右，当型循环 InitStack(S); while ( T!=NULL || !StackEmpty(S)){ while ( T != NULL ){ Visit(T->data) ; 置栈S为空 Push(S,T); T = T->lchild; T为空 } N if( !StackEmpty(S) ){ 访问根结点 Pop(S,T); Push(S,T) T = T->rchild; T=T->lchild } } } 【算法2】 void PreOrder(BiTree T, Status ( *Visit ) (ElemType e)) { // 基于方法二，流程图如右，当型循环 InitStack(S); while ( T!=NULL || !StackEmpty(S) ){ 置栈S为空 while ( T != NULL ){ Y Visit(T->data); T为空 Push(S, T->rchild); N T = T->lchild; 访问根结点 } Push(S,T->rchild) if ( !StackEmpty(S) ){ T=T->lchild Pop(S,T); } } } 进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。 6.9.2 中序非递归算法 栈S空 N Pop(S, T); T=T->rchild Y 栈S空 N Pop(S, T); Y 【思路】 T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？ 方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。 【算法】 void InOrder(BiTree T, Status ( *Visit ) (ElemType e)) { // 流程图如右，当型循环 置栈S为空 InitStack(S); while ( T!=NULL || !StackEmpty(S) ){ while ( T != NULL ){ T为空 Push(S,T); Y N 栈S空 T = T->lchild; Push(S,T) N } T=T->lchild Pop(S, T); if( !StackEmpty(S) ){ 访问根结点 Pop(S, T); T=T->rchild Visit(T->data); 20 数据结构教案 第6章 树与二叉树 T = T->rchild; } } } 进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。 6.9.3 后序非递归算法 【思路】 T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。 可采用标记法，结点入栈时，配一个标志tag 置栈S为空 一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。 Y T为空 首先将T和tag(为0)入栈，遍历左子树；返Y N 栈S空 回后，修改栈顶tag为1，遍历右子树；最后访问 Push(S,T, 0); N 根结点。 T=T->lchild typedef struct stackElement{ 栈顶标记为1 N Y Bitree data; char tag; 栈顶标记置1 Pop(S, T, tag) 访问T->data T=T->rchild }stackElemType; 【算法】 void PostOrder(BiTree T, Status ( *Visit ) (ElemType e)) { // 流程图如右，当型循环 InitStack(S); while ( T!=NULL || !StackEmpty(S) ){ while ( T != NULL ){ Push(S,T,0); T = T->lchild; } while ( !StackEmpty(S) && GetTopTag(S)==1){ Pop(S, T); Visit(T->data); } if ( !StackEmpty(S) ){ SetTopTag(S, 1); // 设置栈顶标记 T = GetTopPointer(S); // 取栈顶保存的指针 T = T->rchild; }else break; } } 21
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- 517ttc.cn 版权所有 赣ICP备2024042791号-8
违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务