数据结构第6章ppt课件.ppt

《数据结构第6章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第六章树和二叉树复习一、二叉树二叉树的定义、存储二叉树的性质线索化二叉树二、树和森林树的定义、存储树和森林的遍历树和森林与二叉树之间的转换三、哈夫曼树哈夫曼树定义、建立哈夫曼编码本章学习要求掌握：树和二叉树的性质，有关术语及基本概念掌握：二叉树的两种存储方法，重点是链式存储掌握：各次次序的遍历算法，能灵活遍历算法实现二叉树的各种运算掌握：几种建立二叉树的方法了解：二叉树的线索化，了解在各种线索树中查找给定结点的前趋和后继的方法了解：树、森林和二叉树之间的转换方法了解：树的各种存储结构及其特点；树和森林的两种次序的遍历掌握：哈夫曼树的基本概念及哈夫曼编码的

2、方法2一、二叉树或空，或由根和由互不相交的左子树、右子树构成。1、二叉链表第六章树和二叉树abcdfeabcedfg2、顺序存储g3特征：1.叶子结点只可能在层次最大的两层上出现2.任一结点，若其右分支下的子孙的最大层次为k，则其左分支下的最大层次为K或K+1.3.完全二叉树最多只有一个度为1的结点满二叉树和完全二叉树满二叉树：深度为k且有2k-1个结点的二叉树。可以对满二叉树进行编号。编号方式为：根编号为1，从上到下，从左到右。满二叉树完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树编号从1到n的结点一一对应时，称为完全二叉树。

3、完全二叉树4练习1（第六章课后习题四、2）已经某完全二叉树有100个结点，试求该二叉树的叶子数解：设度为0的结点n0个数为x，则度为2的结点个数n2为x-1且完全二叉树的度为1的结点个数为0或1根据题意得：n0+n1+n2=100即2x-1+n1=100所以,n1=1x=50可得：叶子数为50个练习2（第六章课后习题四、5）已知完全二叉树的第6层有5个叶子，试画出所有满足这一条件的完全二叉树，并指出结点最多的那棵树的叶子数解：完全二叉树的叶子只会出现在最下面两层5性质1：在二叉树的第i(i>0)层上至多有2i-1个结点。性质2：深度为k的二叉树中至多有2k-1个结点

4、(k>0)。性质3：对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0=n2+1。性质4：有n个结点的完全二叉树的深度为+1。2、二叉树的性质6性质5：如果对一棵有n个结点的完全二叉树按层序从1开始编号，则对任一结点(i<=i<=n),有：(1)如果i=1，则结点i是二叉树的根结点；如果i>1,则其双亲结点是[i/2]。(2)如果2i<=n,则结点i的左孩子是结点2i；否则结点i无左孩子。(3)如果2i+1<=n,则结点i的右孩子是结点2i+1；否则结点i无右孩子。732个结点的完全二叉树，从根开始，按层次从左到右用1-32编号。请回答：（1）

5、它共有多少层？（2）各层最左边的结点的编号是多少？（3）编号为6的结点的左孩子的编号是多少？它的右孩子呢？（4）编号为16的结点的左孩子的编号是多少？它的右孩子呢？（5）对于编号为8的结点，它的父结点的编号是多少？编号为13的结点呢？编号为1的结点呢？练习38二叉树的遍历：按某条搜索路径访问二叉树中每一个结点，使得每个结点被访问一次且仅被访问一次。遍历方法有4种：先序遍历，中序遍历，后序遍历，层次遍历。3、二叉树的遍历9先序遍历二叉树：（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树先序遍历序列：abcdfge1234567abcdfge10中序遍历二叉树：

6、（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树中序遍历序列：bafgdceabcdfge123456711后序遍历二叉树：（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点后序遍历序列：bgfdecaabcdfge123456712abcdfge1234567层次遍历二叉树：按层次（1-k层)，每层从左到右依次访问二叉树中的每一个结点。层次遍历序列：abcdefg13练习4已知二叉树先序遍历序列是:abcdefg;中序遍历序列是:cbdaefg;（1）画出该二叉树;（2）写出后序遍历序列（1）（2）写出后序遍历序列：cdbgfeaabcdefg123

7、45671415ltag=0：lchild指示该结点的左孩子ltag=1：lchild指针该结点的前趋。rtag=0：rchild指示该结点的右孩子rtag=1：rchild指针该结点的后继。有线索标志的二叉树4线索二叉树15BACEDGFroot先序线索二叉树NULL先序序列：ABDEGCF16BACEDGFroot中序线索二叉树NULLNULLIH中序序列：DBGIEHACF17BACEDGFroot后序线索二叉树HILK后序序列：IDGHEBKLFCANULL1819ABCDEABDCET中序序列：BCAED00001111^11^中序线索二叉树19练习5