第6章树和二叉树练习.ppt

《第6章树和二叉树练习.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构主讲：张荣梅2004年9月第6章树和二叉树第6章树和二叉树第6章树和二叉树知识点1、二叉树及二叉树的存储结构2、二叉树的遍历3、树的基本概念树的遍历4、哈夫曼树难点1、二叉树遍历算法的设计2、修改二叉树遍历算法，进行二叉树其它相关的操作，解决实际应用问题第6章树和二叉树第6章树和二叉树（要求）1.熟练掌握二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.熟练掌握各种遍历策略的递归和非递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。

2、4.熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握1至2种建立二叉树和树的存储结构的方法。6.学会编写实现二叉树的各种操作的算法。7.掌握建立哈夫曼编码的方法。第6章树和二叉树第6章树和二叉树目录6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用小结习题与练习第6章树和二叉树

3、6.1树的定义和基本术语一、树的定义二、树的抽象数据类型定义三、树的基本术语第6章树和二叉树一、树的定义非线性数据结构：结构（定义）中至少存在一个结点，它不只一个前驱或后继；树形结构是一类重要的非线性结构，其中以二叉树最为常用；树形结构是结点间有分支的、层次的关系的结构；树形结构特点：每个结点可有不止一个直接后继，除根外的所有结点都有且只有一个直接前驱；树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构等都可用树来形象表示。第6章树和二叉树树的图示：张一张四张三张五张六张二第6章树和二叉树一、树的定义树（Tree）（递归定义）：树是n（n≥

4、0）个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、…、Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。说明：树中，每个结点被定义为它的每个子树的根结点的前驱，它的每个子树的根结点为它的后继。第6章树和二叉树一、树的定义树的表示形式：（1）树形表示法：（最常用）ECFAAMGBDH（b）一般的树ILKJ（a）只有根结点的树第6章树和二叉树树的表示（2）嵌套集合表示法：（集合的集体，对于任两个集合，或不相交，或一个包含另

5、一个）ABFEKLDHMJICG第6章树和二叉树树的表示（3）广义表：根作为由子树森林组成的表的名字写在表的左边。(A(B(E(K,L),F),C(G),D(H(M),I,J)))ECFAMGBDHILKJ请对比...第6章树和二叉树树的表示（4）凹入表示法：ECFAMGBDHILKJABEKLF请对比...CGDHMIJ第6章树和二叉树二、抽象数据类型树的定义抽象数据类型树的定义：（P118-119）第6章树和二叉树三、树的基本术语1、结点2、结点的度(Degree)3、叶子(Leaf)（终端结点）4、分支结点（非终端结点）5、内部结点6、树的度7、

6、孩子(Child)、双亲(Parent)8、兄弟(Sibling)9、祖先、子孙10、结点的层次(Level)11、堂兄弟12、树的深度(Depth)13、有序树、无序树14、森林(Forest)第6章树和二叉树6.2二叉树一、二叉树的定义二、二叉树的性质三、二叉树的存储结构第6章树和二叉树一、二叉树的定义1、二叉树（BinaryTree）：每个结点至多只有两棵子树的树型结构。特点：（１）不存在度大于２的结点；（２）子树次序不能颠倒，有左右之分。（３）与一般树的区别：当只有一个孩子结点时，二叉树区分左右顺序，一般树不区分。2、二叉树的抽象数据类型定义（

7、P121-123）第6章树和二叉树一、二叉树的定义3、二叉树的五种基本形态空二叉树仅有根结点的二叉树右子树为空的二叉树左、右子树均非空的二叉树左子树为空的二叉树第6章树和二叉树二、二叉树的性质性质1在二叉树的第i层上至多有2i-1个结点(i≥1)。性质2深度为k的二叉树至多有2k-1个结点(k≥1)。证明：由性质１得：最多的结点数（每一层为最大结点数）：2０＋21＋2２＋…＋2k-1＝2k-1（等比数列求和）性质3对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1第6章树和二叉树二、二叉树的性质完全二叉树和满二叉树满二叉

8、树：一棵深度为k且有2k-1个结点的二叉树。特点：每一层上的结点数都是最大结点数。可以对满二叉