C++程序设计第四章树形结构

1、数 据 结 构 第4章 树型结构学习要点熟练掌握二叉树的结构特性，了解相应的证明方法。 建立存储结构是进行操作的前提。故须熟悉二叉树的各种存储结构、并把握各种存储结构的特点及适用范围。 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其他操作。理解包括层次遍历在内的各种非递归遍历的算法。 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化二叉树上找到给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索

2、又为相应的遍历提供了方便。 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。 学会编写实现树的各种操作的算法。 理解等价关系和等价类问题。 了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。 第4章 树型结构 树型结构是一种典型的分支结构，并且具有明显的层次特征。 树型结构在客观世界中是广泛存在的，如家族谱、组织机构、博弈等都可用树型结构形象地表示。 树型结构在计算机领域中也有着广泛的应用：编译程序、数据库系统、分析算法4.1 树、森林的定义及基本术语 树(tree)是n ( )个结点的有限集T，当n=0时称为空树，否则满足以下两个条件： 有且仅有一个特定的结点，称为树的根(r

3、oot) 其余结点可分为m( )个互不相交的子集T1,T2,Tm，其中每一个子集本身又是一棵树，并称其为根结点的子树(subtree)0n0m4.1 树、森林的定义及基本术语 森林是m（m0）棵互不相交的树的集合。 用森林的定义也可定义树：一棵非空的树由根结点及其子树森林所构成。 树和森林均为典型的树型结构，从形态上看，树结构类似于自然界倒长的一棵树4.1树、森林的定义及基本术语 基本术语 结点：包含了数据元素及若干个指向其子树的分支。 结点的度：结点的子树数目或分支个数。 树的度：在树中取各结点的度的最大值。 分支结点（又称非终端结点）：度大于零的结点。 树叶结点（又称终端结点）：度为零的结

4、点。 结点的路径：根结点到该结点所经分支和结点构成结点的路径。 结点的路径长度：根结点到该结点路径上所经分支的数目。 4.1树、森林的定义及基本术语 基本术语 结点的层次：设根结点的层次为1，则其子树的根结点层次为2；第L 层结点的子树的根结点层次为L+1。 树的深度：树中结点（该结点必为树叶结点）的最大层次。 孩子结点及双亲结点：结点的子树的根结点称为该结点的孩子结点，该结点又称为孩子结点的双亲结点。 兄弟结点：拥有同一个双亲结点的若干个结点互称为兄弟结点。 堂兄弟结点：在同一层次上，但双亲结点不同的若干个结点称为堂兄弟结点。 4.1树、森林的定义及基本术语 基本术语 祖先结点：根结点到该结

5、点路径上的所有结点均为该结点的祖先结点。 子孙结点：某结点的子树中所包含的所有结点均为该结点的子孙结点。 无序树：子树之间不存在次序关系，即子树能够调换，则称该树为无序树。 有序树：子树之间映射客观存在的次序关系（子树不能调换），则称该树为有序树。 线性结构和树型结构的比较线性结构线性结构树型结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继) 多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)4.2 二叉树4.2.1 二叉树的结构定义 二叉树定义二叉树是n（n0）个结点的有限集，当n=0时，二叉树为空；当n0时，二叉树由一个根

6、结点及至多两棵互不相交的左右子树组成，且左右子树都是二叉树。二叉树特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒4.2.1 二叉树的结构定义 二叉树的基本形态空二叉树只有根结点的二叉树右子树为空左子树为空左右子树均非空4.2.2 几种特殊形态的二叉树 满二叉树：一棵深度为k的二叉树若每一层上的结点数都达到最大则称其为满二叉树。 完全二叉树：一棵具有n个结点且深度为k的二叉树若前 k1层的结点数都达到最大，剩余的结点在第k层中从左至右连续分布则称其为完全二叉树。 拟满二叉树：一棵具有n个结点且深度为k的二叉树若前 k1层的结点数都达到最大，剩余

7、的结点在第k层中随机分布则称其为拟满二叉树。 正则二叉树：在一棵二叉树中，如果只存在度为0和度为2的结点则称其为正则二叉树。 平衡二叉树：在一棵二叉树中，若其任一子树型均满足：|左子树的深度右子树的深度|1，则称其为平衡二叉树。 4.2.2 几种特殊形态的二叉树4.2.3 二叉树的性质 二叉树性质1 在二叉树的第 i 层上至多有2i-1 个结点。 (i1) 证明：用归纳法证明之1. i=1时，只有一个根结点，2i-1 = 20 = 1；是对的2. 假设对所有j(1 ji)命题成立，即第j层上至多有2j-1 个结点，那么，第i-1层至多有2i-2 个结点又二叉树每个结点的度至多为2，第i层上最大

