数据结构第6章树和二叉树ppt课件.ppt

数据结构第 6 章树和二叉树 ppt 课件.ppt 1、第六章树和二叉树 6.1 树的类型定义 6.2 二叉树的类型定义和实现 6.3遍历二叉树和线索二叉树 6.4 树和森林 6.5Huffman 树与 Huffman 编码 1 对比树型结构和线性结构的结构特点第一个数据元素(无前驱)最终一个数据元素(无后继)其它数据元素(一个前驱、一个后继)根结点(无前驱)多个叶子结点(无后继)其它数据元素(一个前驱、多个后继)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~26.1 树的类型定义树是 n(n≥0)个结点的有限集 D，当 n≥1 时：1〕有一个特定的结点root 被称为根(结点 2、);2〕除根以外的结点被分成 m(m≥0)个不相交的有限集 T1,T2,……,Tm，其中每个集合又是一棵树，称为根的子树。ABCDEFGHIJMKL3 结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中全部结点的度的最大值度为零的结点度大于零的结点 DHIJM 树的基本术语(从根到结点的)路径：由从根到该结点所经分支和结点构成 4 孩子结点：结点的子树的根称为该结点的孩子双亲结点：B 结点是 A 结点的孩子，则 A 结点是 B结点的双亲兄弟结点：同一双亲的孩子之间互称兄弟堂兄弟结点：其双亲 3、在同一层的结点互称堂兄弟祖先结点：从根到该结点所经分支上的全部结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙 5 孩子结点双亲结点兄弟结点堂兄弟结点祖先结点子孙结点结点的层次:树的深度：ABCDEFGHIJMKL 假设根结点的层次为 1，第 L 层结点的子树的根结点层次为 L+1树中叶子结点所在的最大层次 6 有序树：子树之间存在确定的次序关系。最左边子树的根称为第一个孩子；最右边子树的根称为最终一个孩子。森林：是m〔m≥0〕棵互不相交的树的集合。ArootBCDEFGHIJMKLF 无序树：不考虑子树的 4、顺序。7 任何一棵非空树是一个二元组 Tree=〔root，F〕其中：root 被称为根结点 F 被称为子树森林森林和树之间的联系：一棵树去掉根后，其子树构成一个森林；一个森林增加一个根结点成为树。8ABCDEFGHIJMKL(A(B(E,F(K,L)),C(G),D(H,I,J(M))))T1T3T2 树根广义表树的表示方法：层次结构；1〕嵌套集合；2〕广义表；3〕凹入表示法 9ADTTree{数据对象 D：D 是具有相同特性的数据元素的集合。数据关系 R： 若 D 为空集，则称为空树； 若 D 中仅含一个数据元素，则关系 R 5、为空集； 否则 R={H}， (1)在 D 中存在唯一的称为根的数据元素root...