《数据结构 第五章教学课件 .ppt》由会员分享，可在线阅读，更多相关《数据结构 第五章教学课件 .ppt（88页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构 第五章教学课件 第五章 树和二叉树数据结构目录4123 树的定义和基本术语二叉树二叉树遍历树和森林5二叉树的应用第五章第五章树和二叉树树和二叉树总体要求了解树的定义和基本术语；了解树及二叉树的存储结构；重点掌握二叉树的结构特性及相应的证明方法；掌握二叉树的各种遍历算法；掌握树和二叉树之间的转换；了解最优树的特性；了解Huffman树、编码的实现及应用。了解二叉排序树及其应用与实现5.1树的定义和基本术语u5.1.1树的定义树（树（TreeTree）是若干个结点组成的有限集合，其中）是若干个结点组成的有限集合，其中必须有一个结点是必须有一个结点是根结点根结点，其余结点划分为若干个，其余
2、结点划分为若干个互互不相交的集合不相交的集合，每一个集合还是一棵树，称为根的，每一个集合还是一棵树，称为根的子子树树。注意，当树的结点个数为0时，我们称这棵树为空树，记为。AB CDFHEIG例5.1A是根；其余数据元素分成两个互不相交的子集，T1=B,D,E,F,H,I；T2=C,G；T1,T2都是根A的子树，且本身也是一棵树。可继续向下分为更小的子树，直到每棵子树只有一个根结点为止。根结点T1T2ACGB DE FK LHMI J例如A只有根结点的树有13个结点的树根结点T1T3T21、树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。2、树中所有结点可以有零个或多个后继
3、结点。只有根结点的树。树具有以下两个特点：思考：下面三个结构是否是树结构？u5.1.2树的表示方法1.直观表示法2.嵌套集合表示法3.凹入表示法4.广义表表示法u5.1.3树的术语1层2层4层3层height=4ACGBDE FK LHMI J 结点结点 结点的度结点的度 叶子结点叶子结点 分支结点分支结点 孩子结点孩子结点 父亲结点父亲结点 兄弟结点兄弟结点 祖先结点祖先结点 树的度树的度 结点的层次结点的层次 树的深度树的深度 森林森林有序树 子树之间存在确定的次序关系无序树 子树之间不存在确定的次序关系家族树就属于有序树。森林森林是m(m0)棵互不相交的树的集合rootroot给森林中的
4、各子树加上一个父亲结点，森林就变成了树。T3T2T1ABE FK LDHMI JCGCG5.2二叉树u5.2.1二叉树基本概念二叉树二叉树（BinaryTreeBinaryTree）是一种）是一种每个结点最多拥有每个结点最多拥有22个子树个子树的树结构，其中第的树结构，其中第11个子树被称为左子树，第个子树被称为左子树，第22个子树被称为右子树。个子树被称为右子树。BDEGHCIFA根结点右子树左子树交换之后就是另一棵不同的二叉树(a)空二叉树(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树二叉树的五种基本形态（11）满二叉树）满二叉树在一棵二叉树中，如果在一棵二叉树中
5、，如果所有分支结点都存在左子树和所有分支结点都存在左子树和右子树右子树，并且，并且所有叶子结点都在同一层上所有叶子结点都在同一层上，这样的一，这样的一棵二叉树称作满二叉树。棵二叉树称作满二叉树。（22）完全二叉树）完全二叉树完全二叉树是一种完全二叉树是一种叶子结点只能出现在最下层和次下叶子结点只能出现在最下层和次下层层且且最下层的叶子结点集中在树的左边最下层的叶子结点集中在树的左边的特殊二叉树。的特殊二叉树。总结：1、完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。2、深度为k的完全二叉树在k-1层上一定是满二叉树。u5.2.2二叉树的性质性质1：一棵非空在二叉树的第i层上至
6、多有2i1个结点(i 1)。证明：当i=1时，只有根结点，2i-1=20=1。假设对所有j，ij 1，命题成立，即第j层上至多有2j-1个结点。由归纳假设第i-1层上至多有2i2个结点。二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i2=2i-1。性质2：一棵深度为k的二叉树中，最多具有2k1个结点。证明：性质1可见，深度为k的二叉树的最大结点数为20+21+2k-1=2k-1性质3：对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:n0n21。证明：n=n0+n1+n2e=n1=2n2+n1因此，2n2+n1=n0+n1+n2-1n0=n2+1