数据结构-树和森林的表示和遍历.ppt

树和森林的表示方法和遍历 树和森林的遍历 树的表示方法 小结和作业 森林和二叉树的对应关系 一 双亲表示法 二 孩子链表表示法 三 带双亲的孩子链表表示法 树的存储结构 四 树的孩子兄弟表示法 双亲表示法 用一组连续空间存储树的结点 同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置 双亲表示法 root 0n 7 0A1B2C3D4E5F6G data 1 0 0 0 2 2 5 parent 双亲表示法 defineMAX TREE SIZE100 结点结构 C语言的类型描述 typedefstructPTNode TElemTypedata intparent 双亲位置域 PTNode 双亲表示法 typedefstruct PTNodenodes MAX TREE SIZE intr n 根结点的位置和结点个数 PTree 树结构 孩子链表表示法 1 结点同构 结点的指针个数相等 为树的度k 这样n个结点度为k的树必有n k 1 1个空链域 1 多重链表 每个结点有多个指针域 分别指向其子树的根 孩子链表表示法 2 结点不同构 结点指针个数不等 为该结点的度d 2 孩子链表 每个结点的孩子结点用单链表存储 再用含n个元素的结构数组指向每个孩子链表 孩子链表表示法 root 0n 7 data 0A1B2C3D4E5F6G firstchild 孩子链表表示法 typedefstructCTNode intchild structCTNode nextchild ChildPtr 孩子结点结构 C语言的类型描述 孩子链表表示法 typedefstruct TElemTypedata ChildPtrfirstchild 孩子链的头指针 CTBox 双亲结点结构 孩子链表表示法 typedefstruct CTBoxnodes MAX TREE SIZE intn r 结点数和根结点的位置 CTree 树结构 带双亲的孩子链表表示法 1 双亲表示法 PARENT T x 可以在常量时间内完成 但是求结点的孩子时需要遍历整个结构 2 孩子链表表示法 适于那些涉及孩子的操作 却不适于PARENT T x 操作 3 将双亲表示法和孩子链表表示法合在一起 可以发挥以上两种存储结构的优势 称为带双亲的孩子链表表示法 带双亲的孩子链表表示法 root 0n 7 Parent 0A1B2C3D4E5F6G 1 0 0 0 2 2 5 data firstchild 树的孩子兄弟存储表示法 树的孩子兄弟存储表示法 又称为二叉树表示法 以二叉链表作为树的存储结构 结点结构 firstchilddatanextsibling 指向第一个孩子结点 指向下一个兄弟结点 树的孩子兄弟存储表示法 typedefstructCSNode TElemTypedata structCSNode firstchild nextsibling CSNode CSTree C语言的类型描述 树的孩子兄弟存储表示法 A B C D E F G root A B C D E F G 森林和二叉树的对应关系 树与二叉树的对应关系 给定一棵树 通过树的二叉链表表示法可以找到唯一的一棵二叉树与之对应 树的二叉链表的右子树一定是空的 森林与二叉树的对应关系 将森林中的第二棵树看成第一棵树的兄弟即可 森林和二叉树的对应关系 T1 T2 Tn 森林和二叉树的对应关系 由森林转换成二叉树的转换规则为 若F 则B 由ROOT T1 对应得到Node root 否则 由 t11 t12 t1m 对应得到LBT 由 T2 T3 Tn 对应得到RBT 森林和二叉树的对应关系 森林转换成二叉树 先将森林中的所有树转换成二叉树 森林和二叉树的对应关系 以第一棵二叉树的根为树根 将森林中所有的二叉树转换成一棵二叉树 A 森林和二叉树的对应关系 由二叉树转换为森林的转换规则为 由LBT对应得到 t11 t12 t1m 若B 则F 否则 由Node root 对应得到ROOT T1 由RBT对应得到 T2 T3 Tn 森林和二叉树的对应关系 二叉树转换成森林 1 抹线 将二叉树中根结点与其右孩子连线 及沿右分支搜索到的所有右孩子间连线全部抹掉 使之变成孤立的二叉树 2 还原 将孤立的二叉树还原成树 森林和二叉树的对应关系 1 断开二叉树中右分支中搜索到的所有右孩子间的连线 森林和二叉树的对应关系 2 将得到的二叉树全部还原成树 A B C D G H I J 森林和二叉树的对应关系 由树 森林和二叉树的相互转换可知 树和森林的各种操作均可与二叉树的各种操作相对应 不过 和树对应的二叉树 其左 右子树的概念已改变为 左子树是孩子 右子树是兄弟 树和森林的遍历 一 树的遍历 二 森林的遍历 三 树的遍历的应用 树的遍历 先根 次序 遍历 先根 次序 遍历 若树不空 则先访问根结点 然后依次先根遍历各棵子树 A BEF C DGHIJK 先根 次序 遍历序列为 树的遍历 后根 次序 遍历 后根 次序 遍历 若树不空 则先依次后根遍历各棵子树 然后访问根结点 A EFB C IJKHGD 后根 次序 遍历序列为 树的遍历 按层次遍历 按层次遍历 若树不空 则自上而下自左至右访问树中每个结点 A BCD EFG 按层次遍历序列为 H IJK 树的遍历 树的二叉树表示 树先根遍历ABEFCDG 因此 树的先根遍历结果与其对应二叉树表示的先序遍历结果相同 树的遍历 树的二叉树表示 树后根遍历EFBCGDA 因此 树的后根遍历结果与其对应二叉树表示的中序遍历结果相同 森林的遍历 1 森林中第一棵树的根点 2 森林中第一棵树的子森林 3 森林中其它树构成的森林 森林可以分解成三部分 森林的遍历 先序遍历 若森林不空 则1 访问森林中第一棵树的根结点 即 依次从左至右对森林中的每一棵树进行先根遍历 2 先序遍历森林中第一棵树的子树森林 3 先序遍历森林中 除第一棵树之外 其余树构成的森林 先根遍历序列为 A BCDE FG HIKJ 森林的遍历 先序遍历 森林对应的二叉树 森林的遍历 中序遍历 森林不空 则中序遍历森林中第一棵树的子树森林 即 依次从左至右对森林中的每一棵树进行后根遍历 访问森林中第一棵树的根结点 中序遍历森林中 除第一棵树之外 其余树构成的森林 中序遍历序列为 A BCED GF KIJH 森林的遍历 中序遍历 树的遍历与二叉树遍历的对应关系 先根遍历 后根遍历 树 二叉树 森林 先序遍历 先序遍历 中序遍历 中序遍历 树的遍历的应用 设树的存储结构为孩子兄弟链表 typedefstructCSNode TElemTypedata structCSNode firstchild nextsibling CSNode CSTree 一 求树的深度 二 输出树中所有从根到叶子的路径 三 建立树的存储结构 树的遍历的应用 一 求树的深度的算法 1 如果T为空 则树的深度为0 2 求出T每棵子树的深度 3 从所有子树的深度中取最大 然后加1 即为树的深度 树的遍历的应用 intDepth TreeT 只考虑逻辑结构 if T return 0 for p T1 T2 Tn 每棵子树 d p Depth p a max d 1 d 2 d n return a 1 树的遍历的应用 intDepth CSTreeT 二叉链表作为存储结构 if T return0 空树 p T firstchild d 0 while p 依次求子树的深度 return d 1 d1 Depth p if d1 d d d1 p p nextsibling 树的遍历的应用 intDepth CSTreeT if T return0 d1 Depth T firstchild d2 Depth T nextsibling return max d1 d2 d1 d1 1 树的遍历的应用 二 输出树中所有从根到叶子的路径的算法 对左图所示的树 其输出结果应为 ABEABFACADGHIADGHJADGHK 树的遍历的应用 对树先根遍历 深度优先 1 T为空 栈中存放的是从根到T的父结点的路径 2 将T压栈 栈中存放的是从根到T的路径 3 递归访问T的子树 4 将T出栈 树的遍历的应用 voidAllPath CSTreeT Stack S 树的先根遍历 AllPath Push S T data 树根压栈 p T firstchild T的第一颗子树 while p T的所有子树AllPath p S p p nextsibling Pop S 访问完T的所有子树 if T PrintStack S return 树的遍历的应用 voidOutPath CStreeT Stack S Push S T data OutPath T firstchild S OutPath T nextsibling S if T return 利用二者的先序遍历结果相同 if T firstchild 叶子 节点printStack S pop S 树的遍历的应用 三 建立树的存储结构的算法 和二叉树类似 不同的定义相应有不同的算法 假设以二元组 F C 的形式自上而下 自左而右依次输入树的各边 建立树的孩子 兄弟链表 树的遍历的应用 对左侧所示树的输入序列应为 A A B A C A D C E C F E G A A B A C A D C E A B C D 可见 算法中需要一个队列保存已建好的结点的指针 树的遍历的应用 voidCreatTree CSTree 所建为根结点else 非根结点的情况 for CreateTree 树的遍历的应用 GetHead Q s 取队列头元素 指针值 while s data fa 查询双亲结点DeQueue Q s GetHead Q s if s firstchild s firstchild p 链接第一个孩子结点else r s firstchil