8、结点数是第i-1层的2倍，即2i-2 * 2 = 2i-1 故命题得证4.2.3 二叉树的性质 二叉树性质2 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。 证明基于上一条性质，深度为 k 的二叉树上的结点数至多为20+21+ +2k-1 = 2k-1 。4.2.3 二叉树的性质 二叉树性质3 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。 证明：设n1 为二叉树中度为1的结点数，二叉树上结点总数 n = n0 + n1 + n2 ，又二叉树上分支总数 b = n1 +2 n2 ，而 b = n-1 = n0 + n1 +

9、n2 - 1，由此， n0 = n2 + 1 。一棵完全二叉树的例子 4.2.3 二叉树的性质 二叉树性质4 具有 n 个结点的完全二叉树的深度为 +1 证明设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；3. 若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。4.2.3 二叉树的性质用归纳法证明如下： 当i=1 时，由完全二叉树的定义及编号规则可知，i 结点是二叉树的根，其左孩子若存在编号是2 即2i，右孩子若存在编号是3 即2i+1，性质成立。 设编号

10、为i-1 的结点其左孩子若存在编号是2(i-1)，右孩子若存在编号是2(i-1) +1 性质成立。 由完全二叉树的定义及编号规则可知，对于第i 个结点，其左孩子若存在，编号必为编号为i-1 的那个结点的左孩子位序加2，即2(i-1)+2=2i；右孩子若存在，编号必为编号为i-1 的那个结点的右孩子位序加2，即2(i-1) +1+2=2 i+1，故和成立。 性质得证。4.2.4 二叉树的存储结构 顺序存储结构 特点 结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素const MAXSIZE=100; / 暂定二叉树中结

11、点数的最大值为100struct SqBiTree ElemType *base; /存储空间基址 int nodeNum; /二叉树中结点数 ;二叉树的存储结构(顺序存储)4.2.4 二叉树的存储结构 二叉树的链式存储结构 二叉链表/ BTnode.h，二叉链表结点结构 template struct BTnode ElemType Data; BTnode *Lchild , *Rchild ; ; lchilddatarchild二叉链表例 ABCDEFGABCDEFG在n个结点的二叉链表中，有n+1个空指针域Root4.2.4 二叉树的存储结构 二叉树的链式存储结构三叉链表templa

12、te struct BTnode ElemType Data; BTnode *Lchild , *Rchild; BTnode *parent;lchilddatarchildparent三叉链表例 rootABCDEFG A B C D E F G4.2.5 二叉链表类的定义 二叉链表类模板/BinaryTree.h #ifndef _BINARYTREE_H #define _BINARYTREE_H #include #include #include BTnode.h using namespace std; template /二叉链表类 class BinaryTree publ

13、ic: BinaryTree():m_root(NULL) / 构造函数 BinaryTree(const BinaryTree &rhs) /拷贝构造 m_root=_Copy (rhs.m_root); 4.2.5 二叉链表类的定义 二叉链表类模板BinaryTree& operator=(const BinaryTree &rhs)/赋值重载 if(&rhs=this) return *this; _Destroy(m_root); m_root=_Copy( rhs.m_root); return *this; BinaryTree() /析构函数 _D

