《自考数据结构导论02142第4章.ppt》由会员分享，可在线阅读，更多相关《自考数据结构导论02142第4章.ppt（68页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章4.1树的基本概念树的基本概念4.2二叉树二叉树4.3二叉树的存储结构二叉树的存储结构4.4二叉树的遍历二叉树的遍历4.5树和森林树和森林4.6哈夫曼树哈夫曼树1第四章第四章树树型型结构是一类重要的非线性结构。树型结构是结点之间有分支，结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中
2、，用树来表示树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。的行为时，可用树来描述其执行过程等等。4.1树的定义和基本术语树的定义和基本术语树树是是n(nn(n=0)=0)个结点的有限集个结点的有限集T T，满足：满足： (1)(1)有且仅有一个特定的称为有且仅有一个特定的称为根根的结点；的结点； (2)(2)其余的结点可分为其余的结点可分为m(m=0)m(m=0)个个互不相交互不相交的子集的子集 T T1 1,T,T2
3、 2,T,T3 3TTm m，其中每个子集其中每个子集T Ti i又是一棵树，又是一棵树， 并称其为并称其为子树子树。一、树的定义一、树的定义递归是树的固有特性递归是树的固有特性2第四章第四章二、树的逻辑表示二、树的逻辑表示一般表示法一般表示法(直观表示法直观表示法)：FCEGBDAb、嵌套括号法：嵌套括号法：(根根(子树子树,子树子树子树子树)(A(B(E,F),C,D(G)根根ABFCDGEc、凹入法表示：凹入法表示：另三种表示法另三种表示法a、文氏图法：文氏图法：BACDEFG第一层第一层第二层第二层第三层第三层3第四章第四章三、树的基本术语三、树的基本术语度度结点的度结点的度：该结点的
4、子树数（即分支数）。：该结点的子树数（即分支数）。树的度树的度：树中结点的度最大值。：树中结点的度最大值。结点结点由一个数据元素及若干指向其它结点的分支所组成。由一个数据元素及若干指向其它结点的分支所组成。叶子（终端结点）叶子（终端结点）度为零的结点。度为零的结点。孩子（子结点）孩子（子结点）结点的子树的根称为该结点的孩子。结点的子树的根称为该结点的孩子。双亲（父结点）双亲（父结点）一个结点称为该结点所有子树根的双亲。一个结点称为该结点所有子树根的双亲。非终端结点非终端结点度不为零的结点。度不为零的结点。祖先祖先结点祖先指根到此结点的一条路径上的所有结点。结点祖先指根到此结点的一条路径上的所有
5、结点。子孙子孙从某结点到叶结点的分支上的所有结点称为该结从某结点到叶结点的分支上的所有结点称为该结点的子孙。点的子孙。兄弟兄弟同一双亲的孩子之间互称兄弟。同一双亲的孩子之间互称兄弟。4第四章第四章结点的层次结点的层次从根算起，根为第一层，其孩子在第二层从根算起，根为第一层，其孩子在第二层,.，L层上任何结点的孩子都在层上任何结点的孩子都在L+1层上。层上。堂兄弟堂兄弟其双亲在同一层的结点。其双亲在同一层的结点。树的深度树的深度树中结点的最大层次。树中结点的最大层次。森林森林是是m（0）棵树的集合。棵树的集合。有序树有序树若树中各结点的子树从左到右是有次序的，若树中各结点的子树从左到右是有次序的
6、，不能互换，称为有序树。不能互换，称为有序树。无序树无序树若树中各结点的子树是无次序的，若树中各结点的子树是无次序的，可以互换，则成为无序树。可以互换，则成为无序树。5第四章第四章求根求根Root(T):求树求树T的根结点；的根结点；求双亲求双亲Parent(T,X):求结点求结点X在树在树T上的双亲；上的双亲；若若X是树是树T的根或的根或X不在不在T上，则结果为一特殊上，则结果为一特殊标志；标志；求孩子求孩子Child(T,X,i):求树求树T上结点上结点X的第的第i个孩子个孩子结点；若结点；若X不在不在T上或上或X没有第没有第i个孩子，则结果个孩子，则结果为一特殊标志；为一特殊标志；建树建
7、树Create(X,T1,Tk),k1:建立一棵以建立一棵以X为为根，以根，以T1,Tk为第为第1,k棵子树的树；棵子树的树；剪枝剪枝Delete(T,X,i):删除树删除树T上结点上结点X的第的第i棵子树；棵子树；若若T无第无第i棵子树，则为空操作；棵子树，则为空操作；遍历遍历TraverseTree(T):遍历树，即访问树中每遍历树，即访问树中每个结点，且每个结点仅被访问一次个结点，且每个结点仅被访问一次。四、树的基本操作四、树的基本操作6第四章第四章 二叉树在树结构的应用中起着非常重要的作用，因为二叉树有许多二叉树在树结构的应用中起着非常重要的作用，因为二叉树有许多良好的性质和简单的物理
8、表示，而任何树都可以与二叉树相互转换，这良好的性质和简单的物理表示，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。样就解决了树的存储结构及其运算中存在的复杂性。4.2二叉树二叉树1 1、定义：、定义： 二叉树二叉树是是n(n=0)n(n=0)个结点的有限集合，它或为空个结点的有限集合，它或为空(n=0)(n=0)，或是由一个或是由一个根结点根结点及及两棵两棵互不相交的互不相交的左、右左、右子树子树组成，且每棵子树都是二叉树。组成，且每棵子树都是二叉树。4.2.1 4.2.1 二叉树的基本概念二叉树的基本概念 这是一个这是一个递归递归定义。定义。二叉树可以是空集
9、合，二叉树可以是空集合，根可以有空的左子树根可以有空的左子树或空的右子树。或空的右子树。ABDCFGHE7第四章第四章2、特点：、特点：二叉树可以是空的，称二叉树可以是空的，称空二叉树空二叉树；每个结点每个结点最多最多只能有两个孩子；只能有两个孩子；子树有左、右之分且子树有左、右之分且次序不能颠倒次序不能颠倒。、二叉树与树的比较：、二叉树与树的比较：结结点点子子树树结点顺序结点顺序树树n0不定不定(有限有限)无无二叉树二叉树n02有有(左、右左、右) 8第四章第四章 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明
10、它是左子树，还是右子树。这是二叉树与树的最要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。下图列出主要的差别。下图列出二叉树的二叉树的5 5种基本形态种基本形态，图，图(C) (C) 和（和（d d）是不是不同的两棵二叉树。同的两棵二叉树。(a)空二叉树空二叉树A(b)根和空的根和空的左右子树左右子树A(c)根和左子树根和左子树A(d)根和右子树根和右子树A(e)根和左右子树根和左右子树二叉树的二叉树的5种形式种形式4.2.1 4.2.1 二叉树的定义二叉树的定义9第四章第四章初始化初始化Initiate(BT):建立一棵空二叉树，建立一棵空二叉树，BT= 。求双亲求双亲
11、Parent(BT,X):求出二叉树求出二叉树BT上结点上结点X的双亲结点，的双亲结点，若若X是是BT的根或的根或X根本不是根本不是BT上的结点，运算结果为上的结点，运算结果为NULL。求左孩子求左孩子Lchild(BT,X)和求右孩子和求右孩子Rchild(BT,X)：分别求分别求出二叉树出二叉树BT上结点上结点X的左、右孩子；若的左、右孩子；若X为为BT的叶子或的叶子或X补在补在BT上，运算结果为上，运算结果为NULL。建二叉树建二叉树Create(BT):建立一棵二叉树建立一棵二叉树BT。先序遍历先序遍历PreOrder(BT):按先序对二叉树按先序对二叉树BT进行遍历，每进行遍历，每个
12、结点被访问一次且仅被访问一次，若个结点被访问一次且仅被访问一次，若BT为空，则运算为空，则运算为空操作。为空操作。4、二叉树的基本操作（见、二叉树的基本操作（见P77）10第四章第四章中序遍历中序遍历InOrder(BT):按中序对二叉树按中序对二叉树BT进行进行遍历，每个结点被访问一次且仅被访问一次，遍历，每个结点被访问一次且仅被访问一次，若若BT为空，则运算为空操作。为空，则运算为空操作。后序遍历后序遍历PreOrder(BT):按后序对二叉树按后序对二叉树BT进进行遍历，每个结点被访问一次且仅被访问一次，行遍历，每个结点被访问一次且仅被访问一次，若若BT为空，则运算为空操作。为空，则运算
13、为空操作。层次遍历层次遍历LevelOrder(BT):按层从上往下，同一按层从上往下，同一层中结点按从左往右的顺序，对二叉树进行遍层中结点按从左往右的顺序，对二叉树进行遍历，每个结点被访问一次且仅被访问一次，若历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。为空，则运算为空操作。11第四章第四章1 1、性质、性质1 1： 在二叉树的第在二叉树的第i(ii(i=1)=1)层上至多有层上至多有2 2i-1i-1个个结点。结点。二叉树具有下列重要性质：二叉树具有下列重要性质：4.2.2 4.2.2 二叉树的性质二叉树的性质（）2 2、性质、性质2 2：深度为深度为k(kk(k=1
14、)=1)的二叉树至多有的二叉树至多有2 2k k1 1个个结点。结点。3 3、性质、性质3 3：对任何一棵二叉树，如果其终端结点对任何一棵二叉树，如果其终端结点 数为数为n n0 0，度为度为2 2的结点数为的结点数为n n2 2，则，则n n0 0n n2 21 1。即：即：叶结点数叶结点数n n0 0= =度为度为2 2的结点数的结点数n n2 2+1+112第四章第四章 满二叉树（满二叉树（结点数结点数=2=23 3-1=7-1=7）满二叉树中满二叉树中结点顺序编号结点顺序编号：即从第一层结点开始自上：即从第一层结点开始自上 而下，从左到右进行连续编号。而下，从左到右进行连续编号。满二叉
15、树满二叉树深度为深度为k(k=1)且有且有2 2k k-1-1个结点的二个结点的二叉树。叉树。4.2.2 4.2.2 二叉树的性质二叉树的性质123456713第四章第四章12345612345712367注：注：满二叉树是完全二叉树的特例。满二叉树是完全二叉树的特例。完全二叉树完全二叉树深度为深度为K K的二叉树中，的二叉树中，K-1K-1层结层结点数是满的点数是满的(2(2k-2k-2 ) )，K K层结点是左连续的层结点是左连续的( (即结点即结点编号是连续的编号是连续的) )。如下图（如下图（a a）4.2.2 4.2.2 二叉树的性质二叉树的性质(a)完全二叉树完全二叉树YES!(b
16、)非完全二叉树非完全二叉树NO!(c)非完全二叉树非完全二叉树NO!14第四章第四章 符号符号【x x】表示不大于表示不大于x x的最大整数。的最大整数。 假设此二叉树的深度假设此二叉树的深度为为k k，则根据性质则根据性质2 2及完全二叉及完全二叉树的定义得到：树的定义得到：2 2k-1k-11n=21n=2k k-1 -1 或或 2 2k-1k-1=n2=n2k k取对数得到：取对数得到：k k1log1log2 2nk n1i1，则，则i i的双亲的双亲Parent(AParent(A) )是结点是结点i/2i/2; ;（2 2）如果如果2*in2*in，则其则其左孩子是结点左孩子是结点
17、2*i2*i, , 否则，结点否则，结点i i无左孩子且为叶子结点；无左孩子且为叶子结点；（3 3）如果如果2*i2*i1n1n，则其则其右孩子是结点右孩子是结点2*i2*i1 1， 否则，结点否则，结点i i无右孩子。无右孩子。A1B2C3D4EF6H8IJ10G75916第四章第四章思考题思考题: :一棵完全二叉树一棵完全二叉树, ,结点总数结点总数n=980,n=980,问问: :该二叉树的深度该二叉树的深度=?=?最下层结点个数最下层结点个数=?=?度为度为1 1的结点个数的结点个数n n1 1=?=?叶结点个数叶结点个数n n0 0=?=?性质性质4 4性质性质2 2完全二叉树定义完
18、全二叉树定义性质性质3 3结点数最少结点数最少 个个? ?深度为深度为5 5的二叉树的二叉树结点数最多结点数最多 个个? ?结点数最少结点数最少 个个? ?深度为深度为5 5的完全二叉树的完全二叉树结点数最多结点数最多 个个? ?5 531311616313117第四章第四章1.树最适合用来表示树最适合用来表示()A.有序数据元素有序数据元素B.无序数据元素无序数据元素C.元素之间具有分支层次关系的数据元素之间具有分支层次关系的数据D.元素之间无联系的数据元素之间无联系的数据2.根据定义，树的叶子结点其度数（）根据定义，树的叶子结点其度数（）A.必大于必大于0B.必等于必等于0C.必等于必等于
19、1D.必等于必等于23.对一棵有对一棵有100个结点的完全二叉树按层序编号，则编号为个结点的完全二叉树按层序编号，则编号为49的结的结点，它的左孩子的编号为（点，它的左孩子的编号为（）A.99B.98C.97D.504.树形结构中，若结点有个兄弟，是的双亲，则的度为树形结构中，若结点有个兄弟，是的双亲，则的度为_。5.深度为深度为15的满二叉树上，第的满二叉树上，第11层有层有个结点。个结点。6.三个结点可构成三个结点可构成种不同形态的二叉树。种不同形态的二叉树。请你给出答案请你给出答案思考题思考题想一想想一想CAB4210=1024518第四章第四章 它是用一组连续的存储单元存储二叉树的数据
20、元素。因此，必须它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，可用编号的方法。相互位置能反映出结点之间的逻辑关系，可用编号的方法。二叉树的顺序存储结构二叉树的顺序存储结构即对二叉树按完全二即对二叉树按完全二叉树进行编号，然后用一维数组存储，其中叉树进行编号，然后用一维数组存储，其中编号编号为为i i的结点存储在数组中的结点存储在数组中下标为下标为i i的分量中。的分量中。 该方法称为该方法称为“以编号为地址以编号为地址”策略策略4
21、.3.1 4.3.1 二叉树的顺序存储结构二叉树的顺序存储结构4.3二叉树的存储结构二叉树的存储结构 从树根起，自上层至下层，每层自左至右的给所有结点编号缺点从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H H且只有且只有H H个结点的右单支树却需要个结点的右单支树却需要2 2h h-1-1个结点存储空间。而且，若经个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！常需要插入与删除树中结点时，顺序存储方式不是很好！19第四章第四章对于完全二
22、叉树来说，采用以编号作为数组的下边的方法将结点存入一位数组中，也就是将编号为i的结点存入一维数组的以i为下标的数组元素中。对于非完全二叉树，则用某种方法将其转化为完全二叉树，为此可增设若干个虚拟结点。lkjihgfedcba 1 2 3 4 5 6 7 8 9 10 11 12 abcdefghijkl123456789 1011120Btree：20第四章第四章lkjihgfedcba 1 2 3 4 5 6 7 8 9 10 11 12 此方法用于完全二叉树，则：此方法用于完全二叉树，则： 节省内存节省内存 结点位置确定方便结点位置确定方便abcdefghijkl21第四章第四章ABCDE
23、FG 表示该处没有元素存在表示该处没有元素存在ABCDEFG用于一般二叉树：用于一般二叉树：（浪费空间）（浪费空间）用于单分支二叉树则存储空间浪费极大。用于单分支二叉树则存储空间浪费极大。用于单分支二叉树则存储空间浪费极大。用于单分支二叉树则存储空间浪费极大。 1 2 3 4 5 6 7 8 9 10 11123456789101122第四章第四章lchilddatarchild结点形式：结点形式：左孩指针左孩指针指向其左孩结点；指向其左孩结点； 右孩指针右孩指针指向其右孩结点；指向其右孩结点；二叉链表类型定义二叉链表类型定义typedeftypedef structstruct btnode
24、btnode DatatypeDatatype data; data; structstruct btnodebtnode * *lchildlchild,*,*rchildrchild; ; * *BintreeBintree; ; ;二二叉链表类型叉链表类型4.3.2 4.3.2 二叉树的链式存储结构二叉树的链式存储结构二叉链表表示法：二叉链表表示法：23第四章第四章例：例：CABDEFGH三叉链表表示法：三叉链表表示法：lchilddataparentrchild结点形式：结点形式：指向双亲指向双亲4.3 4.3 二叉树的存储结构二叉树的存储结构ABDCFGHE二叉链表二叉链表T注：注：
25、在含在含n个结点的二叉链表中有个结点的二叉链表中有2n个指针域，其中个指针域，其中n-1个用来指向结点的左右孩子，其余个用来指向结点的左右孩子，其余n+1个空链域个空链域.24第四章第四章一、遍历含义一、遍历含义 在二叉树的一些应用中，常常要求在树中查找具有某种特征的结在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题。树的问题。遍历二叉树遍历二叉树是指按是指按一定规律一定规律对二叉树中的每对二叉树中的每个结点个结点访问访问且仅访问一次且仅访问一次即访遍树中每一结即
26、访遍树中每一结点（只一次），打印或处理结点。点（只一次），打印或处理结点。 遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律（或次序），能把二叉树上的各结点都访问一次且只寻找一种规律（或次序），能把二叉树上的各结点都访问一次且只访问一次。访问一次。二、遍历规则二、遍历规则bc(根结点根结点D)(右子树右子树R)R)(左子树左子树L)由二叉树的递归定义知，二叉树由二叉树的递归定义知，二叉树的三个基本组成单元是：根结点、的三个基本组成单元是：根结点、左子树和右子树。左子树和右子树。a4.4二叉树的遍历二叉树的遍历25第四章
27、第四章令：令：L L 遍历左子树遍历左子树 D D 访问根结点访问根结点 R R 遍历右子树遍历右子树组合组合LDRLDR、LRDLRD、DLRDLR、RDLRDL、RLDRLD、DRLDRL先先左左后后右右DLRDLR先（根）序遍历，先（根）序遍历， LDRLDR中（根）序遍历，中（根）序遍历， LRDLRD后（根）序遍历。后（根）序遍历。1、先序遍历先序遍历DLR首首先先访问访问根根结点，结点，其次其次遍历遍历根的根的左子树左子树，最后最后遍历根遍历根右子树右子树，对每棵子树同样按，对每棵子树同样按这三步（这三步（先根、后左、再右先根、后左、再右）进行。）进行。2、中序遍历中序遍历LDR首
28、首先先遍历根的遍历根的左子树左子树，其次其次访问访问根根结点，结点，最后最后遍历根遍历根右子树右子树，对每棵子树同样按，对每棵子树同样按这三步（这三步（先左、后根、再右先左、后根、再右）进行。）进行。3、后序遍历后序遍历LRD首首先先遍历根的遍历根的左子树左子树，其次其次遍历根的遍历根的右子树右子树，最后最后访问访问根根结点，对每棵子树同样结点，对每棵子树同样按这三步（按这三步（先左、后右、最后根先左、后右、最后根）进行。）进行。4.4 4.4 二叉树的遍历二叉树的遍历26第四章第四章三、遍三、遍历历算法算法1、先序遍历（递归算法、先序遍历（递归算法）：）：步骤：步骤：若二叉树为空，则退出；若
29、二叉树为空，则退出；否则否则:（1）访问根结点；）访问根结点；（2）先序遍历根的左子树；）先序遍历根的左子树；（3）先序遍历根的右子树。）先序遍历根的右子树。算法：算法：voidpreorder(bitreptrr)/*先先序序遍历以遍历以r为根的二叉树为根的二叉树*/if(r=NULL)return;printf(r-data);/*访问根结点访问根结点*/preorder(r-lchild)；preorder(r-rchild);/*先先序序遍历以遍历以r的右孩子为根的右子树的右孩子为根的右子树*/；4.4 4.4 二叉树的遍历二叉树的遍历27第四章第四章preorder(A)参数为根参数
30、为根A 输出输出Apreorder(A-lchild)preorder(A-rchild)调用调用参数为根参数为根return调用调用递归调用函数递归调用函数preorderABDCE参数为根参数为根B 输出输出Bpreorder(B-lchild)Preorder(B-rchild)参数为根参数为根D 输出输出Dpreorder(D-lchild)preorder(D-rchild)调用调用函数函数preorder函数函数preorder调用调用参数为根参数为根return函数函数preorder调用调用参数为根参数为根return函数函数preorder调用调用参数为根参数为根C 输出输出
31、Cpreorder(C-lchild)preorder(C-rchild)函数函数preorder返回返回返回返回参数为根参数为根E 输出输出Epreorder(E-lchild)preorder(E-rchild)调用调用返回返回调用调用参数为根参数为根return函数函数preorder调用调用参数为根参数为根return函数函数preorder参数为根参数为根return调用调用28第四章第四章2 2、中序遍历运算、中序遍历运算（递归算法（递归算法）步骤：步骤：若二叉树为空，则退出；若二叉树为空，则退出；否则否则:（1）中序遍历根的左子树；）中序遍历根的左子树；（2）访问根结点；）访问根
32、结点；（3）中）中序遍序遍历根的右子树。历根的右子树。算法：算法：voidinorder(bitreptrr)/*中序遍历以中序遍历以r为根的二叉树为根的二叉树*/if(r=NULL)return;inorder(r-lchild)；/*中序遍历以中序遍历以r的左孩子为根的左子树的左孩子为根的左子树*/printf(r-data);/*访问根结点访问根结点*/inorder(r-rchild);/*.*/29第四章第四章3、后序遍历运算（递归算法、后序遍历运算（递归算法）步骤：步骤：若二叉树为空，则退出；若二叉树为空，则退出；否则否则:（1）后序遍历根的左子树；）后序遍历根的左子树；（2）后序
33、遍历根的右子树。）后序遍历根的右子树。（3）访问根结点；）访问根结点；算法：算法：voidpostorder(bitreptrr)/*后序遍历以后序遍历以r为根的二叉树为根的二叉树*/if(r=NULL)return;postorder(r-lchild)；/*后序遍历以后序遍历以r的左孩子为根的左子树的左孩子为根的左子树*/postorder(r-rchild)；printf(r-data);/*访问根结点访问根结点*/30第四章第四章对于如下图的二叉树，其先序、中序、后序遍历对于如下图的二叉树，其先序、中序、后序遍历的序列为：的序列为：ABCDFGEHA、B、D、F、G、C、E、H。B、F
34、、D、G、A、C、E、H。F、G、D、B、H、E、C、A。先序遍历：先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：31第四章第四章以中序遍历为例来说明中序遍历二叉树的递归过程以中序遍历为例来说明中序遍历二叉树的递归过程ABDCEBD第一次经过第一次经过第二次经过第二次经过第三次经过第三次经过32第四章第四章二叉树的层次遍历：二叉树的层次遍历：从二叉树的根结点的这一层开始，逐层向下从二叉树的根结点的这一层开始，逐层向下遍历，在每一层上按从左到右的顺序对结点逐个访问。遍历，在每一层上按从左到右的顺序对结点逐个访问。四、二叉树的层次遍历四、二叉树的层次遍历ABCDFGEH右图按照层次遍历，所得到
35、的右图按照层次遍历，所得到的的结点序列为：的结点序列为：ABCDEFGH设立一个队列设立一个队列Q，用于存放结点，以保证二叉树结点，用于存放结点，以保证二叉树结点按照层次顺序从左往右进入队列。若二叉树按照层次顺序从左往右进入队列。若二叉树bt非空：非空：将根结点插入队列；将根结点插入队列；从队列中删除一个结点，访问该结点，并将该结点从队列中删除一个结点，访问该结点，并将该结点的孩子（若有的话）插入队列。的孩子（若有的话）插入队列。若此时队列非空，再从队列中删除一个结点，访问若此时队列非空，再从队列中删除一个结点，访问该结点，并将它的孩子结点插入队列。依次重复进行，该结点，并将它的孩子结点插入队
36、列。依次重复进行，直到队列为空。直到队列为空。Voidlevelorder(BinTreebt)LkQueQ;InitQueue(&Q);if(bt!=NULL)EnQueue(&Q,bt);while(!EmptyQueue(Q) p=Gethead(&Q); outQueue(&Q); visit(p); if (p-lchild!NULL) EnQueue(&Q,p-lchild); if (p-rchild!NULL) EnQueue(&Q,p-rchild); 33第四章第四章注：注：“遍遍历历”是二叉树各种操作的基础，可以在遍历是二叉树各种操作的基础，可以在遍历过程中对结点进行各种
37、操作，如：对于一棵已知二叉树过程中对结点进行各种操作，如：对于一棵已知二叉树求二叉树中结点的个数求二叉树中结点的个数；求二叉树中叶子结点的个数求二叉树中叶子结点的个数；求二叉树中度为求二叉树中度为1的结点个数的结点个数；求二叉树中度为求二叉树中度为2 2的结点个数的结点个数；求二叉树中非终端结点个数求二叉树中非终端结点个数；交换结点左右孩子；交换结点左右孩子；判定结点所在层次；判定结点所在层次；6.3 6.3 遍历二叉树遍历二叉树五、遍历二叉树的应用五、遍历二叉树的应用34第四章第四章例例1：编写求二叉树中叶结点个数的算法编写求二叉树中叶结点个数的算法(设二设二叉树的二叉链表的根指针为叉树的二
38、叉链表的根指针为bt)。intleafcount(bitreptrbt)/*求二叉树求二叉树bt中叶结点的数目中叶结点的数目*/if(bt=NULL)return(0);elseif(bt-lchild=NULL&bt-rchild=NULL)return(1);elsen=leafcount(bt-lchild);/*求左子树的叶子数目求左子树的叶子数目*/m=leafcount(bt-rchild);/*求右子树的叶子数目求右子树的叶子数目*/return(m+n); 35第四章第四章例例2：编写输出二叉树中所有度为编写输出二叉树中所有度为1 1的结点的数据域的的结点的数据域的值，并统计其
39、数目的算法值，并统计其数目的算法( (设二叉树的二叉链表的根指设二叉树的二叉链表的根指针为针为t)t)。 intonesoncount(bitreptrt)/*输出二叉树输出二叉树t中度为中度为1的结点值，并求其个数的结点值，并求其个数*/if(t=NULL)return(0);elseif(t-lchild=NULL&t-rchild!=NULL)|(t-lchild!=NULL&t-rchild=NULL)printf(t-data);return(onesoncount(t-lchild)+onesoncount(t-rchild)+1);elsereturn(onesoncount(t
40、-lchild)+onesoncount(t-rchild);36第四章第四章例例3：编写输出二叉树中所有度为编写输出二叉树中所有度为2 2的结点的数据域的的结点的数据域的值，并统计其数目的算法值，并统计其数目的算法( (设二叉树的二叉链表的根指设二叉树的二叉链表的根指针为针为BT)BT)。inttwoson(bitreptrBT)/*输出二叉树输出二叉树BT中所有度为中所有度为2的结点的数据域值，并统计其数目的结点的数据域值，并统计其数目*/if(BT=NULL)return(0);elseif(BT-lchild=NULL|BT-rchild=NULL)return(twoson(BT-l
41、child)+twoson (BT-rchild);elseif(BT-lchild!=NULL&BT-rchild!=NULL)printf(BT-data);return(twoson(BT-lchild)+twoson(BT-rchild)+1);37第四章第四章例例4：编写一算法，打印出一棵二叉树中所有非终端编写一算法，打印出一棵二叉树中所有非终端结点的值，并统计非终端结点的个数。结点的值，并统计非终端结点的个数。( (二叉树以二叉二叉树以二叉链表存储，根指针为链表存储，根指针为btbt) ) intnotleafcount(bitreptrbt)/*求二叉树求二叉树bt中非叶结点的数
42、目中非叶结点的数目*/if(bt=NULL)return(0);elseif(bt-lchild=NULL&bt-rchild=NULL)return(0);/*无左右子树无左右子树*/elseprintf(bt-data);/*输出非终端结点值输出非终端结点值*/n=notleafcount(bt-lchild);/*求左子树的非终端结点数目求左子树的非终端结点数目*/m=notleafcount(bt-rchild);return(m+n+1);/*返回总的非终端结点数返回总的非终端结点数*/38第四章第四章例例5：编写一算法，打印出一棵二叉树中所有结点的编写一算法，打印出一棵二叉树中所有
43、结点的值，并统计结点的个数。值，并统计结点的个数。( (二叉树以二叉链表存储，根二叉树以二叉链表存储，根指针为指针为btbt) ) intint f5 ( f5 (bitreptr btbt ) )/* /* 打印出二叉树打印出二叉树t t中所有结点的值，并统计结点的个数中所有结点的值，并统计结点的个数 * */ / if ( if ( btbt = NULL ) = NULL ) return (0) ; return (0) ; else else printf(btprintf(bt-data); /* -data); /* 输出结点值输出结点值* */ / n = f5( n = f5
44、( btbt-lchildlchild); ); /* /* 求左子树的结点数目求左子树的结点数目* */ / m = f5( m = f5( btbt-rchildrchild); ); /* /* 求右子树的结点数目求右子树的结点数目* */ / return (m+n+1) ; /* return (m+n+1) ; /* 返回总的结点数返回总的结点数* */ / 39第四章第四章例例6：设二叉树存储结构采用二叉链表表示，每个结设二叉树存储结构采用二叉链表表示，每个结点的数据域中存放一个整数。试编写一个算法，求此点的数据域中存放一个整数。试编写一个算法，求此二叉树上数据域的值为的结点个数
45、。二叉树上数据域的值为的结点个数。 intf6(bitreptrbt)/*求二叉树求二叉树bt结点数据域值为的结点的数目结点数据域值为的结点的数目*/if(bt=NULL)return(0);elseif(bt-data=)return(f6(bt-lchild)+f6(bt-rchild)+1);elsereturn(f6(bt-lchild)+f6(bt-rchild); 40第四章第四章一、双亲表示法一、双亲表示法 以一组连续空间存储树的结点，即一个一维数组构成，以一组连续空间存储树的结点，即一个一维数组构成，数组每个分量包含两个域：数据域和双亲域。数据域用数组每个分量包含两个域：数据域
46、和双亲域。数据域用于存储树上一个结点的数据元素值，双亲域用于存储本于存储树上一个结点的数据元素值，双亲域用于存储本结点的双亲结点在数组中的序号（下标值）。结点的双亲结点在数组中的序号（下标值）。4.5 4.5 树和森林树和森林例：例：双亲表示双亲表示A -1B 0C 0D 1E 1F 2G 2H 4I4G 4数组下标数组下标0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9每个数组元素每个数组元素含两个成员，含两个成员，即：（结点值即：（结点值和其双亲在表和其双亲在表中的位置）中的位置）注：注：找父结点容易，找结点找父结点容易，找结点的孩子麻烦，需遍历整张表。的孩子
47、麻烦，需遍历整张表。4.5.1 4.5.1 树的存储结构（三种）树的存储结构（三种）ABGCDEFHJI41第四章第四章根结点没有双亲，双亲域的值为根结点没有双亲，双亲域的值为-1。双亲链表的类型。双亲链表的类型定义如下：定义如下：#definesize10typedefstructdatatypedata;intparent;Node;Nodeslistsize;42第四章第四章二、孩子链表表示法二、孩子链表表示法树中每个结点的孩子串成一单链表树中每个结点的孩子串成一单链表孩子链表孩子链表n n个结点个结点nn个孩子链表个孩子链表n n个头指针用顺序表存储个头指针用顺序表存储表头数组：表头数
48、组：数组元素存数组元素存储结点本身的信息和该结点的孩子链表的头指针。储结点本身的信息和该结点的孩子链表的头指针。孩子链表的结点为孩子链表的结点为:childnext存放孩子结点在表头数组中的序号存放孩子结点在表头数组中的序号指向下一个孩子结点指向下一个孩子结点43第四章第四章孩子链表表示法的类型定义：孩子链表表示法的类型定义：#defineMAXND20typedefstructbnodeintchild;structbnode*next;node,*childlink;TypedefstructDataTypedata;childlinkhp;headnode;Headnode；linkMA
49、XND；44第四章第四章ABCDEFGHIJ数组下标数组下标0 01 12 2 3 3 4 4 5 5 6 6 7 7 8 8 9 912987注注: :在孩子链表表示中，找孩子方便，但在孩子链表表示中，找孩子方便，但 求结点的双亲困难，因此可在顺序表中再增求结点的双亲困难，因此可在顺序表中再增加一个域，用于指明每个结点的双亲在表中加一个域，用于指明每个结点的双亲在表中位置，即将双亲表示法和孩子链表表示法结位置，即将双亲表示法和孩子链表表示法结合起来。合起来。3435ABGCDEFHJI45第四章第四章双亲孩子表示法双亲孩子表示法树中每个结点的孩子串成一单链表树中每个结点的孩子串成一单链表孩子
50、链表孩子链表n n个结点个结点nn个孩子链表个孩子链表 同时用一维数组顺序存储树中的各结点，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的数组元素除了包括结点本身的信息和该结点的孩子链表的头指针之外，还增设一个域，用来孩子链表的头指针之外，还增设一个域，用来存储结点双亲结点在数组中的序号。存储结点双亲结点在数组中的序号。46第四章第四章A -1B 0C 0D 1E 1F 2G 2H 4I4J4 数组下标数组下标0 01 12 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9ABGCDEFHJI129873435parenthp#defineMAXND20
51、typedefstructbnodeintchild;structbnode*next;node,*childlink;TypedefstructDataTypedata;intparent;childlinkhp;headnode;Headnode；linkMAXND；47第四章第四章三、孩子兄弟链表表示法三、孩子兄弟链表表示法（二叉链表表示）（二叉链表表示）sondatabrother结点形式：结点形式：指向结点的第一个孩子结点指向结点的第一个孩子结点指向该结点的下一个兄弟结点指向该结点的下一个兄弟结点例：例：123456798 1 孩子兄弟孩子兄弟表表示示 2 3 4 5 6 7 8 9
52、 48第四章第四章孩子兄弟链表表示法类型定义：孩子兄弟链表表示法类型定义：TypedefstructtnodeDataTypedata;structtnode*son,*brother;*Tree;49第四章第四章4.5.2 4.5.2 树、森林与二叉树的转换树、森林与二叉树的转换例：例：ABCGEFDHJI二叉树二叉树1 1、一般树、一般树方法：方法： 各兄弟之间加连线；各兄弟之间加连线； 对任一结点，除最左孩子外，抹掉该对任一结点，除最左孩子外，抹掉该结点与其余孩子的各枝；结点与其余孩子的各枝； 以根为轴心，将连线顺时针转以根为轴心，将连线顺时针转45450 0。加连线加连线ABCGEFD
53、HJI留最左孩留最左孩ABCGEFDHJI转转45450 0ABCGEFDHJI50第四章第四章例：例：DABEC树树二叉树二叉树DABEC孩子兄孩子兄弟表示弟表示二叉链二叉链表表示表表示ABCEDABCDE完全一样完全一样一棵树唯一对应一棵二叉树一棵树唯一对应一棵二叉树51第四章第四章二叉树二叉树2 2、森林、森林森林森林F转换成二叉树的方法如下：转换成二叉树的方法如下：l（1）将每棵树转换成相应的二叉树；）将每棵树转换成相应的二叉树；l（2）将（）将（1）中得到的各棵二叉树的根结点看做是）中得到的各棵二叉树的根结点看做是兄弟连接起来。兄弟连接起来。ABCD树树T1EF树树T2GHJI树树T
54、3ABCDEFGHJIGHJIABCDEF森林森林F对应的二叉树对应的二叉树52第四章第四章例：例：方法：方法： 从根结点起；从根结点起； 该结点左孩和左孩右枝上的结点依次该结点左孩和左孩右枝上的结点依次 作为该结点孩子；作为该结点孩子； 重复重复 。还原还原ABCGEFD一般树一般树3 3、二叉树、二叉树还原还原ABCGEFD根无右孩的二叉树可以转变成一般树。根无右孩的二叉树可以转变成一般树。53第四章第四章4.5.3 4.5.3 树和森林的遍历树和森林的遍历先序遍历：先序遍历：先访问根结点，然后先访问根结点，然后依次依次先序先序 遍历根的每棵子树；遍历根的每棵子树；后序遍历：后序遍历：先先
55、依次依次后序遍历每棵子树，最后序遍历每棵子树，最 后访问根结点。后访问根结点。DABEC先序遍历次序：？先序遍历次序：？后序遍历次序：？后序遍历次序：？层次遍历次序：？层次遍历次序：？注：注：二叉树二叉树树树转转先序遍历先序遍历先序遍历先序遍历对应对应后序遍历后序遍历中序遍历中序遍历对应对应层次遍历：层次遍历：ABCDEBDCEAABCED一、树的遍历一、树的遍历54第四章第四章二、森林的遍历二、森林的遍历l先序遍历森林：先序遍历森林：访问森林中每棵树的根结点；先序遍历森访问森林中每棵树的根结点；先序遍历森林中第一棵树的根结点的子树组成的森林；先序遍历除去林中第一棵树的根结点的子树组成的森林；
56、先序遍历除去第一棵树之外其余的树组成的森林。第一棵树之外其余的树组成的森林。对下图中森林进行先序遍历的序列为：对下图中森林进行先序遍历的序列为：ABCDEFGHJIl中序遍历森林：中序遍历森林：中序访问森林中第一棵树的根结点的子树中序访问森林中第一棵树的根结点的子树组成的森林；访问第一棵树的根结点；中序遍历除去第一组成的森林；访问第一棵树的根结点；中序遍历除去第一棵树之外其余的树组成的森林；棵树之外其余的树组成的森林；对下图中森林进行先序遍历的序列为：对下图中森林进行先序遍历的序列为：BCDAFEJHIGABCDEFGHJI55第四章第四章问题问题：n n个学生成绩个学生成绩 a a1 1，a
57、 a2 2，,a,an n （百分制），现百分制），现 要转换成五分制。要转换成五分制。 即即 a a1 1，a a2 2，,a,an n 分五分五类：类： 一类：一类： 60 60 不及格不及格 二类：二类： 60 60， 70 70 ） 及格及格 三类：三类： 70 70， 80 80 ） 中等中等 四类：四类： 80 80， 90 90 ） 良好良好 五类：五类： 90 90 优秀优秀每类出现的概率：每类出现的概率： 分数分数 0 059 6059 6069 7069 7079 8079 8089 9089 90以上以上 概率概率 5% 15% 40% 30% 10%5% 15% 40%
58、 30% 10%4.6 4.6 判定树和哈夫曼树判定树和哈夫曼树4.6.1 4.6.1 分类与判定树分类与判定树56第四章第四章若按顺序判，得下列判断过程若按顺序判，得下列判断过程： 对对n n个数分类花费时间较多。个数分类花费时间较多。因为大多数元素因为大多数元素属于中和良，这样大多数数据都得通过属于中和良，这样大多数数据都得通过3 3至至4 4次次判断，这样总的判断次数就多。判断，这样总的判断次数就多。改改进进中中a 60a 70不及格不及格及格及格a 80a 90良良优优Y YN NN NY YN NY YY YN Na判定树判定树用于描用于描述分类过程的二叉述分类过程的二叉树，其中：每
59、个非树，其中：每个非终端结点包含一个终端结点包含一个条件，对应一次比条件，对应一次比较；每个终端结点较；每个终端结点包含一个种类标记，包含一个种类标记，对应于一种分类结对应于一种分类结果。果。57第四章第四章510153040总的判断次数最少总的判断次数最少。因为属于中、良的数最多，。因为属于中、良的数最多，而检验它们的判断少，因此总的判断次数少。而检验它们的判断少，因此总的判断次数少。哈夫曼树哈夫曼树中中a 70a 60不及格不及格及格及格a 80a 90良良优优N NY YY YN NY YN NN NY Ya如何构造时间性能最高的判定树？如何构造时间性能最高的判定树？58第四章第四章4.
60、6.2 4.6.2 哈夫曼树与哈夫曼算法哈夫曼树与哈夫曼算法一、路径长度一、路径长度叶结点带权的二叉树：叶结点带权的二叉树：结点结点n ni i的带权路径长度：的带权路径长度： 为结点为结点ni i到树根的路径长度到树根的路径长度(n(ni i的祖先的个数的祖先的个数l li i)结点结点ni i所带的权（所带的权（p pi i）每个叶子每个叶子n1 1，n2 2，,nk k带一个实数称为带一个实数称为权权) )一组实数一组实数 p p1 1，p p2 2，,p pk k 例：例：p pi i表示表示输入最终落入输入最终落入n ni i的概率的概率abcd7 75 52 24 4a的路径长度的
61、路径长度=？2 27=147=1459第四章第四章叶结点带权的二叉树路径长度叶结点带权的二叉树路径长度WPLWPL：abcd7 75 52 24 4d d的路径长度的路径长度= =？ WPL=WPL=？ n n WPL=WPL=(p pk kllk k) )， k=1k=1 其中：其中：nn叶子数叶子数 p pk k第第k k个叶子的权个叶子的权 l lk k从根到第从根到第k k个叶子的路径长度（分支数）个叶子的路径长度（分支数）8 8363660第四章第四章例：二叉树有例：二叉树有4 4个叶子，权分别为个叶子，权分别为7 7，5 5，2 2，4 4abcd7 75 52 24 4badc7
62、 74 42 25 5WPL=36WPL=36WPL=?WPL=?WPL=?WPL=?(35)(35)(46)(46)结论结论：带权路径长最小的二叉树带权路径长最小的二叉树权大的权大的叶子离根近叶子离根近权小的叶子离根远权小的叶子离根远哈夫曼树（最优二叉树）哈夫曼树（最优二叉树）dab7 74 45 52 2c二、哈夫曼树二、哈夫曼树其特征是其特征是61第四章第四章F=TF=T1 1，T T2 2，,T,Tn n TT1 1，T T2 2，,T,Tn n 权从小到大排列权从小到大排列 取取F F中中T T1 1和和T T2 2( (权最小的二棵权最小的二棵) )生成一棵二叉树生成一棵二叉树T
63、T， T T为根，为根， T T1 1、T T2 2分别为分别为T T的左、右子树，的左、右子树， T T的权的权=T=T1 1的权的权+T+T2 2的的权；权； T T插入到插入到F F的余下森林中（按序）；的余下森林中（按序）；方法：方法：三、哈夫曼算法三、哈夫曼算法构造构造给定给定n n个权值个权值 p p1 1，p2 2，, , pn n nn个叶子带的权个叶子带的权 森林森林F F=T=T1 1，T T2 2，,T,Tn n TTi i只有一个带权只有一个带权p pi i 的根结点，左、右子树为空的根结点，左、右子树为空 排排序序重复重复、，直至，直至F=TF=T为一棵二叉树。为一棵
64、二叉树。 此二叉树此二叉树T T即即为哈夫曼树为哈夫曼树62第四章第四章森林森林F F= = p= 7p= 7，5 5，2 2，4 4 dab7 74 45 52 2c例：例：bcda5 5b2 2c4 4d7 7a森林森林F= F= 2 2c4 4d5 5b7 7a不减序列不减序列第一步：第一步：插入插入F F5 5b2 2c4 4d6 62 2c4 4d6 67 7a第二步：第二步：5 5b2 2c4 4d6 61111插入插入F F7 7a5 5b2 2c4 4d6 61111第三步：第三步：插入插入F Fdab7 74 45 52 2c哈夫曼树哈夫曼树初始森林共有初始森林共有n棵二叉树
65、，每棵棵二叉树，每棵树中都仅有一个孤立的结点，要树中都仅有一个孤立的结点，要进行进行n-1次合并才能得到哈夫曼次合并才能得到哈夫曼树，每次合并产生一个新结点。树，每次合并产生一个新结点。最终由最终由2n-1个结点。个结点。63第四章第四章采用顺序存储，设置大小为采用顺序存储，设置大小为2n-1的数组，每个数组元素由的数组，每个数组元素由4个域组成：个域组成：存储权值、双亲指针、左孩子指针和右孩子指针。类型定义如下：存储权值、双亲指针、左孩子指针和右孩子指针。类型定义如下：constintn=10;typedefstructfloatw;/w为结点的权值为结点的权值intparent,lchil
66、d,rchild;/父结点和左、右孩子所在数组的下标父结点和左、右孩子所在数组的下标node;typedefnodehftree2*n-1；哈夫曼算法：哈夫曼算法：1.将表示哈夫曼树的数组将表示哈夫曼树的数组T中的中的2n-1结点初始化；结点初始化；2.读入读入n个权值到数组个权值到数组T的前的前n个分量中，它们是初始森林中的个分量中，它们是初始森林中的n个孤立的根结个孤立的根结点的权值；点的权值；3.对森林中的树进行对森林中的树进行n-1次合并，共产生次合并，共产生n-1个新结点，依次放入数组个新结点，依次放入数组T的第的第i个个分量重分量重(n=i2*n-1)。每次合并的步骤如下：。每次合
67、并的步骤如下：从当前森林的所有结点从当前森林的所有结点Tj(0=j=i-1)中选取具有最小权值和次小权中选取具有最小权值和次小权值的两个根结点，分别用值的两个根结点，分别用x和和y记住这两个根结点在数组记住这两个根结点在数组T中的下标。中的下标。将根为将根为Tx和和Ty的两棵树合并，使它们分别成为新结点的两棵树合并，使它们分别成为新结点Ti的左右的左右孩子，得到一棵以新结点孩子，得到一棵以新结点Ti为根的二叉树。同时修改为根的二叉树。同时修改Tx和和Ty的双的双亲域亲域parent，使其指向新结点，使其指向新结点Ti,将将Tx和和Ty的权值相加后作的权值相加后作为新结点为新结点Ti的权值。类的
68、权值。类C语言描述的算法见语言描述的算法见P122。64第四章第四章四、哈夫曼编码四、哈夫曼编码 每个字符在电文中出现的次数为每个字符在电文中出现的次数为w wi i，其编其编 码长为码长为m mi i，电文有电文有n n种字符，则电文总长种字符，则电文总长=?=? 什么是哈夫曼编码？如何设计？什么是哈夫曼编码？如何设计？ 求哈夫曼编码的算法。求哈夫曼编码的算法。 分二步：分二步：1 1）以）以n n个字符的权值，构造哈夫曼树；个字符的权值，构造哈夫曼树； 2 2）求）求n n个字符的哈个字符的哈夫曼编码。夫曼编码。 4.6.3 4.6.3 哈夫曼树及其应用哈夫曼树及其应用 n n ( (w
69、wi immi i) ) i=1i=1 65第四章第四章 哈夫曼编码哈夫曼编码可利用可利用哈夫曼哈夫曼树构造用于通信的二进制编码称为树构造用于通信的二进制编码称为哈夫曼哈夫曼编码编码。树中从根到每个叶子都有一条路径，对路径上的各树中从根到每个叶子都有一条路径，对路径上的各分支约定指向左子树根的分支表示分支约定指向左子树根的分支表示“0”码，指向右子码，指向右子树的分支表示树的分支表示“1”码，取每条路径上的码，取每条路径上的“0”或或“1”的序列作为和各个叶子对应的字符的编码，这就是的序列作为和各个叶子对应的字符的编码，这就是哈夫哈夫曼曼编码编码。66第四章第四章 哈夫曼哈夫曼编码的应用编码的
70、应用例电文：例电文：“CASTTATASA”。其中：其中：C出现出现1次，次，A出现出现4次，次，S出现出现2次，次，T出现出现3次，次，出现出现3次。次。哈夫曼哈夫曼编码：编码：C：100A：11S：101T：00：010000111167第四章第四章了了解解树树的的定定义义及及基基本本术术语语；掌掌握握二二叉叉树树的的定定义义、性性质质及及满满二二叉叉树树、完完全全二二叉叉树树的的定定义义；熟熟练练掌掌握握二二叉叉树树的的二二叉叉链链表表表表示示；熟熟练练掌掌握握二二叉叉树树的的三三种种遍遍历历（先先序序、中中序序、后后序序）过过程程和和算算法法，并并能能运运用用遍遍历历算算法法实实现现二二叉叉树树的的其其它它一一些些操操作作；熟熟悉悉树树的的各各种种存存储储表表示示及及特特点点，熟熟练练掌掌握握树树与与二二叉叉树树的的转转换换方方法法；熟熟练练掌掌握握建建立立哈哈夫夫曼曼树树的的方方法法；理理解解由由二二叉叉树树先先序序序序列列、中中序序序序列列及及后后序序序序列列和和中中序序序序列列可可唯唯一一的的确确定定一一棵棵二二叉叉树树的的道道理理，掌握由此建立二叉树的方法。掌握由此建立二叉树的方法。重点重点：二叉树遍历过程及算法、哈夫曼树的构造。二叉树遍历过程及算法、哈夫曼树的构造。第四章树和二叉树小结第四章树和二叉树小结68
