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