14、estroy(m_root); /按以先序次序输入结点值的方式建立二叉树的接口函数void Create1(ElemType ch,const ElemType &endChar); /以二叉树的先序和中序次序建立二叉树的接口函数 void Create2(ElemType ch1,ElemType ch2,int); 4.2.5 二叉链表类的定义 二叉链表类模板/先序递归遍历二叉树的接口函数 void PreorderTraverse (void (*visit)(const ElemType &); /先序非递归遍历二叉树的接口函数 void PreorderTravers

15、eNonRecursive (void (*visit)(const ElemType &);/中序递归遍历二叉树的接口函数 void InorderTraverse (void (*visit)(const ElemType &); /中序非递归遍历二叉树的接口函数 void InorderTraverseNonRecursive (void (*visit)(const ElemType &); /后序递归遍历二叉树的接口函数 void PostorderTraverse (void (*visit)(const ElemType &); /后序非递归遍历二

16、叉树的接口函数 void PostorderTraverseNonRecursive (void (*visit)(const ElemType &); /层次遍历二叉树 void LevelTraverse (void (*visit)(const ElemType &e); .4.2.6 二叉树的递归遍历 问题的提出 顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。 “访问”的含义可以很广，如：输出结点的信息等。 “遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性

17、结构，每个结点有两个后继， 则存在如何遍历即按什么样的搜索路径遍历的问题。 4.2.6 二叉树的递归遍历 从下图中可以看到，二叉树是由根结点（D）、左子树（L）及右子树（R）三部分组成。 由这三部分的组合可得到以下的搜索路径：DLR、LDR、LRD、DRL、RDL、RLD。 其中，先左后右的搜索方式是最常用的遍历二叉树的方法。 4.2.6 二叉树的递归遍历 先序遍历二叉树（DLR ） 若二叉树为空树，则空操作；否则， 访问根结点 先序遍历左子树 先序遍历右子树。 先序遍历右图得到: a b d e g h c f4.2.6 二叉树的递归遍历/先序递归遍历二叉树 template void Bi

18、naryTree :_PreorderTraverse (BTNode*T, void(*visit)(const ElemType &e) if(T) visit(T-data); _PreorderTraverse(T-lchild,visit); _PreorderTraverse(Tt-rchild,visit); /先序递归遍历二叉树的接口函数 template void BinaryTree :PreorderTraverse( void (*visit)(const ElemType &e) _PreorderTraverse(m_root, visit); 4.

19、2.6 二叉树的递归遍历 中序遍历二叉树（LDR ） 若二叉树为空树，则空操作；否则， 中序遍历左子树 访问根结点 中序遍历右子树。 中序遍历右图得到: d b g h e a f c4.2.6 二叉树的递归遍历 后序遍历二叉树（LRD ） 若二叉树为空树，则空操作；否则， 后序遍历左子树 后序遍历右子树 访问根结点 后序遍历右图得到: d h g e b f c a4.2.7 几个二叉树基本操作的例子 建立二叉树 对前页所示的二叉树进行先序遍历，得到一个变通的遍历结果： a b d # # e g # h # # # c f # # # 建立二叉链表的存储结构，利用先序遍历思想，以变通的遍历

20、结果作为输入数据，执行以下操作： 若当前输入数据为特殊字符，则当前二叉树根结点为空，否则： 1. 生成根结点，当前数据写入根结点数据域 2. 建立左子树 3.建立右子树 4.2.7 几个二叉树基本操作的例子 建立二叉树/按先序次序输入结点值的方式建立二叉树T template void BinaryTree:_Create1(BTNode * &T, ElemType ch,const ElemType &c,int &i) if(chi=c) /c为特殊数据(如#)用以标示空指针 T=NULL; else T=new BTNode; T-data=chi; _Crea

21、te1(T-lchild,ch,c,+i); _Create1(T-rchild,ch,c,+i); 4.2.7 几个二叉树基本操作的例子 销毁二叉树 如果二叉树为空则结束，否则： （1）销毁左子树。 （2）销毁右子树。 （3）释放根结点。 显然，这是一个递归的过程，借助了后序遍历的思想4.2.7 几个二叉树基本操作的例子 销毁二叉树/销毁二叉链表形式的二叉树T template void BinaryTree:_Destroy(BTNode* &T) if(T) _Destroy(T-lchild); _Destroy(T-rchild); delete T; T=NULL; 4.2

22、.7 几个二叉树基本操作的例子 求二叉树深度的算法 如果二叉树为空则深度为0，否则： （1）求二叉树左子树的深度。 （2）求二叉树右子树的深度。 （3）二叉树的深度是左、右深度大的那棵子树的深度加1。这也是一个递归的过程，可借助后序遍历思想实现。4.2.7 几个二叉树基本操作的例子 求二叉树深度的算法/求二叉树的深度 template int BinaryTree:_Depth(BTNode* T) if(!T) return 0; int h1,h2; h1=_Depth(T-lchild); h2=_Depth(T-rchild); return h1h2?h1+1:h2+1; 4.2.8

23、 二叉树的非递归遍历 / 中序遍历二叉树的非递归算法(利用栈) template void BinaryTree :InorderTraverseNonRecursive ( void (*visit)(constElemType &e) stackBTNode * S; S.push(m_root); /根指针进栈 while(!S.empty() BTNode *p; p=S.top (); while(p) p=p-lchild; S.push(p); / 向左走到尽头 4.2.8 二叉树的非递归遍历 / 中序遍历二叉树的非递归算法(利用栈)（续） S.pop(); / 空指针退

24、栈 if(!S.empty() / 访问结点,向右一步 p=S.top (); S.pop(); visit(p-data); S.push(p-rchild); 中序非递归遍历二叉树时栈的变化示例 4.2.8 二叉树的非递归遍历 / 层次遍历二叉树的非递归算法(利用队列) template void BinaryTree :LevelTraverse( void (*visit)(const ElemType &e) queueBTNode * Q; if(m_root) Q.push(m_root); / 根指针进队 while(!Q.empty() BTNode *p; p=Q.

25、front (); / 取队头指针 Q.pop ();/出队 visit(p-data); / 访问队头指针所指元素 if(p-lchild) Q.push (p-lchild); / 非空的左孩子指针进队 if(p-rchild) Q.push(p-rchild); / 非空的右孩子指针进队 4.2.9 其他部分成员函数的实现 /返回二叉树T中结点的左兄弟结点指针 template BTNode* BinaryTree :LeftSibling (BTNode *p) BTNode *father; father=Parent (p); if(father & father-rchi

26、ld=p ) return father-lchild; return NULL; 4.2.9 其他部分成员函数的实现 /返回二叉树T中元素值为e的结点的双亲结点指针 template BTNode* BinaryTree :_Parent(BTNode* T,BTNode* p) if(T=NULL | T=p) return NULL; if(T-lchild=p | T-rchild=p) return T; BTNode *q; q=_Parent (T-lchild, p); if(q) return q; q =_Parent (T-rchild,p); return q; 4.2

27、.9 其他部分成员函数的实现 /复制一棵子树 template BTNode* BinaryTree:_Copy( BTNode* T) if(T=NULL) return NULL; BTNode *p; p=new BTNode; p-data=T-data; p-lchild=_Copy(T-lchild); p-rchild=_Copy(T-rchild); return p; 4.2.9 其他部分成员函数的实现 / 设设置置条件插入条件插入 / 初始条件：二叉树m_T存在,e是m_T中某个结点,LR为0或1,以复制对象的方式获/ 得的非空二叉树s与m_T不相交且右子树为空。操作结果：

28、根据LR为0或1,插入s/ 为T中e结点的左或右子树 e结点的原有左或右子树则成为s的右子树 template bool BinaryTree:InsertChild(BTNode *p, const int &LR,BinaryTree &r) BTNode*q,*s; if(p) q=r.Root(); /取对象根结点指针 s=_Copy(q); /对象复制 4.2.9 其他部分成员函数的实现 / 设设置置条件插入条件插入（续）续） if (LR=0) s-rchild=p-lchild; p-lchild=s; else s-rchild=p-rchild; p-rchi

29、ld=s; return true; return false; 4.2.10 主函数 （演示二叉链表类部分基本操作的执行结果）4.2.11 线索二叉树 遍历二叉树的结果是，求得结点的一个线性序列。 先序序列: A B C D E F G H K 中序序列: B D C A H G K F E 后序序列: D C B H K G F E AABCDEFGHK4.2.11 线索二叉树 线索二叉树 在二叉树的结点中，为了遍历方便，可以加入按某种遍历的线性序中的“前驱”和“后继” 的指针，称作“线索” 包含 “线索” 的存储结构，称作 “线索链表”，与其相应的二叉树，称作 “线索二叉树” 对二叉树按

30、某种遍历次序使其变为线索二叉树的过程称作“线索化”4.2.11 线索二叉树 线索二叉树的约定 在二叉链表的结点中增加两个标志域ltag和rtag，并作如下规定： 若该结点的左子树不空，则lchild域的指针指向其左子树，且左标志域ltag的值为“Link”；否则，lchild域的指针指向其“前驱”，且左标志域ltag的值为“Thread” 若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域rtag的值为“Link”；否则，rchild域的指针指向其“后继”，且右标志域rtag的值为“Thread”6.3 遍历二叉树和线索二叉树 线索二叉树的类型描述enum PointerTa

31、g Link=0 ,Thread=1 ; template struct BiThrnode ElemType data; BiThrnode* Lchild; BiThrnode* Rchild; PointerTag Ltag, Rtag; ; 中序线索二叉树的结构010011110011头结点根结点ABCDE4.2.11 线索二叉树 由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。 线索二叉树中序遍历的关键问题 中序遍历的第一个结点 ? 左子树上处于“最左下”（没有左子树）的结点。 在中序线索化链表中结点的后继 ？ 若无右子树，则为后继线索所指结点；否则

32、为对其右子树进行中序遍历时访问的第一个结点。for (p = firstNode(T); p; p = Succ(p) Visit(p);4.2.11 线索二叉树 中序线索二叉树的遍历算法template void BinaryThrTree : Traverse_InOrderBiThrTree( void (*visit)(const ElemType &e) BiThrnode* p; p=m_T-lchild; / p指向根结点 while(p!=m_T) / 空树或遍历结束时,p=T while(p-ltag=Link) p=p-lchild; visit(p-data);

33、while(p-rtag=Thread&p-rchild!=m_T) p=p-rchild; visit(p-data); / 访问后继结点 p=p-rchild; 4.2.11 线索二叉树 建立线索链表的方法 在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。 遍历过程中，附设指针pre, 并始终保持指针pre指向当前访问的指针p所指结点的前驱。 若p结点没有左子树，则令其左指针指向它的前驱（pre所指结点）并将其左标志改为Thread（1）。 若pre结点没有右子树，则令它的右指针指向它的后继（p所指结点）并将其右标志改为Thread（1）。在访问

34、下一结点前pre=p；p再移至下一访问结点。 中序遍历进行中序线索化/ 中序线索化二叉树T,Thrt指向头结点,Ltag.Rtag初始值均为Link template void BinaryThrTree:_InOrderThreading( BiThrnode* &T) BiThrnode *pre； BiThrnode* Thrt=new BiThrnode; Thrt-Ltag=Link; / 建头结点 Thrt-Rtag=Thread; Thrt-Rchild=Thrt; / 右指针回指 中序遍历进行中序线索化/ 中序线索化二叉树T(续)/Thrt指向头结点,Ltag.Rtag

35、初始值均为Link if(!T) / 若二叉树空，则左指针回指 Thrt-Lchild=Thrt; else Thrt-Lchild=T; pre=Thrt; _Threading(T, pre); / 中序遍历的方式线索化二叉树 pre-Rchild=Thrt; pre-Rtag=Thread; / 最后一个结点线索化 Thrt-Rchild=pre; T=Thrt; 中序遍历进行中序线索化的算法/ 中序遍历的方式线索化二叉树p template void BinaryThrTree :_Threading(BiThrnode* &p, BiThrnode* &pre) if

36、(p) _Threading(p-Lchild, pre); / 递归左子树线索化 if(!p-Lchild) / 没有左孩子 p-Ltag=Thread; / 前驱线索 p-Lchild=pre; / 左孩子指针指向前驱 if(!pre-Rchild) / 前驱没有右孩子 pre-Rtag=Thread; / 后继线索 pre-Rchild=p; / 前驱右孩子指针指向后继(当前结点p) pre=p; / 保持pre指向p的前驱 _Threading(p-Rchild,pre); / 递归右子树线索化 4.3 树和森林的再讨论4.3.1 树的存储结构 树的链式存储结构 依据树的度设立指向孩子

37、结点的指针个数 依据结点的度设立指向孩子结点的指针个数 孩子-兄弟表示法（树的二叉链表结构） 二个链域分别指向该结点的第一个孩子和下一个兄弟。 特点：找孩子容易，找兄弟容易。同样适用于森林。/模板形式定义的结点结构template struct TreeNode ElemType data; TreeNode * firstchild; TreeNode * nextsibling; ； 孩子兄弟表示法例 acbdefgacbdefga bcd ef g 4.3.1 树的存储结构 静态树表包括：双亲表示法和孩子表示法 双亲表示法 所有的树中结点存储在一个地址连续的存储空间中，结点中除数据域外只

38、设一个指向双亲的游标。 结点的结构为： /模板形式定义的结点结构template struct PTNode ElemType data; / 结点的数据域 int parent; / 结点的双亲游标 ; 双亲表示法的结构 树的结构struct PTree PTNode nodesMAX _SIZE; int n, root; /n为 结点个数、root为根结点的位置） 树的双亲表示法例 4.3.1 树的存储结构 孩子表示法 实现：把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，n个结点有n个孩子链表；而n个头指针又组成一个线性表，为便于查找，用顺序存储。 特点：找孩子容

39、易，找双亲难。孩子表示法的结构 孩子的结点结构 头结点结构template Struct CTNode ElemType data; / 结点的数据域 CLinkList *firstchild;/ 结点的孩子链表指针域; struct CLinkList int child; CLinkList *next; 孩子表示法的结构 树的结构struct CTree CTNode nodesMAX _SIZE; int n, root; /n为 结点个数、root为根结点的位置） 孩子表示法例 abcdefhgiabcdefghi01726453812456873datafirstchild孩子双

40、亲链表表示法例 abcdefhgia-1b0c0d1e1f2g4h4i401726453812456871datafirstchildparent4.3.2 树和森林的遍历 树的遍历 先根(次序)遍历 若树不空，则先访问根结点，然后依次先根遍历各棵子树。 后根(次序)遍历 若树不空，则先依次后根遍历各棵子树，然后访问根结点。 按层次遍历 若树不空，则自上而下自左至右访问树中每个结点。树的遍历例 先根(次序)遍历: a b d e g h i c f 后根(次序)遍历: d g h i e b f c a 层次(次序)遍历: a b c d e f g h i4.3.2 树和森林的遍历森林由三部

41、分组成：1森林中第一棵树的根结点；2森林中第一棵树的子树森林；3森林中其它树构成的森林。4.3.2 树和森林的遍历 森林的先序遍历 若森林不空，则1. 访问森林中第一棵树的根结点；2. 先序遍历森林中第一棵树的子树森林；3. 先序遍历森林中（除第一棵树之外）其余树构成的森林。 即：依次从左至右对森林中的每一棵树进行先根遍历。4.3.2 树和森林的遍历 森林的中序遍历 若森林不空，则1. 中序遍历森林中第一棵树的子树森林；2. 访问森林中第一棵树的根结点；3. 中序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行后根遍历。森林的遍历例 先序遍历：A B C D

42、 E F G H I J 中序遍历：B C D A F E H J I G 当以二叉链表作树的存储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历的算法实现。 森林的先序和中序遍历即为其对应二叉树的先序和中序遍历ABCDEFGHIJABCDEFGHIJ树和二叉树遍历的对应关系 ？树二叉树森林先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历求树深度的算法/求树的深度template int Tree:Depth (Treenode * &T) int i,j; if( ! T) return 0; I = Depth (T-firstchild); J = Depth (T

43、-nextsibling); return i j ? i + 1 : j; 4.4 树型结构的应用 4.4.1 算术表达式求值 此应用中的算术表达式求值限于二元运算符。 表达式定义如下： 表达式=(操作数)+(运算符)+(操作数) 操作数=无符号整数 | 表达式 表达式可以有三种标识方法，设Exp=S1+OP+S2，则 OP+S1+S2为表达式的前缀表示法； S1+OP+S2为表达式的中缀表示法； S1+S2+OP为表达式的后缀表示法4.4.1 算术表达式求值 将表达式用一棵二叉树表示，则: 二叉树的先序遍历次序恰好为表达式的前缀表示（波兰式）。 二叉树的中序遍历次序恰好为表达式的中缀表示。

44、 二叉树的后序遍历次序恰好为表达式的后缀表示（逆波兰式）。4.4.1 算术表达式求值 由表达式的三种不同的标识方法，可得到以下结论： 操作数之间的相对次序不变。 运算符的相对次序不同。 中缀式丢失了括弧信息，致使运算的次序不确定。 前缀式的运算规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一最小表达式。 后缀式的运算规则为：运算符在式中出现的顺序恰为表达式的运算顺序；每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。 4.4.1 算术表达式求值 设BinaryExpTree是用二叉链表结构定义的表达式类，在建立了二叉算术表达式树后，类BinaryExpTree的求

45、值过程（成员函数_Evaluate）如下：/用后序遍历的方式对表达式树求值 int BinaryExpTree :_Evaluate(BTnode* &T) if(T) if(!T-Lchild & !T-Rchild ) return T-data 0; /字符型转换成整型 return _Opreate(_Evaluate(T-Lchild),T-data, _Evaluate(T-Rchild); return 0; 4.4.1 算术表达式求值 成员函数_Opreate过程如下：/ 字符theta决定a与b 执行何种运算 int BinaryExpTree:_Opreat

46、e(const int &a,const char &theta, const int &b) int c; switch (theta) case + : c = a + b; break; case - : c = a - b; break; case * : c= a * b; break; case/ : c = a / b; return c; 4.4.1 算术表达式求值 成员函数_ Create 过程如下：/已知二叉树的先序遍历次序及中序遍历次序，建立二叉树T 其中：ch1/为表达式的前缀表示，ch2为表达式的中缀表示，low、 high分别为中/缀次序的起

47、始位置和最终位置，本函数根据先序次序和中序次序的形成规/律，运用先序递归遍历的思想逐个为先序次序中的第k个元素（k的初值为0）/生成二叉链表中的结点。void BinaryExpTree : _Create (BTnode* &T,char ch1, char ch2,int low,int high,int &k) int i; if (low high) T = NULL; else T = new BTnode; T-data = ch1k; / 查找k在中序中的位置，从而划分D L R for(i=low;iLchild,ch1,ch2,low,i-1,k); / 建立

48、左子树建立左子树 _Create (T-Rchild,ch1,ch2,i+1,high,k); / 建立右子树建立右子树 4.4.1 算术表达式求值 完整的算术表达式求值类代码 4.4.2 树与等价问题 等价关系等价关系：若集合S中的关系R是自反的、对称的和可传递的，则称它是一个等价关系。 等价类等价类：设R是集合S的等价关系，对任意xS，由 x R = y | y S / x R y )给出的集合x RS称为由 xS 生成的一个R等价类。 若R是S上的一个等价关系，由R可以产生这个集合S的一个唯一的划分S1, S2, , Sn。这些集合互不相交，其并为S，则这些子集Si便称为S的R等价类。

49、等价类问题可描述为：假设集合S有n个元素，已知m个形如 (x, y)( x, yS )的等价偶对确定了等价关系R，求S的划分。 4.4.2 树与等价问题 求解等价类问题的算法如下： 令S中每个元素各自形成一个只含单个成员的子集，记作S1, S2, , Sn。 重复读入m个关系（偶对），对每个读入的偶对（x，y），判定x和y所属的子集，若这两个子集不相等，则合并它们并取代这两个子集。 当所有的m个关系处理完后，剩下的这些非空子集即为S的R等价类。求解等价类问题的示例 有一个集合S= a, b, c, d, e, f 初始时每个元素各自形成一个等价类：a、b、c、d、e、f。 设有等价关系R=(a

50、, c), (b, d), (a, f), (e, f）。 则当讨论完等关系R中的偶对后，集合中的元素形成二个等价类：a , c, e, f、b, d。 4.4.2 树与等价问题 由求解等价类问题的算法可知，划分等价类需对集合进行以下的几个基本操作： 构造只含一个元素的集合。 判定某个元素所在的子集。 合并两个互不相交的集合。 这些基本操作的实现当然需建立在存储结构的基础上，静态树表中的双亲表示法是一合适的选择。 / PTnode.hstruct PTnode char data; / 结点的数据域结点的数据域 int parent; / 结点的双亲游标结点的双亲游标; 4.4.2 树与等价问

51、题 用双亲表示法结构表示，求解等价类问题的C+类MEset可如下定义： /MEset.h#ifndef H_MEset_H#define H_MEset_H#include #include PTnode.husing namespace std; class MEsetpublic: / 构造函数：分配构造函数：分配m个存储单元的顺序空间个存储单元的顺序空间 MEset(int n):m_len(0),m_size(n) m_nodes = new PTnoden; 4.4.2 树与等价问题 C+类MEset定义（续）： /析构函数：释放空间析构函数：释放空间 MEset() delete

52、m_nodes; bool Create( char , const int &); / 建立集合建立集合 void Display(); / 显示当前集合的状态显示当前集合的状态 int LocateElem( const char &);/ 查找元素在集合中的位置查找元素在集合中的位置 int FindRoot( const int &); / 查找元素所处集合的根查找元素所处集合的根 void Merge( const int &, const int &);/ 合并两个集合合并两个集合 void EffMerge( const int &

53、, const int &); / 高效合并两个集合高效合并两个集合 private: int m_len; int m_size; PTnode *m_nodes; 4.4.2 树与等价问题 构造函数为存储集合中的数据元素分配了m个（双亲表示法结点结构）存储单元的顺序空间。 4.4.2 树与等价问题 建立n个只含一个元素的等价类的过程（成员函数Create）/ 建立建立n个集合（初始时每一集合只有一个元素）个集合（初始时每一集合只有一个元素） bool MEset:Create( char ch, int const &n) int i = 0; if( n m_size)

54、return false; while ( i n) m_nodesi.data = chi; m_nodesi.parent = -1; i+; m_len = n; return true; 4.4.2 树与等价问题 建立n个等价类实际上是建立了含有n棵子树的森林，如下图所示。 4.4.2 树与等价问题 读入偶对(x, y)如何判定某个元素所在的子集（子树），又如何合并两个互不相交的子集（子树）？ 首先，分别查找元素x和y在数组中的位置（设x和y在数组中的位置分别是i和j）/ 查找元素查找元素e在集合中的位置在集合中的位置 int MEset:LocateElem(const char &

55、amp;e) int i=0; while ( i = m_len) return -1; return i; 4.4.2 树与等价问题 接着分别查找位序是i和j的数据元素所处子集（子树）的根 / 查找位序是查找位序是i的元素所处集合的根的元素所处集合的根 int MEset:FindRoot(const int &i) int k; for ( k = i; m_nodesk.parent = 0; k = m_nodesk.parent); return k; 4.4.2 树与等价问题 若元素x和y在集合中所处子集（子树）的根不同（i != j），则合并之。 / 合并根的位置是合并

56、根的位置是i和和j的两个集合的两个集合 void MEset:Merge( const int &i, const int &j) m_nodesi.parent = j; 4.4.2 树与等价问题 如偶对(a,c)中的数据元素a所属子集（子树）为0，数据元素c所属子集（子树）为2，如下图所示，则有：m_nodes0.parent=2。 4.4.2 树与等价问题 这种方法有可能出现单支树的情形，使得查找某一数据元素所处子集（子树）的根时，搜索长度达到最大如下图所示。 假设n个集合S1,S2,Sn, 每个子集只有一个元素Si = i ，用n棵只有一个根节点的树表示，则在做了n-1

57、次并操作后，最后得到的集合（树）深度平均为log n，最坏时为n。 4.4.2 树与等价问题 为确保集合（树）的深度任何情况下不超出log n，则需对合并方法进行改良 。/高效合并根的位置是高效合并根的位置是i和和j的两个集合的两个集合 void MEset:EffMerge(const int &i,const int &j) if (m_nodesi.parent m_nodesj.parent) m_nodesj.parent += m_nodesi.parent; m_nodesi.parent = j; else m_nodesi.parent += m_nodesj

58、.parent; m_nodesj.parent = i; 4.4.2 树与等价问题 下图是基于S= a, b, c, d, e, f ， R=(a,c),(b,d),(a,f),(e,f)，经高效合并后的结果示意图 4.4.2 树与等价问题 类MEset中的其他成员函数如下。 演示等价类合并过程的主函数/ 显示当前集合的状态显示当前集合的状态void MEset:Display() cout 位置位置 data parent endl; for (int i = 0; i m_len; i+) cout i m_nodesi.data m_nodesi.parent endl; 4.4.3

59、赫夫曼树及赫夫曼编码 结点的路径长度 从根结点到该结点的路径上分支的数目。 树的路径长度 树根到每个结点的路径长度之和。 结点的带权路径长度 从树根到该结点之间的路径长度与该结点上所带权值的乘积 树的带权路径长度 树中所有叶子结点的带权路径长度之和 设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi，则其中带权路径长度WPL最小的二叉树叫最优二叉树或者叫赫夫曼树。nkkklwTWPL1)(WPL计算例 4.4.3 赫夫曼树及赫夫曼编码 构造赫夫曼树的方法1. 根据给定的 n 个权值 w1, w2, , wn，构造 n 棵二叉树的集合 F = T1, T2, ,

60、Tn，其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树；2. 在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；3. 从F中删去这两棵树，同时加入刚生成的新树；4. 重复 2 和3 两步，直至 F 中只含一棵树为止。构造赫夫曼树过程例 a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118第1步第2步第3步第4步赫夫曼树存储 由于树中的结点数是确定的 ，选择静态三叉树表作为存储结构。 静态三叉树表结点结构 / HTnode.h/ 赫夫曼树节点结构赫夫曼树节点结构 struct HTnode char ch; int weight,parent,lchild,rchild; 赫夫曼树存储赫夫曼树存储4.4.3 赫夫曼树及赫夫曼编码 C+实现的HuffmanTree类定义 / 赫夫曼树类赫夫曼树类 class HuffmanTree / 将赫夫曼编码类作为赫夫曼类的友元类（后面用到