数据结构-java语言描述(下)ppt

《数据结构-java语言描述(下)ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构——Java语言描述(下)第七章树和二叉树第八章图第九章排序第十章查找第十一章哈希表第7章树和二叉树7.1树7.2二叉树7.3以结点类为基础的二叉树设计7.4二叉树类7.5二叉树的分步遍历7.6线索二叉树7.7霍夫曼树7.8树的遍历本章主要知识点：树的定义、表示方法和存储结构二叉树的定义、性质和存储结构，满二叉树和完全二叉树的概念二叉树的前序、中序、后序和层序遍历算法二叉树中序和层序游标类的设计方法线索二叉树的基本概念哈夫曼树和哈夫曼编码，哈夫曼编码的软件设计方法树与二叉树的转换，树的遍历7.1树7.1.1树的定义树是由n（n≥0）个结点构成的满足以下条件的结点

2、集合：（1）当n>0时，有一个特殊的结点称为根结点，根结点没有前驱结点；（2）当n>1时，除根结点外的其他结点被分成m（m>0）个互不相交的集合T1,T2,…,Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵结构和树结构类同的子树。树的示例：只有根结点的树一般的树结点：结点由数据元素和构造数据元素之间关系的指针组成。结点的度：结点所拥有的子树的个数称为该结点的度。叶结点：度为0的结点称为叶结点，叶结点也称作终端结点。分支结点：度不为0的结点称为分支结点，分支结点也称作非终端结点。孩子结点：树中一个结点的子树的根结点称作这个结点的孩子结点。双亲结点：若树中某结点有孩子结点，则这

3、个结点就称作它的孩子结点的双亲结点。兄弟结点：具有相同的双亲结点的结点称为兄弟结点。树的度：树中所有结点的度的最大值称为该树的度。结点的层次：从根结点到树中某结点所经路径上的分支数。树的深度：树中所有结点的层次的最大值称为该树的深度。无序树：树中任意一个结点的各孩子结点的排列没有严格次序的树称为无序树。有序树：树中任意一个结点的各孩子结点的排列有严格次序的树称为有序树。森林：m（m≥0）棵树的集合称为森林。7.1.2树的表示方法1直观表示法2形式化表示法树的形式化表示法主要用于树的理论描述。树的形式化表示法定义树T为T=（D，R）其中D为树T中结点的集合，R为树T中结点之间关系

4、的集合。当树T为空树时D=￠；当树T不为空树时有D={Root}∪DF，其中Root为树T的根结点，DF为树T的根Root的子树集合，DF可由下式表示：DF=D1∪D2∪…∪Dm（1≤i,j≤m,Di∩Dj=￠）3凹入表示法直观表示法B图的凹入表示：7.13树的抽象数据类型数据集合：树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。操作集合：（1）双亲结点parent()（2）左孩子结点leftChild()（3）右兄弟结点rightSibling()（4）遍历树traverse(vs)7.1.4树的存储结构1双亲表示法双亲表示法就是用指针表示出每个结点的双亲结

5、点。对于使用仿真指针的双亲表示法来说，每个结点应有两个域，一个是数据元素域，另一个是指示其双亲结点在数组中下标序号的仿真指针域。树及其使用仿真指针的双亲表示法2孩子表示法孩子表示法就是用指针表示出每个结点的孩子结点。常规指针的孩子表示法3双亲孩子表示法双亲孩子表示法就是用指针既表示出每个结点的双亲结点，也表示出每个结点的孩子结点。4孩子兄弟表示法孩子兄弟表示法就是用指针既表示出每个结点的孩子结点，也表示出每个结点的兄弟结点。7.2二叉树7.2.1二叉树的定义二叉树是n（n≥0）个结点构成的、每个结点最多只有两个子树的有序树。满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树

6、和右子树，并且所有叶子结点都在同一层上。完全二叉树：如果一棵具有n个结点的二叉树的逻辑结构与满二叉树的前n个结点的逻辑结构相同。两棵不同的二叉树满二叉树和完全二叉树7.2.2二叉树抽象数据类型数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。操作集合：（1）双亲结点parent()：（2）左孩子结点leftChild()（3）右孩子结点rightSibling()（4）左插入结点insertLeftNode(x)（5）右插入结点insertRightNode(x)：（6）左删除子树deleteLeftTree()（7）右删除子树deleteRigh

7、tTree()（8）遍历二叉树traverse(vs)7.2.3二叉树的性质性质1若规定根结点的层次为0，则一棵非空二叉树的第i层上最多有2i（i≥0）个结点。性质2若规定空二叉树树的深度为-1(即根结点的深度为0)，则深度为k的二叉树的最大结点数是2k+1-1（k≥-1）个。性质3具有n个结点的完全二叉树的深度k为不超过log2(n+1)-1的最大整数。性质4对于一棵非空的二叉树，如果叶结点个数为n0，度为2的结点数为n2，则有n0=n2+1。性质5对于具有n个结点的完全二叉树，如果按照从