第六章 树与二叉树－树和森林.ppt

第六章树与二叉树二叉树、树和森林
任课教师:代丽( dlzist@)
二叉树、树和森林
树的存储结构
树的存储结构有顺序结构和链表结构。
顺序存储结构即向量, 一般将树结点按自上而下, 自左至右的顺序一一存放。如完全二叉树就可以采用顺序存储结构。
对于一般树结构更适合使用链表存储结构。常用的有: 多叉链表和孩子-兄弟二叉链表。
下图所示的树是一个三叉树, 可用三重链表来存储, 其结点结构为: 有一个数据域和三个指针域, 指针域用于指向该结点的各个孩子。
该树的三重链表如图(a)所示。 孩子—兄弟链表如图(b)所示。
树与二叉树之间的转换
对于一般树, 树中孩子的次序并不重要, 只要双亲与孩子的关系正确即可。但在二叉树中, 左、右孩子的次序是严格区分的。所以在讨论二叉树与一般树之间的转换时, 为了不引起混淆, 就约定按树上现有结点次序进行转换。
1. 一般树转化为二叉树
将一般树转化为二叉树的思路, 主要根据树的孩子-兄弟存储方式而来, 步骤是: 
(1) 加线: 在各兄弟结点之间用虚线相链。可理解为每个结点的兄弟指针指向它的一个兄弟。
(2) 抹线: 对每个结点仅保留它与其最左一个孩子的连线, 抹去该结点与其它孩子之间的连线。可理解为每个结点仅有一个孩子指针, 让它指向自己的长子。
1. 一般树转化为二叉树
(3) 旋转: 把虚线改为实线从水平方向向下旋转45°, 成右斜下方向。原树中实线成左斜下方向。这样就形成一棵二叉树。
由于二叉树中各结点的右孩子都是原一般树中该结点的兄弟, 而一般树的根结点又没有兄弟结点, 因此所生成的二叉树的根结点没有右子树。
在所生成的二叉树中某一结点的左孩子仍是原来树中该结点的长子, 并且是它的最左孩子。
2. 二叉树还原为一般树
二叉树还原为一般树, 此时的二叉树必须是由某一树转换而来的没有右子树的二叉树。并非随便一棵二叉树都能还原成一般树。其还原过程也分为三步:
(1) 加线: 若某结点i是双亲结点的左孩子, 则将该结点i的右孩子以及当且仅当连续地沿着右孩子的右链不断搜索到所有右孩子, 都分别与结点i的双亲结点用虚线连接。
(2) 抹线: 把原二叉树中所有双亲结点与其右孩子的连线抹去。这里的右孩子实质上是原一般树中结点的兄弟, 抹去的连线是兄弟间的关系。
(3) 进行整理: 把虚线改为实线, 把结点按层次排列
森林与二叉树的转换
森林是树的有限集合。
1. 森林转换为二叉树
森林转换为二叉树的步骤为: 
(1) 将森林中每棵子树转换成相应的二叉树, 形成有若干二叉树的森林。
(2) 按森林图形中树的先后次序, 依次将后边一棵二叉树作为前边一棵二叉树根结点的右子树, 这样整个森林就生成了一棵二叉树, 实际上第一棵树的根结点便是生成后的二叉树的根结点。
2. 二叉树还原为森林
将一棵由森林转换得到的二叉树还原为森林的步骤是: 
(1) 抹线: 将二叉树的根结点与其右孩子的连线以及当且仅当连续地沿着右链不断地搜索到的所有右孩子的连线全部抹去, 这样就得到包含有若干棵二叉树的森林。
(2) 还原: 将每棵二叉树按二叉树还原一般树的方法还原为一般树, 于是得到森林。
这部分的图示, 请自己练****画出。
一般树或森林的遍历
一般树的遍历主要是先序和后序遍历。
树的先序遍历首先访问树的根结点, 然后从左至右逐一先序遍历每一棵子树。
树的后序遍历首先后序遍历树的最左边的第一棵子树, 接着从左至右逐一后序遍历每一棵子树, 最后访问树的根结点。
由于一般树转换为二叉树后, 此二叉树没有右子树, 对此二叉树的中序遍历结果与上述一般树的后序遍历结果相同。因此, 有时候把一般树的后序遍历称为中序遍历。