4.4 树、森林★3◎3

4.4 树、森林★3◎3

　　1．树具有的性质
　　性质1：树中的结点数等于所有结点的度数加1。
　　性质2：度为m的树中第i层上至多有个结点（i≥1）。
　　性质3：高度为h的m次树至多有个结点。
　　性质4：具有n个结点的m次树的最小高度为。
　　2．树的遍历运算
　　树的遍历运算是指按照某种方式访问树中的每一个结点且每一个结点只被访问一次，主要包括先根遍历和后根遍历两种。
　　（1）先根遍历
　　算法步骤为：
　　①访问根结点。
　　②按照从左到右的次序先根遍历根结点的每一棵子树。
　　（2）后根遍历
　　算法步骤为：
　　①按照从左到右的次序后根遍历根结点的每一棵子树。
　　②访问根结点。
　　当用二叉链表作为树的存储结构时，树的先根遍历与后根遍历可借用二叉树的先序遍历与中序遍历的算法来实现。
　　3．树的存储结构
　　主要包括双亲存储结构、孩子链存储结构，以及孩子兄弟链存储结构三种。
　　（1）双亲存储结构
　　用一组连续空间存储树的所有结点，同时在每个结点中附设一个伪指针指示其双亲结点位置，存储结构如下：
　　
　　这种存储结构利用了每个结点（根结点除外）只有唯一双亲的性质。在这种存储结构中，求某个结点的双亲结点十分容易，但求某个结点的孩子结点时需要遍历整个结构。
　　（2）孩子链存储结构
　　树中每个结点可能有多棵子树，它们可以用多重链表来表示，在每个结点设置多个指针域，其中每个指针指向一棵子树的根结点，链表中的结点可以是定长的，也可以是变长的，分别如图4-7中的（a）、（b）所示。
　　
　　另外的一种存储方法是将每个结点的孩子结点排列起来，形成一个线性表，且以单链表做存储结构，此时n个结点有n个孩子链表，n个头结点指针组成一个线性表。其存储结构如下：
　　
　　（3）孩子兄弟链存储结构
　　这种表示法又称为二叉链表表示法，用二叉链表做树的存储结构，每个结点设计3个域：一个数据元素域，一个指向该结点第一个孩子的指针，一个指向该结点下一个兄弟结点的指针。其存储结构如下：
　　
　　这种存储结构的最大优点是可方便地实现树和二叉树的相互转换；其缺点是从当前结点查找双亲结点比较麻烦，需要从树的根结点开始逐个结点比较查找。
　　4．森林的遍历运算
　　森林的遍历运算是指按照某种方式访问森林中的每一个结点且每一个结点只被访问一次，主要包括先序遍历和中序遍历两种。
　　（1）先序遍历森林
　　如森林非空，可按照下述规则遍历：
　　 访问森林中第一棵树的根结点；
　　 先序遍历第一棵树中根结点的子树森林；
　　 先序遍历除去第一棵树之后剩余的树所构成的森林。
　　（2）中序遍历森林
　　如森林非空，可按照下述规则遍历：
　　 中序遍历森林中第一棵树的根结点的子树森林；
　　 访问第一棵树的根结点；
　　 中序遍历除去第一棵树之后剩余的树构成的森林。
　　5．树、森林与二叉树的转换
　　（1）森林、树转换为二叉树
　　操作步骤如下：
　　①在所有相邻兄弟结点（森林中每棵树的根结点都可看成兄弟结点）之间加一水平连线。
　　②对每个非叶结点而言，除了它最左边的孩子结点外，删去它与其他孩子结点之间的连线。
　　③ 所有水平连线都以左边结点为轴心顺时针旋转45°。
　　树是森林的特殊情况，由于一般树的根结点不存在兄弟结点和相邻的树，所以对应二叉树的右子树为空。
　　（2）二叉树转换为森林、树
　　操作步骤如下：
　　①对二叉树中任一结点k1，沿着k1的右子树方向搜索所有的右孩子结点，得到结点序列k1、k2、…、km，其中ki+1是ki的右孩子结点，km没有右孩子结点；
　　②
　　③若有双亲结点 ，则连接 与 （2≤i≤m）；
　　④将图形规整化，使各结点按层次排列。