《数据结构PPT教学课件-第六章 树和二叉树》由会员分享，可在线阅读，更多相关《数据结构PPT教学课件-第六章 树和二叉树（125页珍藏版）》请在金锄头文库上搜索。
1、计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6引言：引言：树型结构是一类重要的树型结构是一类重要的非线性非线性结构。树型结构是结点之间有分结构。树型结构是结点之间有分支，且具有层次关系的结构，支，且具有层次关系的结构，非常类似于自然界中的树。非常类似
2、于自然界中的树。树结构在客观世界大量存在。例如家谱、树结构在客观世界大量存在。例如家谱、行政组织机构行政组织机构都可用都可用树形象地表示。树形象地表示。树在计算机领域中也有着广泛的应用：树在计算机领域中也有着广泛的应用：在编译程序中，用树来表示源程序的语法结构；在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在数据库系统中，可用树来组织信息；Windows操作系统中对磁盘文件的管理。操作系统中对磁盘文件的管理。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationSci
3、ence&TechnologyChap6教师教师学生学生其他人员其他人员20072007级级 20082008级级 20092009级级20102010级级南信大南信大数理院数理院计算机院计算机院语院语院叶子叶子根根子树子树计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6 第六章第六章 树和二叉树树和二叉树6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树6.36.3遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4
4、 6.4 树和森林树和森林6.6.5 5 哈夫曼树及应用哈夫曼树及应用计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6树的定义、术语、操作树的定义、术语、操作二叉树定义、性质、操作二叉树定义、性质、操作二叉树的存储结构二叉树的存储结构( (重点重点) )顺序存储、顺序存储、链接存储链接存储线索二叉树线索二叉树( (难点难点) )（特殊的链接存储结构）（特殊的链接存储结构）二叉树二叉树运算运算递归递归遍历遍历非递归非递归遍历遍历二叉树遍历二叉树遍历
5、( (重点重点) )二叉树二叉树其他运算其他运算树的存储结构树的存储结构森林与二叉树的转换森林与二叉树的转换树和森林的遍历树和森林的遍历二叉树二叉树应用应用哈夫曼树哈夫曼树及其应用及其应用( (重点、重点、难点难点) )内容及重、难点内容及重、难点6.16.26.26.36.36.46.5计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap66.1 6.1 树的定义与术语树的定义与术语一、树的定义一、树的定义 树是由树是由n(n 0)个结点组成的有限集
6、合。如果个结点组成的有限集合。如果n=0，称为，称为空树空树；如果；如果n0，则：，则： 有一个特定的有一个特定的元素元素称之为称之为根根(root)的结点，的结点， 除根以外的其他结点划分为除根以外的其他结点划分为m(m 0)个互不相交个互不相交的有限集合的有限集合T1,Tm，每个集合又是一棵树，并且称之，每个集合又是一棵树，并且称之为根的为根的子树子树(subTree)。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6A只有根结点的树只有根结
7、点的树ABCDEFGHIJKLM有子树的树有子树的树根根子树子树例：例：计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ACGBDEFKLHMIJ1）树中只有根结点没有前趋；）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径。）除根外的其他结点，都存在唯一条从根到该结点的路径。
8、( (非空非空) )树结构特点：树结构特点：计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素( (无后继无后继) )多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个
9、后继多个后继) )计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ABCDEFGHIJKLM树形表示树形表示( A( B(E(K,L), F ), C(G), D(H(M), I, J) )广义表广义表二、树的表示方法二、树的表示方法 I JFKLGMCCDBEA文氏图文氏图凹入表凹入表计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScien
10、ce&TechnologyChap6结点结点(node)结点的度结点的度(degree)结点的子树个数结点的子树个数分支分支(branch)结点结点度不为度不为0的结点的结点根根(root)即根结点即根结点(没有前驱没有前驱)叶叶(leaf)结点结点度为度为0的结点的结点孩子孩子(child)结点结点双亲双亲(parent)结点结点兄弟兄弟(sibling)结点结点具有同一双亲的结点具有同一双亲的结点三、树的基本术语三、树的基本术语ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0分支结点：分支结点：A,B,C,D,E,H叶结点：叶结点：K，L，
11、F，G，M，I，J结点结点A的孩子：的孩子：B，C，D结点结点B的孩子：的孩子：E，F结点结点I的双亲：的双亲：D结点结点L的双亲：的双亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6祖先祖先(ancestor)结点结点结点的祖先是从根到该结点所结点的祖先是从根到该结点所经分支上的所有结点经分支上的所有结点.子孙子孙(descendant)结点结点以某结点为根的子树中的任一以某结点为根
12、的子树中的任一结点都为该结点的子孙结点都为该结点的子孙.结点的层次结点的层次(level)根结点的层数为根结点的层数为1，其余结点，其余结点的层数为双亲结点的层数加的层数为双亲结点的层数加1树的高度树的高度(depth)树中结点的最大层数树中结点的最大层数树的度树的度(degree)树的基本术语树的基本术语( (续续) )ABCDEFGHIJKLM结点结点K的祖先：的祖先：A,B,E结点结点B的子孙：的子孙：E,F,K,L树的度：树的度：3树的高度：树的高度：4结点结点A的层次：的层次：1结点结点M的层次：的层次：4计算机与软件学院（计算机与软件学院（SchoolofComputerandSo
13、ftware）NanjingUniversityofInformationScience&TechnologyChap6n n 有序树有序树子树的次序不能互换子树的次序不能互换n无序树无序树子树的次序可以互换子树的次序可以互换n森林（森林（Forest）m棵互不相交的树的集合棵互不相交的树的集合基本术语（续）：基本术语（续）：计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6树的运算分树的运算分3 3大类：大类：第一类：第一类：查找类查找类遍历遍历
14、树中每个结点、求树的状态（如树高度、判树空）树中每个结点、求树的状态（如树高度、判树空）查找查找满足某种特定关系的结点满足某种特定关系的结点,如查找根结点等如查找根结点等第二类，第二类，插入类插入类包括初始化空树、构造树、在树的当前结点上插入一个新结包括初始化空树、构造树、在树的当前结点上插入一个新结点等；点等；第三类，第三类，删除类删除类包括清空树、销毁树、删除树中结点。包括清空树、销毁树、删除树中结点。四、树的基本操作（四、树的基本操作（P118P118）计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInf
15、ormationScience&TechnologyChap6五、树的抽象数据类型定义五、树的抽象数据类型定义ADTTree数据对象数据对象D：由由n个具有相同特性的元素构成的集合个具有相同特性的元素构成的集合数据关系数据关系R：若若D为空集，则称为空树为空集，则称为空树。否则否则:(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root;(2)当当n1时时,其余结点可分为其余结点可分为m(m0)个互不相交的有限集个互不相交的有限集T1,T2,Tm,其中每一棵子集本身又是一棵符合本定义的树其中每一棵子集本身又是一棵符合本定义的树,称为根称为根root的子树的子树.基本操作基
16、本操作P： Root(T)/求树的根结点求树的根结点Value(T,cur_e)/求当前结点的元素值求当前结点的元素值Parent(T,cur_e)/求当前结点的双亲结点求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子求当前结点的最左孩子CreateTree(&T,definition)/构造树构造树InitTree(&T)/初始化置空树初始化置空树计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6TreeEmpty(
17、T)/判定树是否为空树判定树是否为空树TreeDepth(T)/求树的深度求树的深度TraverseTree(T,Visit()/遍历遍历Assign(T,cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i,c)/将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树RightSibling(T,cur_e)/求当前结点的右兄弟求当前结点的右兄弟 ClearTree(&T)/清空树清空树DestroyTree(&T)/销毁树销毁树DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子树棵子树ADTTree计算机与软件
18、学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap66.2 6.2 二叉树二叉树6.2.1二叉树的定义二叉树的定义 二叉树或为空树，或是由一个根结点加上两棵分别称为二叉树或为空树，或是由一个根结点加上两棵分别称为左子树左子树和和右子树右子树的、的、互不相交的互不相交的二叉树组成。二叉树组成。ABCDEFGHK根结点左子树右子树说明说明（1）二叉树中每个结点最多有两棵子树；二叉树每个）二叉树中每个结点最多有两棵子树；二叉树每个结点度小于等于结点度小于等于2；（2）
19、左、右子树不能颠倒）左、右子树不能颠倒有序树；有序树；（3）二叉树是递归结构。）二叉树是递归结构。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6LRLR二叉树的五种基本形态二叉树的五种基本形态计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6问题：u1.只有两个结点的二叉树有几种不同的形态？2.只有
20、只有3个结点的二叉树有几种不同形态？分别画出来。个结点的二叉树有几种不同形态？分别画出来。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6二叉树的基本操作二叉树的基本操作查找类查找类插入类插入类删除类删除类 Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDep
21、th(T);PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit(); InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware
22、）NanjingUniversityofInformationScience&TechnologyChap6性质性质1若二叉树的层次从若二叉树的层次从1开始开始,则在二叉树的第则在二叉树的第i 层最多有层最多有2i-1 个结点。个结点。(i 1)证明用数学归纳法证明用数学归纳法性质性质2高度为高度为k 的二叉树最多有的二叉树最多有2k-1个结点。个结点。(k 1) 证明用求等比级数前证明用求等比级数前k k项和的公式项和的公式 2 20 0 + 2 + 21 1 + 2 + 22 2 + + 2 + + 2k-1k-1 = = 2 2k k-1-16.2.2二叉树的性质二叉树的性质计算机与软件
23、学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6性质性质3对任何一棵二叉树对任何一棵二叉树,如果其如果其叶结点叶结点有有n0个个,度为度为2的的非叶结点非叶结点有有n2个个,则有则有n0n21证明：证明：1、结点总数为度为、结点总数为度为0的结点加上度为的结点加上度为1的结点再加上度的结点再加上度为为2的结点：的结点：n=n0+n1+n22、另一方面，二叉树中、另一方面，二叉树中1度结点有一个孩子，度结点有一个孩子，2度结点度结点有二个孩子，根结点不是任何结
24、点的孩子，因此，结点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：总数为：n=n1+2n2+13、两式相减，得到：、两式相减，得到：n0=n2+1计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6定义定义1满二叉树满二叉树(FullBinaryTree) 一棵深度为一棵深度为k且有且有2k-1个结点的二叉树个结点的二叉树。定义定义2完全二叉树完全二叉树(CompleteBinaryTree) 若设二叉树的高度为若设二叉树的高度为h，则共有
25、，则共有h层。除第层。除第h层外，其它各层层外，其它各层(1 h-1)的结点数都达到最大个的结点数都达到最大个数，第数，第h层从左向右连续有若干结点，这就是完层从左向右连续有若干结点，这就是完全二叉树。全二叉树。定义两种特殊的二叉树：定义两种特殊的二叉树：计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6 A A G G F F E E D D C C B BK=3的满二叉树的满二叉树 A A C C B BK=2的满二叉树的满二叉树 A A E
26、E D D C C B B完全二叉树完全二叉树 A A G G F F E E D D C C B B计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6&完全二叉树的特点：完全二叉树的特点：（1）除最后一层外，每一层都取最大结点数，最后一）除最后一层外，每一层都取最大结点数，最后一层结点都有集中在该层最左边的若干位置。层结点都有集中在该层最左边的若干位置。（2）叶子结点只可能在层次最大的两层出现。）叶子结点只可能在层次最大的两层出现。（3）对任一结
27、点，若其右分支下的子孙的最大层次为）对任一结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次为，则其左分支下的子孙的最大层次为L或或L+1。&满二叉树的特点：满二叉树的特点：每一层都拥有最多结点数每一层都拥有最多结点数计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6思考：思考：满二叉树与完全二叉树的有何异同点？满二叉树与完全二叉树的有何异同点？满二叉树一定是一棵完全二叉树，反之满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是
28、一棵满二叉树。完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层，而满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面完全二叉树的叶子结点可以分布在最下面两层。两层。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap61231145891213671014151231145891267101234567123456计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）Nanjing
29、UniversityofInformationScience&TechnologyChap6性质性质4 具有具有n个结点的完全二叉树的高度个结点的完全二叉树的高度为为+1。证明：证明：设深度为设深度为k，根据二叉树性质，根据二叉树性质2知知：2k-1-1n2k-1，即即：2k-1n2k，于是有：于是有： 计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap61.当当i1,结点结点i为根结点，无双亲结为根结点，无双亲结点，否则其双亲为点，否则其双亲为;2
30、.若若2in,结点结点i无左子女无左子女;否则其左否则其左子女为子女为2i;3.若若2i1n,结点结点i无右子女无右子女;否则否则其右子女为其右子女为2i1。性质性质5 对具有对具有n个结点的完全二叉树进行编号（按层次从左到右）个结点的完全二叉树进行编号（按层次从左到右）编号可以反映二叉树结点之间的关系编号可以反映二叉树结点之间的关系。ii+12i2i12i22i3计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap612435689107111213
31、14151617例：例：(1)(1)i=8,i=8,其双亲为其双亲为4 4号结点。号结点。(2)(2)i=18i=18，则，则9 9号结号结点无左子女。点无左子女。i=14i=14，则，则7 7号结号结点的左子女为点的左子女为1414号结点。号结点。(3)(3)i=19i=19，则，则9 9号结号结点无右子女。点无右子女。i=15i=15，则，则7 7号结号结点的右子女为点的右子女为1515号结点。号结点。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyC
32、hap6顺序存储结构顺序存储结构链接存储结构链接存储结构二叉链表二叉链表三叉链表三叉链表6.2.3二叉树的存储二叉树的存储计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6一、顺序存储结构一、顺序存储结构 用一组用一组连续的连续的存储单元存储二叉树的结点数存储单元存储二叉树的结点数据。据。 要求：要求：必须把二叉树中的所有结点，按照一定的必须把二叉树中的所有结点，按照一定的次序排成为一个线性序列，结点在这个序列中的相次序排成为一个线性序列，结点在这
33、个序列中的相互位置能反映出结点之间的逻辑关系。互位置能反映出结点之间的逻辑关系。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6二叉树的顺序存储示例：二叉树的顺序存储示例：ABCABC12312345AB#C12345ABC123对于完全二叉树，结点的层次序列反映了整个二叉树的结构。对于完全二叉树，结点的层次序列反映了整个二叉树的结构。对于一般二叉树，则要通过添加对于一般二叉树，则要通过添加虚结点虚结点将其扩充为完全二叉树。将其扩充为完全二叉树。
34、计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap61A2B3C4#5D6E7F8#9#10G11H二叉树的顺序存储示例：二叉树的顺序存储示例：计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6思考：思考：对如下一棵二叉树采用顺序存储结构，需要添加对如下一棵二叉树采用顺序存储结构，需要添加几个空结点几个空
35、结点?计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6小结：小结：对于完全二叉树对于完全二叉树：结点编号完全可反映出该二叉树中结点之间的逻辑关结点编号完全可反映出该二叉树中结点之间的逻辑关系，可将此类二叉树中结点的编号与数组下标建立一系，可将此类二叉树中结点的编号与数组下标建立一一对应关系，所以采用顺序存储结构较好。一对应关系，所以采用顺序存储结构较好。对于一般的二叉树对于一般的二叉树：需要添加需要添加“虚虚”结点，使之成为一棵完全二叉树，此结点
36、，使之成为一棵完全二叉树，此时仍可用顺序存储结构表示这棵二叉树。时仍可用顺序存储结构表示这棵二叉树。但这样可能造成空间浪费，但这样可能造成空间浪费，最坏情况最坏情况是：深度为是：深度为k且只且只有有k个结点的单支树，需要长度为个结点的单支树，需要长度为2k1的空间。的空间。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ABCDFEGH二、二、二叉树的链式存储结构二叉树的链式存储结构结点结构的设计结点结构的设计二叉链表结点结构二叉链表结点结构三叉
37、链表结点结构三叉链表结点结构计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6二叉链表二叉链表typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;/左右孩子指针左右孩子指针BiTNode,*BiTree; lchild data rchild ABCDEFG在在n个结点的二叉链表中，有个结点的二叉链表中，有n+1个空指针域个空指针域 AB C D E F G空指针个数：空指针
38、个数：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+1结点包含三个域：数据域、左指针域、右指针域结点包含三个域：数据域、左指针域、右指针域 计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6三叉链表三叉链表typedefstruct BiTNode TElemTypedata;structBiTNode*lchild,*rchild,*parent; BiTNode,*BiTree;lchild data
39、parent rchildABCDEFG A B C D E F G结点包含四个域：数据域、双亲指针域、左指针域、右指针域结点包含四个域：数据域、双亲指针域、左指针域、右指针域计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap66.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树遍历定义遍历定义： 指按照某种顺序访问二叉树中的每个结指按照某种顺序访问二叉树中的每个结点，并且使每个结点被访问一次且仅一次。点，并且使每个结点被访问一次且仅一次。6
40、.3.1遍历二叉树遍历二叉树n遍历操作使非线性结构线性化遍历操作使非线性结构线性化。 计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6遍历的顺序遍历的顺序RT、L、R分别代表访问根结点、遍历左子树、遍历右分别代表访问根结点、遍历左子树、遍历右子树子树R遍历方式有遍历方式有6种：种：RTLR、TRL、LTR、RTL、LRT、RLT。TLR（先序遍历）（先序遍历）;LTR（中序遍历）（中序遍历）;LRT（后序遍历）（后序遍历）; 按深度遍历按深度遍历
41、 按广度遍历按广度遍历( (层序遍历层序遍历) )：从上到下、从左到右。：从上到下、从左到右。 计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ADBCTLRATLRTLRBDCTLR先序遍历序列：先序遍历序列：ABDC先序遍历先序遍历: :先序遍历（先序遍历（TLR）若二叉树非空若二叉树非空（1）访问根结点）访问根结点（2）先序遍历左子树）先序遍历左子树（3）先序遍历右子树）先序遍历右子树计算机与软件学院（计算机与软件学院（SchoolofCo
42、mputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ADBCLTRBLTRLTRADCLTR中序遍历序列：中序遍历序列：BDAC中序遍历（中序遍历（LTR）若二叉树非空若二叉树非空（1）中序遍历左子树）中序遍历左子树（2）访问根结点）访问根结点（3）中序遍历右子树）中序遍历右子树中序遍历中序遍历: :计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ADBCL
43、RTLRTLRTADCLRT后序遍历序列：后序遍历序列：DBCAB后序遍历（后序遍历（LRT）若二叉树非空若二叉树非空（1）后序遍历左子树）后序遍历左子树（2）后序遍历右子树）后序遍历右子树（3）访问根结点）访问根结点后序遍历后序遍历: :计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6先序：先序：a * bc def中序：中序：ab*cdef后序：后序：abcd * ef计算机与软件学院（计算机与软件学院（SchoolofComputerand
44、Software）NanjingUniversityofInformationScience&TechnologyChap6( (一一) )二叉树遍历的递归算法二叉树遍历的递归算法先序遍历的定义等价于：先序遍历的定义等价于：若二叉树为空，结束若二叉树为空，结束 基本项基本项（终止条件）（终止条件）若二叉树非空若二叉树非空 递归项递归项 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右子树；1、先序遍历递归算法、先序遍历递归算法(采用二叉链表采用二叉链表)StatusPreOrderTraverse(BiTreeT,Statu
45、s(*visit)(TElemTypee) /*功能功能:先序遍历二叉树先序遍历二叉树;参数参数:T为二叉树的根为二叉树的根,visit为对结点的为对结点的处理处理方法方法*/ if(T)/若根结点不空若根结点不空if(visit(T-data)/访问根结点访问根结点if(PreOrderTraverse(T-lchild,visit)/先序遍历根的左子树先序遍历根的左子树if(PreOrderTraverse(T-rchild,visit)/先序遍历根的右子树先序遍历根的右子树returnOK; 主程序主程序Pre(T)返回返回返回返回pre(T R);返回返回返回返回pre(T R);AC
46、BDTBvisit(B);pre(T L);BTAvisit(A);pre(T L);ATDvisit(D);pre(T L);DTCvisit(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：ABDC计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6BACEDGF先序遍历序列：先序遍历序列： A
47、B DEG C FABDEGCF递归调用递归调用返回返回计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap62、中序遍历递归算法、中序遍历递归算法StatusInOrderTraverse(BiTreeT,Status(*visit)(TElemTypee)/*功能功能:中序遍历二叉树中序遍历二叉树;参数参数:T为二叉树的根为二叉树的根,visit为对结点的处理方法为对结点的处理方法*/ if(T)/若根结点不空若根结点不空if(InOrderTra
48、verse(T-lchild,visit)/中序遍历根结点的左子树中序遍历根结点的左子树if(visit(T-data)/访问根结点访问根结点if(InOrderTraverse(T-rchild,visit)/中序遍历根结点的右子树中序遍历根结点的右子树returnOK;计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap63、后序遍历递归算法、后序遍历递归算法StatusPostOrderTraverse(BiTreeT,Status(*visit
49、)(TElemTypee)/*功能功能:后序遍历二叉树后序遍历二叉树;参数参数:T为二叉树的根为二叉树的根,visit为对结点的处理方法为对结点的处理方法*/if(T)/若根结点不空若根结点不空if(PostOrderTraverse(T-lchild,visit)/后序遍历根结点的左子树后序遍历根结点的左子树if(PostOrderTraverse(T-rchild,visit)/后序遍历根结点的右子树后序遍历根结点的右子树if(visit(T-data)/访问根结点访问根结点returnOK; 计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）Na
50、njingUniversityofInformationScience&TechnologyChap6( (二二) ) 二叉树遍历的非递归算法二叉树遍历的非递归算法 递归算法逻辑清晰、易懂；递归算法逻辑清晰、易懂； 但但在在实实现现时时，由由于于函函数数调调用用栈栈层层层层叠叠加加，效效率不高，而采用非递归算法可提高效率。率不高，而采用非递归算法可提高效率。 计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6T: AT: BT: ET: G栈在先序
51、遍历中的作用栈在先序遍历中的作用BACEDGFT先序遍历序列： A B DEGn栈用于栈用于存放已处理的根结点，以备在处理完该存放已处理的根结点，以备在处理完该结点的左子树后再处理其右子树结点的左子树后再处理其右子树计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6前序前序遍历遍历的的非递归非递归算法基本思路：算法基本思路：1)1)、访问当前、访问当前结点（初始时是根结点）结点（初始时是根结点）2 2) )、结点、结点进栈，沿左指针查找左进栈，沿左
52、指针查找左孩孩子。子。3 3) )、若有左、若有左孩孩子，转第子，转第1 1步。步。4 4) )、若无左、若无左孩孩子，判栈空？空则结束。非空，子，判栈空？空则结束。非空，栈顶结点出栈栈顶结点出栈, ,转向右子树，转第转向右子树，转第1 1步。步。1 1、前序遍历的非递归算法、前序遍历的非递归算法计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap61 1、前序遍历的非递归算法前序遍历的非递归算法 使用一个使用一个栈栈S S，存放已处理的根结点，以备在
53、处理完该结点的左子树后再处理存放已处理的根结点，以备在处理完该结点的左子树后再处理其右子树。初始，栈为空。其右子树。初始，栈为空。StatusPreOrderTraverse(BiTreeT,Status(*visit)(TElemTypee)/*功能功能:前序遍历二叉树前序遍历二叉树;参数参数:T为二叉树的根为二叉树的根,visit为对结点的处理方法为对结点的处理方法*/P=T;InitStack(S);/初始化栈初始化栈while(p|(!StackEmpty(S)/二叉树未处理完二叉树未处理完if(p)/当前未遇空结点当前未遇空结点if(!visit(p-data)/访问当前子树根结点访
54、问当前子树根结点returnERROR;/访问当前子树根结点时出错访问当前子树根结点时出错push(S,p);/结点压栈结点压栈p=p-lchild;/继续向左子树前进继续向左子树前进elsepop(S,p);p=p-rchild;/弹出栈顶结点，处理其右子树弹出栈顶结点，处理其右子树returnOK;计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ABCDE处理的数据项处理的数据项栈栈S中内容中内容p的指向的指向空空AAABBABCCABCAB
55、ADDADAEEAEA空空p计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6BACEDGFTT: AT: BT: ET: G栈在中序遍历中的作用栈在中序遍历中的作用中序遍历序列：D B Gn栈用于保存当前结点的祖先结点栈用于保存当前结点的祖先结点计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap62 2
56、、中序遍历的非递归算法、中序遍历的非递归算法StatusInorderTraverse(BiTreeT,Status(*visit)(TElemTypee)InitStack(S);p=T;while(p|!StackEmpty(S)if(p)/未到达左子树末端未到达左子树末端Push(S,p);/当前结点压栈当前结点压栈p=p-lchild;/继续向左子树前进继续向左子树前进else/已达到左子树末端已达到左子树末端Pop(S,p);/弹出栈顶弹出栈顶if(!visit(p-data)returnERROR;/处理该结点处理该结点p=p-rchild;/向右子树前进向右子树前进returnO
57、K;计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ABCDE分析分析: : 对左图所示的二叉树执行中序遍历的非递对左图所示的二叉树执行中序遍历的非递归算法归算法, ,执行过程中栈、指针的变化情况执行过程中栈、指针的变化情况. .计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap63 3、后序遍历的非递
58、归算法、后序遍历的非递归算法 遇遇到到一一个个结结点点，将将它它压压入入栈栈中中，然然后后去去遍遍历历它它的的左左子子树树；遍遍历历完完左左子子树树后后，还还不不能能立立即即访访问问该该结结点点，而而是是要要根根据据其其右右指指针针指指示示的的结结点点去去遍遍历历该该结结点点的的右右子子树树。遍遍历历完完右右子子树树后后才才能能从从栈栈顶顶弹弹出出该该结结点点。为为此此，需需给给栈栈中中每每个个元元素素加上一个加上一个特征位特征位，以示区别：，以示区别：特特征征位位为为L，表表示示已已进进入入该该结结点点的的左左子子树树，将将从从左左边边回来；回来；特特征征位位为为R，表表示示已已进进入入该该
59、结结点点的的右右子子树树，将将从从右右边边回来回来.计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6有关的说明：有关的说明：typedefenumL,RTag;typedefstructBiTNode/二叉树结点类型定义二叉树结点类型定义TElemTypedata;Tagtag;structBiTNode*lchild,*rchild;BiTNode,*BiTree;lchilddatarchildTag 计算机与软件学院（计算机与软件学院（Sc
60、hoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6后序遍历的非递归算法后序遍历的非递归算法StatusPostorderTraverse(BiTreeT,Status(*visit)(TElemTypee)if(T)InitStack(S);p=T;push(S,NULL);/初始栈底放一空指针初始栈底放一空指针while(p|!StackEmpty(S)while(!p)p-tag=L;Push(S,p);/进入左子树，赋左标志，入栈进入左子树，赋左标志，入栈p=p-lchild;/左
61、子树已走到尽头左子树已走到尽头Pop(S,p);/从栈顶弹出一个结点从栈顶弹出一个结点while(p&(p-tag=R)/从右子树回来从右子树回来if(!visit(p-data)returnERROR;Pop(S,p);if(p)/从左子树回来从左子树回来p-tag=R;Push(S,p);p=p-rchild;returnOK;elsereturnERROR;计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ABCDE处理的数据项处理的数据项栈
62、栈S中内容中内容p的指向的指向tag空空ALALBLALBLCLALBLCL(C(C左左) ) ALBLCLALBLCR(C(C右右) )ALBLCRCALBLALBRDLALBRDLALBRDLALBRDRELALBRDRELALBRDRELALBRDRERp计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ABCDE处理的数据项处理的数据项栈栈S中内容中内容p的指向的指向tagALBRDREREALBRDR DALBRB空空ALAR空空ARA空
63、空计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6三、按层次遍历二叉树三、按层次遍历二叉树层序遍历层序遍历按自上而下，每层从按自上而下，每层从左到右顺序访问结点。左到右顺序访问结点。例如：例如：- -+/a*e fb- - c d 计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6层序遍历层序遍历先根
64、，后子树；先左子树，后右子树先根，后子树；先左子树，后右子树队列队列队头队头树根结点树根结点A入队入队层序层序遍历序列遍历序列:E EGFCDAB计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6层序遍历层序遍历E EGFCDAB队列队列队头队头A层序层序遍历序列遍历序列:A出队出队计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&
65、TechnologyChap6层序遍历层序遍历队列队列队头队头根结点B、C入队A的子树E EGFCDABA层序层序遍历序列: A计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6StatusCreateBiTree(BiTree&T)ch=getchar();if(ch=#)T=NULL;elseif(!(T=(BiTree)malloc(sizeof(BiNode)exitOVERFLOW;T-data=ch;CreateBiTree(T-lch
66、ild);CreateBiTree(T-rchild);returnOK;/CreateBiTreeABCDFEG例如：建立如上二叉树的二叉链表结构应输入：例如：建立如上二叉树的二叉链表结构应输入： ABC#DE#G#F#建立二叉树建立二叉树创建二叉链表创建二叉链表（按先序序列建立二叉树）#计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6 D D A A B B C C E E F F T TvoidLeafNum(BiTreeT,int*n)/
67、采用二叉链表存储二叉树，采用二叉链表存储二叉树，n用于累加二叉树的叶子结点用于累加二叉树的叶子结点/的个数。本算法在先序遍历二叉树的过程中，统计叶子结点的个数的个数。本算法在先序遍历二叉树的过程中，统计叶子结点的个数if(T)if(T-lchild=NULL&T-rchild=NULL)(*n)+;LeafNum(T-lchild,n);LeafNum(T-rchild,n);例、例、编写编写求二叉树的叶子结点个数求二叉树的叶子结点个数的算法的算法输入：二叉树的二叉链表输入：二叉树的二叉链表结果：二叉树的叶子结点个数结果：二叉树的叶子结点个数二叉树的遍历应用举例二叉树的遍历应用举例计算机与软件
68、学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6intDepth(BiTreeT);/求二叉树的高度求二叉树的高度intd1,d2;if(!T)return0;elsed1=Depth(T-lchild);d2=Depth(T-rchild);returnmax(d1,d2)+1;例、例、编写编写求二叉树的高度求二叉树的高度的算法。的算法。输入：二叉树的二叉链表输入：二叉树的二叉链表输出：二叉树的高度输出：二叉树的高度二叉树的遍历应用举例二叉树的遍历应用举例
69、 D D A A B B C C E E F F T T计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap66.3.2线索二叉树线索二叉树1、什么是线索二叉树？、什么是线索二叉树？在存储结构中保存遍历所得在存储结构中保存遍历所得“前驱前驱”和和“后继后继”的信息的信息。线索二叉树概念线索二叉树概念:对二叉链表的结点增加两个标志域，并作如下规定对二叉链表的结点增加两个标志域，并作如下规定:若若该该结结点点的的左左子子树树不不空空，则则lchild域域的
70、的指指针针指指向向其其左左子子树树，且且左左标标志志域域的的值值为为0;否否则则，lchild域域的的指指针针指指向向其其“前前驱驱”，且且左左标标志志的值为的值为1.若该结点的右子树不空，则若该结点的右子树不空，则rchild域的指针指向其右子树，且域的指针指向其右子树，且右标志域的值为右标志域的值为0;否则，否则，rchild域的指针指向其域的指针指向其“后继后继”，且右标，且右标志的值为志的值为1.计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyCh
71、ap6线索二叉树的结点结构：线索二叉树的结点结构：lchildltagdatartagrchildltag=0/lchild域指示结点的左孩子域指示结点的左孩子1/lchild域指示结点的前驱域指示结点的前驱rtag=0/rlchild域指示结点的右孩子域指示结点的右孩子1/rchild域指示结点的后继域指示结点的后继计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ABCDE A B D C ET中序序列：中序序列：BCAED中序线索二叉树中序线
72、索二叉树0000111111 lchild ltag data rtag rchildtypedefenumLink,ThreadPointerTag;/Link：指针；指针；Thread：线索线索typedefstructBiThrNodeTElemTypedata;structBiThrNode*lchild,*rchild;PointerTagLtag,Rtag;BiThrNode,*BiThrTree；计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&Technolog
73、yChap6线索二叉树的生成算法线索二叉树的生成算法（算法算法6.6,见教材见教材P134）为方便添加结点的前驱或后继，需要设置两个指针：为方便添加结点的前驱或后继，需要设置两个指针：Thrt指针指针当前结点之指针；当前结点之指针；pre指针指针前驱结点之指针。前驱结点之指针。若若Thrt-lchildNULL,则则Thrt-Ltag=1;Thrt-lchildpre;/Thrt的前驱结点指针的前驱结点指针pre存入左空域存入左空域若若pre-rchildNULL,则则pre-Rtag1;pre-rchild=Thrt;/Thrt存入其前驱结点存入其前驱结点pre的右空域的右空域voidInT
74、hreading(BiThrTreeThrt,BiThrNode*&pre)/中序线索化二叉树中序线索化二叉树:递归中序遍历二叉树，并将其中序线索化，递归中序遍历二叉树，并将其中序线索化，Thrt指指/向头结点向头结点if(Thrt)InThreading(Thrt-lchild,pre);if(Thrt-lchild=NULL)Thrt-ltag=1;Thrt-lchild=pre;elseThrt-ltag=0;if(pre)if(pre-rchild=NULL)pre-rtag=1;pre-rchild=Thrt;elsepre-rtag=0;pre=Thrt;InThreading(T
75、hrt-rchild,pre);计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6算法算法遍历中序线索二叉树遍历中序线索二叉树在中序线索二叉树中找结点后继的方法：在中序线索二叉树中找结点后继的方法：（1）若）若rtag=Thread,则则rchild域直接指向其后继域直接指向其后继（2）若）若rtag=Link,则结点的后继应是其右子树的左链尾（则结点的后继应是其右子树的左链尾（ltag=Thread)的结点的结点在中序线索二叉树中找结点前驱的方法
76、：在中序线索二叉树中找结点前驱的方法：（1）若）若ltag=Thread,则则lchild域直接指向其前驱域直接指向其前驱（2）若）若ltag=Link,则结点的前驱应是其左子树的右链尾（则结点的前驱应是其左子树的右链尾（rtag=Thread)的结点的结点ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：中序序列：BCAED带头结点的中序线索二叉树带头结点的中序线索二叉树0 1计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&Technolo
77、gyChap6BiThrNode*find_succ(BiThrNode*p)/在中序线索树中找指定结点的后继结点，返回其指针在中序线索树中找指定结点的后继结点，返回其指针BiThrNode*q=p-rchild;if(!p-rtag)while(q-ltag=0)q=q-lchild;returnq;计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6voidInOrderThread(BiThrTreeThrt)/中序遍历以中序遍历以Thrt为根
78、的中序线索二叉树为根的中序线索二叉树BiThrTreep=Thrt;if(p)while(p-ltag=0)p=p-lchild;/找到最左下结点，即中序的第一个结点找到最左下结点，即中序的第一个结点printf(“%3c”,p-data);/访问该结点访问该结点while(p-rchild!=NULL)/反复执行在中序线索树中找指定反复执行在中序线索树中找指定结点的后继结点操作，访问相应结点结点的后继结点操作，访问相应结点p=find_succ(p);/找该结点的后继找该结点的后继printf(“%3c”,p-data);/访问其后继结点访问其后继结点中序线索二叉树的中序遍历算法中序线索二叉
79、树的中序遍历算法计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap66.4.1 6.4.1 树的存储结构树的存储结构 1 1、双亲表示法、双亲表示法( (顺序存储顺序存储) ) 采用一组连续空间存储树的结点采用一组连续空间存储树的结点, ,通通过保存每个结点的双亲结点的位置，表示过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。树中结点之间的结构关系。 I IA AC CB BH HG GF FE ED D -1-1 A 0 A 0 B 1
80、 B 1 C 1 C 1 D 2 D 2 E 2 E 2 F 3 F 3 G 5 G 5 H 5 H 5 I 5 I 50 01 12 23 34 45 56 67 78 89 9data parentdata parent 无双亲无双亲6.4树和森林树和森林计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6 A B C D E F G H I0 1 2 3 4 5 6 7 8 979823564datalink树的孩子链表图示树的孩子链表图示结点
81、的孩子结点结点的孩子结点链表链表(1) (1) 孩子链表：孩子链表：对树的每个结点用线性链表存储它的孩子结点。对树的每个结点用线性链表存储它的孩子结点。I IA AC CB BH HG GF FE ED D 找一个结点的孩子十分方便，找一个结点的孩子十分方便，但要找一个结点的双亲则要遍但要找一个结点的双亲则要遍历整个结构历整个结构 2 2、孩子表示法、孩子表示法通过保存每个结点的孩子结点的位置，通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。表示树中结点之间的结构关系。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUni
82、versityofInformationScience&TechnologyChap69 A 0 B 1 C 1 D 2 E 2 F3 G 5 H 5 I5 0 1 2 3 4 5 6 7 8 979823564data parent link带双亲的孩子链表带双亲的孩子链表结点的孩子结点结点的孩子结点链表链表(2) (2) 双亲孩子表示法：双亲孩子表示法：结合双亲表示法和孩子表示法结合双亲表示法和孩子表示法I IA AC CB BH HG GF FE ED D计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofIn
83、formationScience&TechnologyChap66.4.2 6.4.2 树与二叉树的转换树与二叉树的转换 二叉树与树都可用二叉链表存储，以二叉链表作中介，可导出树与二叉树与树都可用二叉链表存储，以二叉链表作中介，可导出树与二叉树之间的转换。二叉树之间的转换。 树与二叉树转换方法：树与二叉树转换方法：树根结点 X X 的第一个孩子结点 X X 紧邻的右兄弟二叉树根结点 X X 的左孩子结点 X X 的右孩子计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&Tech
84、nologyChap6I IA AC CB BD DH HG GF FE EF FI IA AB BD DH HG GC CE E树根结点 X X 的第一个孩子结点 X X 紧邻的右兄弟二叉树根结点 X X 的左孩子结点 X X 的右孩子例：例：计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6森林森林-树的集合树的集合 将森林转换为二叉树的将森林转换为二叉树的转换规则：转换规则：若若 F = T1F = T1，T2T2，T3T3，TnTn 是森林
85、，则是森林，则 B B（F F）=root,LB,RBroot,LB,RB （1 1）若）若 F F 为空，即为空，即 n=0n=0，则则 B(F)B(F)为空树。为空树。（2 2）若）若 F F 非空，则非空，则 B B（F F）的根是的根是T1T1的根，其左子树为的根，其左子树为LBLB，是从是从T1T1根结点的子树森林根结点的子树森林F1=T11F1=T11，T12T12，T1mT1m转换而成的二叉树；转换而成的二叉树；其右子树为其右子树为RBRB，是从除是从除T1T1外的森林外的森林F F=T2=T2，T3T3，TnTn 转换转换而成的二叉树；而成的二叉树；计算机与软件学院（计算机与软
86、件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6 J J A A L L K KI IH HG GF FE EA AC CB BD D包含3棵树的森林 B B C C D D E E F F G G H H I I J J K K L L F F D D C C A A B B E E G G H H I I J J K K L L每棵树对应的二叉树森林对应的二叉树计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUn
87、iversityofInformationScience&TechnologyChap66.4.3树和森林的遍历树和森林的遍历深度优先遍历深度优先遍历（1）先根次序遍历树）先根次序遍历树（2）后根次序遍历树）后根次序遍历树广度优先遍历树广度优先遍历树（按层次遍历树）（按层次遍历树）计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6树的遍历树的遍历I IA AC CB BH HG GF FE ED DK KL LM M1. 先根遍历：若树为空，则空操
88、作否则访问树的根结点依次先根遍历每棵子树2. 后根遍历：若树为空，则空操作否则依次后根遍历每棵子树访问树的根结点计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6树的遍历I IA AC CB BH HG GF FE ED DK KL LM MABDFCKLMEGHI树的先根树的先根遍历遍历：ABDEGHICFKLMABDEGHICFKLM树的后根遍历树的后根遍历：DGHIEBFCLMKADGHIEBFCLMKAv树的先根遍历等同于对转换所得的二叉树
89、进行先序遍历树的先根遍历等同于对转换所得的二叉树进行先序遍历v树的后根遍历等同于对转换所得的二叉树进行中序遍历树的后根遍历等同于对转换所得的二叉树进行中序遍历计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6层序遍历层序遍历ABCDEFGHIJ遍历序列：遍历序列：A，B，C，D，E，F，G，H，I，J计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformatio
90、nScience&TechnologyChap66.5赫夫曼树及应用赫夫曼树及应用1.什么是什么是Huffman树？树？2.建立建立Huffman树的算法树的算法Huffman算法算法（1）Huffman树的存储结构树的存储结构（2）算法描述）算法描述3.Huffman编码、编码、Huffman译码译码计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6引例编写程序将百分制表示的成绩编写程序将百分制表示的成绩score转换为等转换为等级分级分grad
91、e，规则为：规则为：grade=A:90score100grade=B:80score90grade=C:70score80grade=D:60score70grade=F:score60Score60? grade=FScore70? grade=DYNYScore80? grade=CNYScore90? grade=BNYNgrade=A转换转换n n个成绩的平均比较次数：个成绩的平均比较次数：3.15*n3.15*n0 - 5960 - 6970 - 7980 - 8990 - 1000.050.150.400.300.10分数比例FDCBA等级分转换转换n n个成绩的平均比较次数：个
92、成绩的平均比较次数：2.05*n2.05*n0 - 5960 - 6970 - 7980 - 8990 - 1000.050.150.400.300.10分数比例FDCBA等级分6060Score70?grade=C7070Score80? Y8080Score90?grade=BNScore60? grade=ANgrade=DYNgrade=FYNY转换转换n n个成绩的平均比较次数：个成绩的平均比较次数：2.2*n2.2*nScore70? grade=CScore80? YScore90? grade=BNYScore60? grade=ANYNgrade=FNYgrade=D0 -
93、5960 - 6970 - 7980 - 8990 - 1000.050.150.400.300.10分数比例FDCBA等级分计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6分数05960697079808990100比例数0.050.150.400.300.10（a）WPL=0.0510.1520.4030.3040.104=3.15对对10000个成绩，共需要个成绩，共需要31500次比较。次比较。（b）WPL=0.0540.1530.401
94、0.3020.104=2.05对对10000个成绩，共需要个成绩，共需要20500次比较。次比较。（c）WPL=0.0530.1530.4020.3020.102=2.20对对10000个成绩，共需要个成绩，共需要22000次比较。次比较。上述三个方案上述三个方案计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6一、一、 赫夫曼树赫夫曼树( (最优二叉树最优二叉树) )的概念的概念路径路径：从一个结点到另一个结点之间的若干个分支：从一个结点到另一个
95、结点之间的若干个分支.路径长度路径长度：路径上的分支数目称为路径长度：路径上的分支数目称为路径长度.结点的路径长度结点的路径长度：从根到该结点的路径长度：从根到该结点的路径长度.树的路径长度树的路径长度：树中所有叶子结点的路径长度之和；记为：树中所有叶子结点的路径长度之和；记为PL.在结点数相同的条件下，完全二叉树是路径最短的二叉树。在结点数相同的条件下，完全二叉树是路径最短的二叉树。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6结点的权结点的
96、权：根据应用的需要可以给树的结点赋权值；：根据应用的需要可以给树的结点赋权值；结点的带权路径长度结点的带权路径长度(WeightedPathLength,WPL)从根到该结点的路径长度与该结点权的乘积；从根到该结点的路径长度与该结点权的乘积；树的带权路径长度树的带权路径长度=树中所有叶子结点的带权路径之和；记作：树中所有叶子结点的带权路径之和；记作：示例示例赫夫曼树：赫夫曼树：设有设有n个权值个权值(w1,w2,wn)，构造有构造有n个叶子结点的严个叶子结点的严格二叉树，每个叶子结点有一个格二叉树，每个叶子结点有一个wi作为它的权值。则带权路径长度最小作为它的权值。则带权路径长度最小的严格二叉
97、树称为的严格二叉树称为哈夫曼树哈夫曼树。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6B BD DA AC CC C A AD D7 5 2 47 5 2 44 47 75 52 2A AC C D DB B4 47 75 52 2C CA A B BD D4 47 75 52 2B BWPL=7*2+5*2+2*2+4*2=36WPL=7*2+5*2+2*2+4*2=36WPL=7*1+5*2+2*3+4*3=35WPL=7*1+5*2+2*
98、3+4*3=35WPL=7*3+5*3+2*1+4*2=46WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35WPL=7*1+5*2+2*3+4*3=35计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap61初始化初始化:构造一个森林构造一个森林F=(T1,T2,Tn)，其中每棵二叉树，其中每棵二叉树Ti有有且仅有一个根结点，且仅有一个根结点，权值为权值为Wi；2在在F中选取两棵根结点权值最小的树中选取两棵根结点
99、权值最小的树Ti,Tj(权值分别为权值分别为Wi,Wj，并设，并设Wi=Wj)，分别作为左、右子树，生成一棵新二叉，分别作为左、右子树，生成一棵新二叉树树Tk，Tk根结点权根结点权Wk=Wi+Wj；3从从F中删除中删除Ti,Tj，同时将，同时将Tk加入加入F；4重复重复2、3，直到，直到F中只含一棵树为止；即为中只含一棵树为止；即为Huffman树。树。( (一一) ) 构造赫夫曼树的步骤：构造赫夫曼树的步骤：二、赫夫曼树的构造二、赫夫曼树的构造Huffman算法算法计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityo
100、fInformationScience&TechnologyChap6例：构造以例：构造以W=（2，4，5，7）为叶结点的赫夫曼树。为叶结点的赫夫曼树。7 72 2 4 45 5（）5 57 7）（6 6 2 2 4 45 56 6 2 2 4 47 7（）11115 56 6 2 2 4 47 7（）11111818计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6( (二二) ) 赫夫曼算法的实现：赫夫曼算法的实现：1 1、赫夫曼树的、赫夫曼树
101、的存储结构存储结构：当给定当给定n个叶结点构造赫夫曼树个叶结点构造赫夫曼树,共需要进行共需要进行n-1次合并次合并.每次合并都要产生一个新结点每次合并都要产生一个新结点。合并过程中共产生。合并过程中共产生n-1个新结点。故：赫夫曼树中个新结点。故：赫夫曼树中总结点数为总结点数为2n-1.如何设计赫夫曼树的存储结构？如何设计赫夫曼树的存储结构？将赫夫曼树中的将赫夫曼树中的2n-1个结点可以存储在一个大小为个结点可以存储在一个大小为2n-1的的数组中。数组中。顺序存储顺序存储结点结构定义：结点结构定义：typedefstructintweight;intparent,lchild,rchild;H
102、TNode,*HuffmanTree;计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6赫夫曼树的存储结构举例：设赫夫曼树的存储结构举例：设叶结点权叶结点权:2,4,5,7:2,4,5,7序号序号权值权值父母父母左孩子左孩子右孩子右孩子12345672000400050007000初初始始化化计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationSci
103、ence&TechnologyChap62 2、赫夫曼算法描述：、赫夫曼算法描述：算法的思想：算法的思想：（1）Huffman树初始化；树初始化；（2）i从从1开始循环开始循环n-1次：次：从序号从序号1当前结点当前结点(序号序号:n+i-1)中选取权值最小、中选取权值最小、且无父母结点且无父母结点(parent域为域为0)的两个结点，其序号的两个结点，其序号分别为分别为l,r;以以l,r分别为左、右子树的根生成一棵新的二叉树分别为左、右子树的根生成一棵新的二叉树,新树根结点存于序号为新树根结点存于序号为n+1位置位置,其权值其权值=左右子树左右子树根权之和根权之和.算法的输入与输出：算法的输
104、入与输出：(HuffmanTree&HT,intw,intn)Select(HuffmanTreeHT,intm,intl,intr)CreateBT(HuffmanTree&HT,intR,intl,intr)计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6Huffman算法：算法：voidHuffman(HuffmanTree&HT,intW,intn)/构造以数组构造以数组HT1.2n-1存储的存储的Huffman树，树，n个叶结点的权存储
105、于数个叶结点的权存储于数组组W中，中，n为叶结点数，为叶结点数，Huffman树的根存放于树的根存放于HT2n-1中中HT=(HuffmanTree)malloc(2*n+1)sizeof(HTNode);for(i=1;i=n;i+)/初始化初始化Huffman树树HTi.weight=Wi;HTi.parent=HTi.lchild=HTi.rchild=0;/逐步构造二叉树，构造逐步构造二叉树，构造HT数组后数组后n-1个元素的值个元素的值for(i=1;in;i+)/在在HT1n+i-1中找两个权值最小的元素中找两个权值最小的元素,其下标分别存于变量其下标分别存于变量l、r中中Sele
106、ct(HT,n+i-1,l,r);/生成新二叉树生成新二叉树,其根存于其根存于HTn+i,根的左右子女分别为根的左右子女分别为HTl、HTrCreateBT(HT,n+i,l,r);计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6Select（）（）函数函数voidSelect(HuffmanTreeHT,intm,int&l,int&r)l=r=0;m1=m2=infinity;/infinity是比所有权值都大的数是比所有权值都大的数for(
107、j=1;j=m;j+)if(HTj.parent=0)if(HTj.weightm1)m2=m1;r=l;m1=HTj.weight;l=j;elseif(HTj.weightm2)m2=HTj.weight;r=j:计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6CreateBT（）（）函数函数voidCreateBT(HuffmanTree&HT,intR,intl,intr)/在森林在森林HT中构造二叉树，根为中构造二叉树，根为HTR，左右
108、子女分别左右子女分别为为HTl和和HTrHTR.weight=HTl.weight+HTr.weight;HTR.parent=0;HTR.lchild=l;HTR.rchild=r;HTl.parent=R;HTr.parent=R;计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6哈夫曼树的构造过程举例：设哈夫曼树的构造过程举例：设叶结点权叶结点权:2,4,5,7:2,4,5,7序号序号权值权值父母父母左孩子左孩子右孩子右孩子123456720
109、00400050007000初初始始化化601255构造第一个构造第一个分支结点分支结点构造第二个构造第二个分支结点分支结点1103566构造第三个构造第三个分支结点分支结点1804677计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6三、赫夫曼编码三、赫夫曼编码&在远程通讯中，要将待传字符串转换成二进制的在远程通讯中，要将待传字符串转换成二进制的0、1序列。序列。&最简单的编码方式是采用最简单的编码方式是采用等长编码等长编码设要传送的字符为：设
110、要传送的字符为：ABACCDA若编码为：若编码为：A00 B01 C10 D11若将编码设计为长度不等的二进制编码，即让待传字符串若将编码设计为长度不等的二进制编码，即让待传字符串中中出现次数较多的字符采用尽可能短的编码出现次数较多的字符采用尽可能短的编码，则转换后的，则转换后的二进制编码串便可能缩短。二进制编码串便可能缩短。00010010101100计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6&设要传送的字符为：设要传送的字符为：ABAC
111、CDA&若编码为：若编码为：A0B00C1D-01关键关键：要设计长度不等的编码，则必须使任一字要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀，这种符的编码都不是另一个字符的编码的前缀，这种编码称之为编码称之为前缀编码前缀编码前缀编码前缀编码。 ABACCDA0000110100000AAAAABABB译码译码计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6如何设计前缀编码如何设计前缀编码?&设要传送的字符为：设要传送的
112、字符为：ABACCDA0110010101110ACBD000111采用二叉树设计采用二叉树设计二进制前缀编码二进制前缀编码左分支用左分支用“0”表示表示右分支用右分支用“1”表示表示可编码为：可编码为：A0B110C10D-111计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6译码过程译码过程：分解接收字符串：遇：分解接收字符串：遇“0”向左，遇向左，遇“1”向向右；一旦到达叶子结点，则译出一个字符，反复由根出右；一旦到达叶子结点，则译出一个字
113、符，反复由根出发，直到译码完成。发，直到译码完成。0110010101110ABACCDAACBD000111计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6 假设组成电文的字符集合假设组成电文的字符集合D=d1,d2,dn,每个字符每个字符di在在电文中出现的次数为电文中出现的次数为ci，对应的编码长度为对应的编码长度为li。因此，求电文的总长最短问题可转换为：因此，求电文的总长最短问题可转换为：如何得到电文总长最短的前缀编码？如何得到电文总长
114、最短的前缀编码？以以n n种字符出现的频率作为权值，设计一棵种字符出现的频率作为权值，设计一棵赫夫曼树赫夫曼树赫夫曼树赫夫曼树计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6设计示例设计示例：已知某系统在通讯时出现已知某系统在通讯时出现8种字符种字符,其频率为：其频率为：abcdefgh0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11试设计试设计Huffman编码。编码。a:0001b:10c:1110d:1111e
115、:110f:01g:0000h:00129148001111301235700001111abcdefgh计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6Huffman编码算法：编码算法：算法的思想：算法的思想：（1）以各字符出现频率为叶结点权值）以各字符出现频率为叶结点权值构造构造Huffman树树;（2）对每个叶结点执行：）对每个叶结点执行：由叶结点到根结点逆向求每个字由叶结点到根结点逆向求每个字符的符的Huffman编码编码.5900291
116、400710008100014120023130039001111008117115123419139829145104215116581521210001314权值权值父母父母左孩子左孩子 右孩子右孩子序序号号字字符符a1b2c3d4e5f6g7h8910111213141529148001111301235700001111abcdefgh9 9101011111212131314141 10 00 00 0所以：所以：a的编码为的编码为00018 819194242585829291515100100计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftwar
117、e）NanjingUniversityofInformationScience&TechnologyChap6哈夫曼编码的哈夫曼编码的存储结构存储结构：HC序号序号12345678 0001 1 10 1110 1111 110 HC0不用！不用！typedefchar*Huffmancode;voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intW,intn)存储准备存储准备Huffman(HT,W,n);创建创建Huffman树树对每个字符求其编码对每个字符求其编码HC空间申请空间申请;临时工作空间申请临时工作空间申请;for(i=1;i=n
118、;i+)在当前结点的在当前结点的parent域不为域不为0(未追溯到根未追溯到根)时时,循环执行循环执行:if(当前结点为其父母的左孩子当前结点为其父母的左孩子)则则编码编码=0;elseif(当前结点为其父母的右孩子当前结点为其父母的右孩子)则则编码编码=1;临时工作空间工作指针初始化临时工作空间工作指针初始化;将存在临时工作空间中的该字符的将存在临时工作空间中的该字符的huffman编码链入编码链入HCENDvoidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intW,intn)Huffman(HT,W,n);/创建创建Huffman树树/分配分
119、配n+1个字符编码的头指针向量个字符编码的头指针向量HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);/分配存放字符编码的临时工作空间分配存放字符编码的临时工作空间cdn-1=0;/字符串结束符字符串结束符HC空间申请空间申请;临时工作空间申请临时工作空间申请;for(i=1;i=n;i+)/逐个字符求逐个字符求Huffman编码编码start=n-1;/编码结束符位置编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶到根逆向求编码从叶到根逆
120、向求编码if(HTf.lchild=c)cd-start=0;elseif(HTf.rchild=c)cd-start=1;/为第为第i个字符分配编码存储空间个字符分配编码存储空间HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);在当前结点的在当前结点的parent域不为域不为0(未追溯到根未追溯到根)时时,循环执行循环执行:if(当前结点为其父母的左孩子当前结点为其父母的左孩子)则则编码编码=0;elseif(当前结点为其父母的右孩子当前结点为其父母的右孩子)则则编码编码=1;free(cd);/释放临时工作空间释放临时
121、工作空间计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6Huffman译码算法：译码算法：算法的思想：算法的思想：对对Huffman编码串每个符号的译码，都编码串每个符号的译码，都是从是从Huffman树的根结点向叶结点下行树的根结点向叶结点下行的过程：的过程：逢逢“0”向左孩子下行；向左孩子下行； 逢逢“1”向右孩子下行；向右孩子下行；当下行遇到叶结点时，该叶结点中当下行遇到叶结点时，该叶结点中的字符就是译码符号的字符就是译码符号.计算机与软件
122、学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap629148001111301235700001111abcdefgh设设Huffman编码为：编码为：0 0 0 1 1 1 1 0 1 1 1 1 0 0 10 0 0 1 1 1 1 0 1 1 1 1 0 0 1ac译码结果为：译码结果为：acdh举例：举例：StatusHuffmanDecoding(HuffmanCodeHC,HuffmanTreeHT,intn,char*HCode,HuffmanD
123、ecode&HD)/根据根据Huffman编码表编码表HC和对应的和对应的Huffman树树HT，将存储在，将存储在HCode中的中的Huffman编码编码进行解码，所得的字符存储于进行解码，所得的字符存储于HD中中*p=HCode;/Huffman编码串工作指针编码串工作指针HD=(char*)malloc(strlen(HCode)*sizeof(char);while(*p!=0)f=2*n-1;/从根出发进行匹配从根出发进行匹配while(HTf.lchild!=0&HTf.rchild!=0&*p!=0)/未到达叶端且编码串未处理完未到达叶端且编码串未处理完if(*p=0)f=HTf
124、.lchild;/向左孩子下行向左孩子下行elseif(*p=1)f=HTf.rchild;p+;/下一编码符号下一编码符号if(HTf.lchild=0&HTf.rchild=0)/下行遇叶结点下行遇叶结点HDi+=HC.charsf;/得到该编码的字符得到该编码的字符elsereturnERROR;/错误的编码，不能正确译码错误的编码，不能正确译码HDi=0;/译码字符串结束符译码字符串结束符returnOK;本章小结本章小结1.定义和性质定义和性质(递归特性、递归特性、5个性质个性质)2.存储结构存储结构3.遍历遍历4.线索化线索化顺序结构顺序结构链式结构链式结构二叉链表二叉链表三叉链表
125、三叉链表先序线索树先序线索树中序线索树中序线索树后序线索树后序线索树树树二叉树二叉树森林森林Huffman编码编码先先序序遍遍历历中中序序遍遍历历遍历遍历存储结构存储结构遍历遍历孩子孩子-兄弟兄弟先序遍历先序遍历 后序遍历后序遍历线索二叉树线索二叉树Huffman树树应应用用中序遍历中序遍历后序遍历后序遍历先序遍历先序遍历层次遍历层次遍历计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6 习题1、在在树树型型结结构构中中，树树根根结结点点没没有有_
126、结结点点，其其余余每每个个结结点点有有且且只只有有_个个前前驱驱结结点点；叶叶子子结结点点没没有有_结结点点，其其余余每每个个结点的后继结点可以有结点的后继结点可以有_。2、设设某某二二叉叉树树的的中中根根序序列列CBEDAGJIFH，后后根根序序列列为为CEDBJIGHFA，试试构构造造出出这这棵棵二二叉叉树树，画画出构造过程和所得到的二叉树。出构造过程和所得到的二叉树。3、若若一一棵棵树树中中度度为为的的结结点点有有n1个个，度度为为2的的结结点点有有n2个个，度度为为m的的结结点点有有nm个个,该该树树有有多多少少个个叶结点？叶结点？计算机与软件学院（计算机与软件学院（SchoolofC
127、omputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6 习题4、写一个递归函数计算二叉树的高度。写一个递归函数计算二叉树的高度。5、试试证证明明：在在二二叉叉链链表表中中，空空指指针针的的个个数数是是二二叉叉树的结点数加树的结点数加1。6、在在一一份份电电文文中中共共使使用用6 6种种字字符符：a,b,c,d,e,fa,b,c,d,e,f，它它们们的的出出现现频频率率依依次次是是4,9,11,18,7,24,9,11,18,7,2，试试画画出出对对应应的的赫赫夫夫曼曼树树（按按左左子子树树根根节节点点的的
128、权权小小于于等等于于右右子子树树根根节节点点的的权权的的次次序序构构造造），求求出出每每个个字字符符的的赫赫夫夫曼曼编编码码。若若接接收收端端收收到到的的电电文文编编码码为为1000100100011110110001001000111101，则则译译码码结结果果是是什什么么，为为什么？什么？ 计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6习题7、对如下的二叉链表进行中序线索化操作，画出添加线索后对如下的二叉链表进行中序线索化操作，画出添加线索后的线索树。的线索树。
