访问第一棵树的根结点.pptVIP

上次课回顾 二叉树遍历的定义 二叉树遍历的递归算法与非递归算法 线索二叉树的定义及遍历 二叉树的线索化 6.4 树和森林 【本节主要内容】 树的存储结构 森林与二叉树的转换 树和森林的遍历 【教学要求】 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。 6.4.1 树的存储结构 1. 双亲表示法 实现：定义结构数组来存放树的结点， 每个结点含两个域： 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难 树的双亲表存储表示： # define MAX_TREE_SIZE 100 typedef struct PTNode { //结点结构 TElemType data; int parent; //保存双亲位置 } PTNode; typedef struct { //树结构 PTNode nodes[MAX_TREE_SIZE]; int r, n; //根的位置和结点数 } PTree; 2. 孩子表示法 多重链表：每个结点有多个指针域，分别指向其子树的根 结点同构：结点的指针个数相等，为树的度D 结点不同构：结点指针个数不等，为该结点的度d 3. 孩子兄弟表示法（二叉树表示法） 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点 特点： 操作容易 破坏了树的层次 6.4.2 森林、树与二叉树转换 由二叉树转换为森林的转换规则 　若 B = Φ, 则 F = Φ; 否则，由 Node(root) 对应得到 ROOT( T1 );由LBT 对应得到 ( t11, t12, …，t1m); 由RBT 对应得到 (T2, T3, …, Tn)　 由此，树的各种操作均可对应到二叉树的操作来完成换言之，和树对应的二叉树，其左、右子树的概念改变成：左是孩子，右是兄弟。 （1）树与二叉树转换 （3）森林转换成二叉树 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构 6.4.3 树和森林的遍历 树的遍历：按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列 常用方法： 先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树 后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点 按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点 先根遍历 后根遍历 ABEHIJCDFGK HIJEBCFKGDA 森林的遍历 先序遍历森林 若森林非空,则可按下述规则遍历: 访问森林中第一棵树的根结点; 先序遍历第一棵树中根结点的子树森林; 先序遍历除去第一棵树之后剩余的树构成的森林. 中序遍历森林 若森林非空,则可按下述规则遍历: 中序遍历森林中第一棵树的根结点的子树森林; 访问第一棵树的根结点; 中序遍历除去第一棵树之后剩余的树构成的森林。 小 结 树的三种存储结构 双亲表示法 孩子链表表示法 孩子兄弟表示法 森林和二叉树的转换 由森林转换为二叉树 由二叉树转换为森林 树和森林的遍历 树的先根遍历（= 二叉树的先序遍历） 树的后根遍历（= 二叉树的中序遍历） 森林的先序遍历（= 二叉树的先序遍历） 森林的中序遍历（= 二叉树的中序遍历） * 数据结构 data parent PTNode data parent …… data parent PTNode [0] [1] … … [98] [99] n PTree a b c d e f h g i a c d e f g h i b -1 0 1 1 2 4 4 4 0 6 0 1 2 3 4 5 7 8 .. 99 data parent 如何找孩子结点 9 data child1 child2 ………. childD data degree child1 child2 ………. childd 所有结点同构，d为树的度，由于树中许多结点的度小于d，故会造成空链域浪费 所有结点不同构，d为结点的度，存储空间节省，但操作不方便 孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表。 typedef struct CTNode {　　　/