第六章树与森林.ppt

第六章树与森林*学****要点:树的递归定义和森林的基本概念。树与森林的存储结构。树与森林的遍历算法树、森林与二叉树的相互转换。*§、树的基本概念树(Tree)是一个由n(n≥0)个结点构成的有限集合T。①当n=0时,称T为“空树”。②当n≠0时,T中诸元素满足下述条件:●有且仅有一个特定数据元素没有前驱,称其为T的根结点。●除根结点外其余数据元素,又可分为m(0≤m<n)个互不相交的有限集合:T1,T2,…,Tm,每一个集合Ti(0≤i≤m)又是一棵树,称为根的子树。*、树的基本概念2树的特性:空树是树的一个特例;一棵非空树,至少有一个根结点,只有根结点的树为最小树;在有多个结点的树里,除根结点外,其余结点分属若干个子树,各子树间互不相交;除根结点外,树中其他结点有且只有一个前驱结点,但可以有零个或多个后继结点。、树的基本概念3有序树与无序树如果树T中各子树从左至右按照一定此序排列,不得互换,则称T是有序树(ordertree),否则为无序树(unordertree)。由此可知,二叉树是一种特殊的有序树,但不是一般树的特例。森林n(n≥0)棵互不相交的树的集合,称为森林(forest)。**、树的表示方法①树形表示法②文氏图表示法③凹入表示法④括弧表示法(A(B(D)(E(I)(J))(F))(C(G)(H)))*、结点结点的度:结点拥有的子树数目,即该结点的后继结点的个数结点的深度(层次):结点位于树的层次数树的度:一棵树中各结点度的最大值树的深度:一棵树中各结点深度的最大值结点间路径:从树中一个结点到另一个结点之间的分支路径长度:*2、结点分类(1)根结点:树T中没有前驱的结点称为T的根结点叶结点:树T中没有后继的点称为T的叶结点内部结点:树T中既有前驱又有后继的结点称为T的内部结点(2)分支结点:树T中度数不等于0的结点为T的分支结点非分支结点:*3、结点间关系描述子结点:树T中一个结点N的所有直接后继,都被称作是该结点N的子结点父结点:树T中把一个结点称作是它所有后继结点的父结点兄弟结点:在树T中,具有相同双亲的结点,互称为是兄弟结点堂兄弟结点:在树T中,双亲在同一层的那些结点,互称为是堂兄弟结点子孙结点:一个结点的子树中的所有结点,都被称作是该结点的子孙结点祖先结点:从根结点到某个结点的路径上的所有分支结点,称为该结点的祖先结点*§“由上到下”和“由左到右”的顺序做成一个结点序列,将该序列存放在一维数组Tr当中。Tr中每个元素(结点)都有一个Data域和一个Parent域,其中Data域存放结点数据,而Parent域存放结点的父结点在数组中下标。