数据结构 （C语言版）课件：第6章_树和二叉树.pptVIP

二叉树遍历 6.4.1 树的存储结构 ● 双亲表示法 6.4 树的存储结构及操作实现 ? 主要特点 这种存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，适合求指定结点的双亲或祖先（包括根）的操作。但如果求指定结点的孩子或其他后代时，则需要遍历整个结构。 因为树中各结点的度不同，所以结点指针域的设置有两种方法。 为结点的度，degree 域的值等于 ，该存储结构节约了存储空间。但由于每个结点的孩子链域数不同，造成每个结点不同构，因此给操作的实现带来了困难。 树的多重链表就是每个结点中包含多个指针域，其中每个指针指向一个孩子，即一棵子树的根结点。 指针域的个数等于该结点的度。 指针域的个数等于整个树的度。 6.4.1 树的存储结构 6.4 树的存储结构及操作实现 ● 孩子表示法 ? 多重链表定义 d 为树的度。因为树中很多结点的度都小于 d，所以链表中有很多空链域，造成存储空间比较浪费。 设树的度为 k，结点数为 n，那么该树空链域的个数为 n(k–1)+1。因此，树的度越大，空链域越多，造成的空间浪费越大。 把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作为存储结构，则 n 个结点有 n 个孩子链表，叶子的孩子链表为空表；而 n 个头指针又组成一个表头线性表，为了便于查找，采用顺序存储结构按层序存储。采用这种存储结构的树称为孩子链表。 6.4.1 树的存储结构 6.4 树的存储结构及操作实现 ● 孩子表示法 ? 孩子链表定义 6.4.1 树的存储结构 6.4 树的存储结构及操作实现 ● 孩子表示法 ? 类型定义 6.4.1 树的存储结构 6.4 树的存储结构及操作实现 ● 孩子表示法 ? 主要特点 这种存储结构表示了树中孩子结点的信息及孩子兄弟结点之间的关系，适合求指定结点的孩子及孩子兄弟的操作。但如果求指定结点的双亲或祖先（包括根），则需要遍历整个结构。 ● 双亲孩子表示法 在树的孩子链表的表头结点结构中增加一个双亲域，即将树的双亲顺序表与树的孩子链表结合起来。采用这种存储结构的树称为双亲孩子链表。 6.4.1 树的存储结构 6.4 树的存储结构及操作实现 ? 定义 双亲孩子链表表头结点结构 双亲孩子链表孩子结点结构 ● 双亲孩子表示法 6.4.1 树的存储结构 6.4 树的存储结构及操作实现 ? 类型定义 ● 双亲孩子表示法 6.4.1 树的存储结构 6.4 树的存储结构及操作实现 ? 主要特点 这种存储结构不仅表示了树中结点的双亲信息，也表示了孩子信息及孩子兄弟及孩子兄弟结点之间的关系，适合求指定结点的双亲或祖先的操作，也适合求指定结点的孩子的操作。 ● 孩子兄弟表示法 链表中的结点是同构的，每个结点除了数据域外，还设置了两个指针域，分别指向该结点的第一个孩子和下一个兄弟。采用这种存储结构的树称为孩子兄弟链表，又称为二叉链表。 6.4.1 树的存储结构 6.4 树的存储结构及操作实现 ? 定义 孩子兄弟链表结点结构 ● 孩子兄弟表示法 6.4.1 树的存储结构 6.4 树的存储结构及操作实现 ? 类型定义 ● 孩子兄弟表示法 6.4.1 树的存储结构 6.4 树的存储结构及操作实现 ? 主要特点 这种存储结构最大优点就是结点结构统一。利用这种存储结构易于实现查找结点等操作；但如果要查找某结点的双亲，则需遍历整个结构。若在结点中增设一个双亲域，则方便双亲操作。 6.4 树和森林 由于树和二叉树都可以采用二叉链表作为存储结构，那么以二叉链表作为媒介就可以导出树与二叉树之间的对应关系。从存储结构上看，树与二叉树的二叉链表是相同的，只是逻辑解释不同而已。 6.4 树和森林 6.4.1 树与二叉树的转换 ● 树转换为二叉树 ● 加线：在各兄弟结点间加一连线，将其隐含的 “兄-弟” 关系以 “父-右子” 关系显示表示出来； ● 抹线：对于任何结点，除了其最左边孩子外，抹掉该结点与其他孩子间的 “父-子” 关系； ● 调整：以树根作为二叉树根，将其与其最左孩子间 “父-子” 关系改为 “父-左子” 关系，且将各结点按二叉树层次排列。 6.4 树和森林 6.4.1 树与二叉树的转换 ● 树转换为二叉树 6.4 树和森林 经过该方法转换后对应的二叉树是唯一的，并具有以下特点：