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

数据结构树和二叉树 ppt 课件.ppt 1、第 6 章树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 6.1 树的定义和基本术语 1.树的规律定义是由 n(n≥0)个结点组成的有限集合 T。在任意一个非空树中：有且仅有一个特定的称为根的结点；n1 时，其余结点可以分为 m〔m0〕个互不相交的有限集 T1,T2,T3,…,Tm，其中每一个集合本身又是一棵树，且称为根的子树。树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它说明了树的特性。如在右图中，是只有一个根结点的树是有13 个结点的树其中 A 是根，其余结点分成三个互不相交的子集：T1={B，E，F，K，L},T2={C，G},T3={D，H，I，J，M} 2、；T1,T2,T3 都是 A 的子树，且本身也是一棵树。则同理按此分析方式分析 T1,T2,T3。AABCDEFGHIJKLM2.树的其它表示方法嵌套集合：是一些集合的集体，对于其中任何两个集合，或不相交，或一个包含另一个的形式表示。广义表表示：根作为由子树森林组成的表的名字写在表的左边。凹入表示：类似书的编目。GCABDHIJEKFLA*****************B****************E***************F***************K**************L**************C****************G***************D****************H******** 3、*******I***************J***************(A(B(E,F(K,L)),C(G),D(H,I,J)))ABCDEFGHIJKL3.树的基本术语结点：数据元素+若干指向其子树的分支；结点的度：结点拥有的子树数；树的度：树中全部结点的度的最大值；叶子结点：度为零的结点，或称为终端结点；分支结点：度大于零的结点，或称为非终端结点；结点的层次：假设根结点的层次为 1,若某结点在第 i 层，则其子树的根在第 i+1 层；ABDEFHIJKM 树的深度：树中叶子结点所在的最大层次；孩子结点：结点的子树的根；相应地该结点称为孩子的双亲结点；兄弟结点：同一个双亲的孩子之间称为兄弟结点；祖先：从根到该结点所经分支上的全部结点；子孙： 4、子树中任一结点；ABDEFHIJKM3.树的基本术语有序树、无序树子树之间是否存在次序关系？将树中结点的各子树看成从左至右是有次序的(即不能互换)称有序树，否则称无序树；森林：是 m〔m≥0〕棵互不相交的树的集合。任何一棵非空树是一个二元组 Tree=〔root，F〕其中：root 被称为根结点，F 被称为子树森林；ABDEFHIJKM3.树的基本术语 4.树结构和线性结构的...