树和二叉树数据结构C语言第三版.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第5章:树形结构,5.1 树的概念与基本操作,5.2 二叉树,5.3 树与森林,5.4 最优二叉树-哈夫曼树,1.树的定义：,树是n（n0）个结点的有限集合。,若n=0，则称为空树；否则，,当n0时，该集合满足如下条件：,1）有且仅有一个特定的结点被称为根，,它没有直接前驱，但有零个或多个直接后继。,2）当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树,，称为根root的子树。,由此可以看出，树的定义是,递归,。,树的特点：,1）树的根结点,没有直接前驱，除根以外的所有结点,有且只有一个直接前驱。,2）树中所有结点可以,有零个或多个直接后继。,树的表示方法(补充)：,(1)树形表示法（倒置树结构）。,树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象。,(2)文氏图表示法（嵌套集合形式）。,使用集合以及集合的包含关系描述树结构。,(3)凹入表示法。,使用线段的伸缩描述树结构。用位置的缩进表示其层次。如程序的缩进结构、书的目录编排格式等。,(4)嵌套括号表示法（广义表形式）。,将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。,例如一本书A分为B、C、D三章，B章分为E、F两节，E节又分为K、L两段。可表示为：(A(B(E(K,L),F),C,D),1)结点：,包含一个数据元素及若干指向其它结点的分支信息。,2)结点的度(degree)：,一个结点的子树个数称为此结点的度。,3)叶子结点(Leaf)：,度为0的结点，即无后继的结点，也称为终端结点。,4)分支结点(Internal node)：,度不为0的结点，也称为非终端结点。,5)孩子结点：,一个结点的直接后继称为该结点的孩子结点。,双亲结点：,一个结点的直接前驱称为该结点的双亲结点。,兄弟结点：,同一双亲结点的孩子结点之间互称兄弟结点。,6)路径与路径长度,树中存在一个结点序列k1,k2,kn,若ki是ki+1的双亲结点，则k1,k2,kn称为k1到kn的路径，显然,从树的根结点到树中其余结点均存在一条路径。,路径的长度,等于路径所通过的结点数目减1(即路径上分支数目)。,7)祖先结点：,一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。,子孙结点：,一个结点的直接后继和间接后继称为该结点的子孙结点。,8)结点的层次：,从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。,9)树的高度(深度)(Height/Depth)：,树中所有结点的层次的最大值。,10)树的度：,树中所有结点度的最大值。,11)有序树、无序树：,如果树中每棵子树从左向右的排列拥有一定的顺序，,不得互换，则称为有序树，否则称为无序树。,12)森林：,m（m0）棵互不相交的树的集合。将一棵非空树的根结点删去，,树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。,else printf(“优秀”);,树转换成的二叉树其右子树一定为空!,二叉树有五种基本形态,任何复杂的二叉树都是这五种基本形态的复合。,(4)重复(2)、(3)两步,当F中只剩下一棵二叉树时,这棵二叉树便是所要建立的哈夫曼树。,PreOrder（bt-rchild）;/*先序递归遍历bt的右子树*/,因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。,right subtree,(4)重复(2)、(3)两步,当F中只剩下一棵二叉树时,这棵二叉树便是所要建立的哈夫曼树。,一个该结点的第一个孩子结点指针域;,（3）Parent（t，x）：求树t中结点x的双亲结点。,从左到右，依次后根遍历根结点的每一棵子树。,后根序遍历：8,9,4,10,11,5,2,12,13,6,14,15,7,3,1,具有不同带权路径长度的二叉树:,Char*cd;,具有最小带权路径长度的二叉树称为哈夫曼树。,（1）Initiate（t）：,初始化一棵空树t。,（2）Root（x）：,求结点x所在树的根结点。,（3）Parent（t，x）：,求树t中结点x的双亲结点。,（4）Child（t，x，i）：,求树t中结点x的第i个孩子结点。,（5）RightSibling（t，x）：,求树t中结点x的第一个右边兄弟结点。,（6）Insert（t,x,i,s）：,把以s为根结点的树插入到树t中作为结点x的第i棵子树。,（7）Delete（t，x，i）：,在树t中删除结点x的第i棵子树。,（8）Traverse（t）：,是树的遍历操作。,二叉树也称为二次树或二分树,它是,另一种树形结构,。它与树形结构的区别：,（,1,）每个结点最多有两棵子树；,（,2,）子树有左右之分。,二叉树的定义是一种,递归定义,。即：二叉树是,n,（,n0,）个结点的有限集合。,（,1,）当,n=0,时，称为空二叉树；,（,2,）当,n0,时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。,说明：,二叉树的结构是非线性的，每一结点最多可有两个后继。,二叉树是有序的。,二叉树并不是树的特例，它跟树是两个不同的概念，是另一种树形结构，,二叉树有五种基本形态,任何复杂的二叉树都是这五种基本形态的复合。,left subtree,right subtree,Root,(,两种特殊的二叉树),1）满二叉树：,在一棵二叉树中,如果所有分支结点都有左孩子结点和右孩子结点,并且叶结点都集中在二叉树的最下一层,这样的二叉树称为满二叉树。,2）完全二叉树：,若二叉树中最多只有最下面两层的结点的度数可以小于2,并且最下面一层的叶结点都依次排列在该层最左边的位置上,则这样的二叉树称为完全二叉树。,满二叉树：,深度为k且有2,k,-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。,1,6,7,5,4,9,8,2,3,11,10,13,12,15,14,完全二叉树：,有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结点位置一一对应，则称这棵二叉树为完全二叉树。,1,6,7,5,4,9,8,2,3,11,10,13,12,14,1,2,3,11,4,5,8,9,12,13,6,7,10,14,15,1,2,3,11,4,5,8,9,12,6,7,10,1,2,3,4,5,6,7,1,2,3,4,5,6,性质1：在二叉树的第i层上至多有2,i-1,个结点(i1)。,证明：归纳基础：当i=1时，整个二叉树只有一根结点，此时2,i-1,=20=1，结论成立。,归纳假设：假设i=k时结论成立，即第k层上结点总数最多为2,k-1,个。,现证明当i=k+1时，结论成立：,因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即22,k-1,=2,(k+1),-1，故结论成立。,性质2：深度为k的二叉树至多有2,k,-1个结点（k1）。,证明：因为深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树的结点总数至多为：,故结论成立。,性质3：对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+1。,证明：设二叉树中结点总数为n，n1为二叉树中度为1的结点总数。因为二叉树中所有结点的度小于等于2，所以有n=n0+n1+n2。设二叉树中分支数目为B，因为除根结点外，每个结点均对应一个进入它的分支，所以有n=B+1。又因为二叉树中的分支都是由度为1和度为2的结点发出，所以分支数目为B=n1+2n2。所以n=B+1=n1+2n2+1;将n=n0+n1+n2代入上式整理可得n0=n2+1，故结论成立。,性质4：具有n个结点的完全二叉树的深度为,log,2,n,+1。,(其中，,log,2,n,的结果是不大于log,2,n,的最大整数。),证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出：,2,K-1,-1n2,K,-1,将不等式两端加1得到：,2,K-1,n2,K,将不等式中的三项同取以2为底的对数，并经过化简后得到：,K-1log,2,n,n，则结点i没有左孩子；否则其左孩子结点的编号为2i。,（3）如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。,下面我们利用数学归纳法证明这个性质。我们首先证明（2）和（3）。,当i=1时，若n3，则根的左、右孩子的编号分别是2，3；若n3，则根没有右孩子；若ndata）;,/*访问结点的数据域*/,PreOrder（bt-lchild）;,/*先序递归遍历bt的左子树*/,PreOrder（bt-rchild）;,/*先序递归遍历bt的右子树*/,中序遍历(Inorder Traversal),void InOrder（BiTree bt）,/*中序遍历二叉树bt*/,if(bt=NULL)return;,/*递归调用的结束条件*/,InOrder（bt-lchild）;,/*中序递归遍历bt的左子树*/,Visit（bt-data）;,/*访问结点的数据域*/,InOrder（bt-rchild）;,/*中序递归遍历bt的右子树*/,后序遍历(Postorder Traversal),void PostOrder（BiTree bt）,/*后序遍历二叉树bt*/,if(bt=NULL)return;,/*递归调用的结束条件*/,PostOrder（bt-lchild）;,/*后序递归遍历bt的左子树*/,PostOrder（bt-rchild）;,/*后序递归遍历bt的右子树*/,Visit（bt-data）;,/*访问结点的数据域*/,G H,D E F,B C,A,图 5-19,按层次遍历该二叉树的序列为：,ABCDEFGH,实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。,查找结点FindNode(*b,x),BTNode*FindNode(BTNode*b,ElemType x),BTNode*p;,if(b=NULL)return NULL;,else if(b-data=x)return b;,else,p=FindNode(b-lchild,x);,if(p!=NULL)return p;,else return FindNode(b-rchild,x);,例5.2统计给定二叉树的叶子结点数目。,算法5.9：求二叉树的叶子数,int countleaf(bitreptr root),/先根遍历根指针为root的二叉树以计算其叶子数,int i;,if(root=NULL)i=0;,else if(root-lchild=NULL),else i=count2(root-lchild)+count2(root-rchild);,return(i);,例5.3求二叉树的深度运算。,求二叉树的高度的递归模型f()如下：,f(NULL)=0,f(b)=MAXf(b-lchild),f(b-rchild)+1 其他情况,int TreeDepth(BiTree*bt),int hl,hr,max;,if(bt!=NULL),hl=PostTreeDepth(bt-LChild);/*求左子树的深度*/,hr=PostTreeDepth(bt-RChild);/*求右子树的深度*/,max=hlhr?hl:hr;/*得到左、右子树深度较大者*/,return(max+1);/*返回树的深度*/,else return(0);/*如果是空树，则返回0*/,例5.4创建二叉树的二叉链表存储，并显示。（略）,例如,已知先序序列为ABDGCEF,中序序列为DGBAECF,则构造二叉树的过程如下所示。,根结点：A,左先序:BDG 左中序:DGB,右先序:CEF 右中序:ECF,根结点：B,左先序:DG 左中序:DG,右先序:空 右中序:空,根结点：D,左先序:空 左中序:空,右先序:G 右中序:G,根结点：G,左先序:空 左中序:空,右先序:空 右中序:空,根结点：C,左先序:E 左中序:E,右先序:F 右中序:F,根结点：E,左先序:空 左中序:空,右先序:空 右中序:空,根结点：F,左先序:空 左中序:空,右先序:空 右中序:空,定理7.1：任何n(n0)个不同结点的二又树,都可由它的中序序列和先序序列惟一地确定。,例如,已知中序序列为DGBAECF,后序序列为GDBEFCA。对应的构造二叉树的过程如下所示。,根结点：A,左中序:DGB 左根:B,右中序:ECF 右根:C,根结点：B,左中序:DG 左根:D,右中序:空 右根:空,根结点：D,左中序:空 左根:空,右中序:G 右根:G,根结点：G,左中序:空 左根:空,右中序:空 右根:空,根结点：C,左中序:E 左根:E,右中序:F 右根:F,根结点：E,左中序:空 左根:空,右中序:空 右根:空,根结点：F,左中序:空 左根:空,右中序:空 右根:空,定理7.2：任何n(n0)个不同结点的二又树,都可由它的中序序列和后序序列惟一地确定。,练习：,1：已知二叉树的后序和中序序列如下,构造出该二叉树,并写出其前序序列。,后序序列:ABCDEFG 中序序列:ACBGEDF,这种存储结构是一种顺序存储结构,用一组连续空间存储树的所有结点,同时在每个结点中附设一个伪指针指示其双亲结点的位置。,树的双亲存储结构示意图,孩子链存储结构可按树的度,(,即树中所有结点度的最大值,),设计结点的孩子结点指针域个数。,孩子兄弟链存储结构是为每个结点设计三个域：,一个数据元素域,;,一个该结点的第一个孩子结点指针域,;,一个该结点的下一个兄弟结点指针域。,下图,(a),的树对应的孩子兄弟链存储结构如图,(b),所示。,树的,孩子兄弟链,存储结构示意图,A,B,C,D,E,F,G,H,I,A,B,C,D,E,F,G,H,I,A,B,C,D,E,F,G,H,I,A,B,C,D,E,F,G,H,I,A,B,C,D,E,F,G,H,I,树转换成的二叉树其右子树一定为空!,5.3.2树、森林与二叉树的相互转换,抹线：,对树中每个结点，除了其左孩子外抹去该结点与其余孩子之间的连线。,加线：,在树中所有相邻的兄弟之间加一连线；,整理：,以树的根结点为轴心，将整树顺时针转,45,。,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,将各棵树分别转换成二叉树,将每棵树的根结点用线相连,以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构,将森林转换为二叉树的过程,3.,二叉树转换成树,加线：,若,p,结点是双亲结点的左孩子，则将,p,的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与,p,的双亲用线连起来,抹线：,抹掉原二叉树中双亲与右孩子之间的连线,调整：,将结点按层次排列，形成树结构,A,B,C,D,E,F,G,H,I,A,B,C,D,E,F,G,H,I,A,B,C,D,E,F,G,H,I,A,B,C,D,E,F,G,H,I,A,B,C,D,E,F,G,H,I,将一棵二叉树还原为树的过程,抹线：,将二叉树中根结点与其右孩子连线，及沿右分支,搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树,还原：,将孤立的二叉树还原成树,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,树的遍历方法主要有以下两种：,1）先根遍历,若树非空，则遍历方法为：,访问根结点。,从左到右，依次先根遍历根结点的每一棵子树。,例如，图中树的先根遍历序列为,ABECFHGD,。,2),后根遍历,若树非空，则遍历方法为：,从左到右，依次后根遍历根结点的每一棵子树。,访问根结点。,例如，图中树的后根遍历序列为,EBHFGCDA,。,2.,树的遍历算法实现,算法,满二叉树：深度为k且有2k-1个结点的二叉树。,5)孩子结点：一个结点的直接后继称为该结点的孩子结点。,BTNode*FindNode(BTNode*b,ElemType x),左先序:E 左中序:E,右先序:空 右中序:空,2）树中所有结点可以有零个或多个直接后继。,WPL(c)=7152234335,一个该结点的第一个孩子结点指针域;,从这个意义上说，遍历操作就是将二叉树中结点按一定规律线性化的操作，目的在于将非线性化结构变成线性化的访问序列。,WPL(b)=4273532146,(4)重复(2)、(3)两步,当F中只剩下一棵二叉树时,这棵二叉树便是所要建立的哈夫曼树。,例如,已知中序序列为DGBAECF,后序序列为GDBEFCA。,1：已知二叉树的后序和中序序列如下,构造出该二叉树,并写出其前序序列。,遍历左子树，遍历右子树，访问根(记做LRD)。,例如:给定一个权值序列2,3,4,7，可构造下图所示的多种二叉树的形态。,InOrder（bt-rchild）;/*中序递归遍历bt的右子树*/,Lchild Data Rchild Parent,1）满二叉树：在一棵二叉树中,如果所有分支结点都有左孩子结点和右孩子结点,并且叶结点都集中在二叉树的最下一层,这样的二叉树称为满二叉树。,主要有以下三种：,1)先序遍历,若森林非空，则遍历方法为：,访问森林中第一棵树的根结点。,先序遍历第一棵树的根结点的子树森林。,先序遍历除去第一棵树之后剩余的树构成的森林。,例如，图中森林的先序遍历序列为,ABCDEFGHIJ,。,2),中序遍历,若森林非空，则遍历方法为：,中序遍历森林中第一棵树的根结点的子树森林。,访问第一棵树的根结点。,中序遍历除去第一棵树之后剩余的树构成的森林。,例如，图中森林的中序遍历序列为,BCDAFEHJIG,。,3),后序遍历,若森林非空，则遍历方法为：,后序遍历森林中第一棵树的根结点的子树森林。,后序遍历除去第一棵树之后剩余的树构成的森林。,访问第一棵树的根结点。,例如，图中森林的后序遍历序列为,DCBFJIHGEA,。,例:学生成绩的分布呈正态分布即：中等成绩的学生较多，而较好或较差学生均比较少。,设其分布规律如下表：,等级,分数段,比例,优秀,良好,中等,及格,不及格,059,6069,7079,8089,90100,5,15,40,30,10,哈夫曼树的应用,要编制一个将百分制转换成五级分制（优、良、中、及、不及）的程序。显然这程序很简单。如下：,if(a60)printf(“不及格”);,else if(a70)printf(“及格”);,else if(a80)printf(“中等”);,else if(a90)printf(“良好”);,else printf(“优秀”);,如果我们以各分数段人数占总人数的比例,5、15、40、30、10,为权值构造哈夫曼树，可得到以下判定树,用这个判定树进行判断可以使大部分数据经过较少次数的比较得到结果。,Y,if(a=70),printf(“中等”);,else if(a=80),printf(“良好”);,else if(a=60),printf(“及格”);,else if(a60),printf(“不及格”);,else printf(“优秀”);,相关术语,1：路径：,若在一棵树中存在着一个结点序列k,1,k,2,k,j,使得k,i,是k,i+1,的父亲(1ij),则称该结点序列是从k,1,到k,j,的路径。,2：路径长度：,从k,1,到k,j,所经过的分支数称为这两点之间的路径长度。,3：结点的权：,树中的结点上赋予的一定意义的实数称之为该结点的权。,4：带权路径长度：,从树根结点到该结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度。,5：树的带权路径长度：,树中所有叶子结点的带权路径长度之和，记为：WPL=,设二叉树具有n个带权值的叶子结点,那么从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和,叫做,二叉树的带权路径长度,。,其中,n表示叶子结点的数目,wi和li分别表示叶子结点ki的权值和根到ki之间的路径长度(即从叶子结点到达根结点的分支数)。,具有最小带权路径长度的二叉树称为,哈夫曼树,。,具有不同带权路径长度的二叉树:,WPL,(a)=7252224236,WPL,(b)=4273532146,WPL,(c)=7152234335,什么样的树的带权路径长度最小？,例如:给定一个权值序列2,3,4,7，可构造下图所示的多种二叉树的形态。,WPL,=2*2+2*3+2*4+2*7=32,WPL,=1*2+2*3+3*4+3*7=41,WPL,=1*7+2*4+3*3+3*2=30,如何构造哈夫曼树,根据哈夫曼树的定义,一棵二叉树要使其,WPL值最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点。,那么如何构造一棵哈夫曼树呢?,其方法如下:,(1)由给定的n个权值W1,W2,.,Wn,构造n棵只有一个叶子结点的二叉树,从而得到一个二叉树的集合F=T1,T2,.,Tn;,(2)在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树,这棵新的二叉树根结点的权值为其左、右子树根结点权值之和;,(3)在集合F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到集合F中;,(4)重复(2)、(3)两步,当F中只剩下一棵二叉树时,这棵二叉树便是所要建立的哈夫曼树。,5.4.2哈夫曼树的构造算法（略）,给定权值w=(1,3,5,7)来构造一棵哈夫曼树。,构造一棵哈夫曼树的过程,-哈夫曼树的应用,在传送电文,(AAADCB),时，希望总长尽可能地短。如对每个字符设计长度不等的编码，且让在,电文中出现次数较多的字符采用尽可能短的编码,，则电文的总长便可减少。,如果设计,ABCD,的编码分别为,0,，,00,，,1,，,01,，但是这样的电文无法翻译，如传送过去的前三个字符的子串“,000”,就可有几种译法，或是,AB,或是,AAA,或是,BA,。,要设计长短不等的编码，则必须是,任一个字符的编码都不是另一个字符的编码的前缀,，这种编码称为,前缀编码,。,如何得到使电文总长最短的二进前缀编码呢？,假设每种字符在电文中出现的次数为,w,k,，其编码长度为,l,k,，电文中只有,n种字符,，则电文总长为:,对应到二叉树上，若置,W,k,为叶子结点的权，,l,k,恰为从根到叶子的路径长度，则上式恰为,二叉树上带权路径长度,。,由此可见，设计电文总长最短的二进制前缀编码，就是,以n种字符出现的频率作权，设计一棵哈夫曼树,的问题，由此得到的二进制前缀编码便称为哈夫曼编码。,对应的哈夫曼编码如下：,1：000 3：001,5：01 7：1,哈夫曼编码具体构造方法如下：,对一棵具有n个叶子的哈夫曼树，规定,哈夫曼树中的左分支为0,右分支为1,则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码，这样的编码称为,哈夫曼编码,。,void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n),/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/,Char*cd;,cd=(char*)malloc(n+1)*sizeof(char);,/*分配求当前编码的工作空间*/,cdn-10；,/*从右向左逐位存放编码，首先存放编码结束符*/,for(i=1;i=n;i+),/*求n个叶子结点对应的哈夫曼编码*/,start=n-1;,/*初始化编码起始指针*/,c=i;p=hti.parent;,/*从叶子结点开始向上倒推*/,while(p!=0),-start;,if(htp.LChild=c)cdstart=0;,/*左分支标0*/,else cdstart=1;,/*右分支标1*/,c=p;p=htp.parent;,/*向上倒推*/,hci=(char*)malloc(n-start)*sizeof(char);,/*为第i个编码分配空间*/,strcpy(hci,free(cd);,作业,1：设给定权集W=3，4，5，6，8，10，50，200，试构造关于W的一棵赫夫曼树，并求其WPL。,1：有段电文”ABBCDSCBCBCAACDACDAAAFS”,统计其中字符的频率,试画出对应的huffman树,并画出每个字符的huffman编码。,本章小结,本章的基本学习要点如下：,(1)掌握树的相关概念,包括树、结点的度、树的度、分支结点、叶子结点、孩子结点、双亲结点、树的深度、森林等定义。,(2)掌握树的表示,包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。,(3)掌握二叉树的概念,包括二叉树、满二叉树和完全二叉树的定义。,(4)掌握二叉树的性质。,(5)重点掌握二叉树的存储结构,包括二叉树顺序存储结构和链式存储结构。,(6)重点掌握二叉树的基本运算和各种遍历算法的实现。,(7)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。,