数据结构第六章ppt课件

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

1、第六章二叉树与树1提示基本内容二叉树的概念、性质和存储结构；二叉树的遍历和线索化算法；树的定义、存储结构、树与二叉树的转换、树的遍历；哈夫曼树的构造；学习要点1．掌握二叉树的结构特性，2．熟悉二叉树的各种存储结构的特点及适用范围；3．遍历二叉树是二叉树各种操作的基础。掌握各种遍历策略的递归算法，能灵活运用遍历算法实现二叉树的其他操作；4．理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5．熟悉树的各种存储结构及其特点，掌握树和与二叉树的转换方法，掌握树的遍历方法；6．了解哈

2、夫曼树的特性，掌握构造哈夫曼树和哈夫曼编码的方法；2树的概念树结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。树是n个结点的有限集合，在任一棵非空树中：（1）有且仅有一个称为根的结点。（2）其余结点可分为个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念JIACBDHGFE3A只有根结点的树ABCDEFGHIJKLM有子树的树根子树4从逻辑结构看：1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他

3、结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构JIACBDHGFE5基本术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~兄弟(sibling)——同一双亲的孩子树的度——一棵树中最大的结点度数结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……深度(depth)——树中结点的最大层次数森林(forest)——m(m0)棵互不相交的树的集

4、合6ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先76.1二叉树概念6.2二叉树遍历6.3树和森林6.4二叉树与树的应用6.5栈、递归、树与回溯法算法内容提要8小结9期中习题第二章线性表一、填空题1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a1，a2,……an)，其中每个ai代表一个______。

5、a1称为______结点，an称为______结点，i称为ai在线性表中的________或______。对任意一对相邻结点ai、ai┼1(1<=i

6、size)error(“表满”)；if((i<1)

7、

8、(i>L.last+1))error(“非法位置”);for(j=L.last;j>=i;j--)______;L.data[i-1]=x;L.last=L.last+1;}4.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为________，量级是________。插入算法的平均时间复杂性为________，平均时间复杂性量级是________。115.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。voiddelete_sqlist(sq

9、listL,inti)/*删除顺序表L中的第i-1个位置上的结点*/{if((i<1)

10、

11、(i>L.last))error(“非法位置”)；for(j=i+1;j=L.last;j++)________;L.last=L.last-1;}126.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是________和________,其平均时间复杂性及其量级分别为________和________。7.线性表的常见链式存储结构有________、________