【数据结构】树与森林（一）

5.6.1 转换概述

• 树与二叉树之间、森林与二叉树之间可以相互转换，而且这种转换是一一对应的。
  

5.6.2 树转换成二叉树

• 树转换成二叉树可归纳3步骤：加线、删线、旋转
  

1. 加线：将树中所有相邻的兄弟之间加一条连线。
   
2. 删线：对树中的每一个结点，只保留它与第1个孩子结点之间的连线，删去它与其他孩子结点之间的连线。
   
3. 旋转：以树的根结点为轴心，将树平面顺时针旋转一定角度并做适当的调整，使得转化后所得二叉树看起来比较规整。
   

• 由树转换成的二叉树永远是一棵根结点的右子树为空的二叉树。
  

5.6.3 二叉树转换成树

• 二叉树转换成树是树转换二叉树的逆过程。
  
• 树转换成二叉树可归纳3步骤：加线、删线、旋转
  

5.6.4 森林与二叉树互转

• 森林是由若干树组成，任何一棵树和树对应的二叉树其右子树一定是空的。
  
• 根据这个规律可以得到森林转化成二叉树的方法：
  

1. 将森林中每棵树转化成二叉树。
   
2. 按照森林的先后顺序，将一颗二叉树视为前一棵二叉树的右子树依次链接起来，从而构成一颗二叉树
   

• 将二叉树转化成森林正好是这个过程相反。
  

5.6.5 树的存储结构

• 树的4种链式存放方式：

1. 双亲链表存储结构
   
2. 孩子链表存储结构
   
3. 双亲孩子链表存储结构
   
4. 孩子兄弟链表存储结构（重点掌握）
   

1）双亲链表存储结构

• 以一组地址连续的存储单元存放树中的各个结点，每个结点有两个域：

• 数据域：用于存放树中该结点的值。
  
• 指针域：用于存放该结点的双亲结点在存储结构中的位置。
  

• 优点：查找一个指定结点的双亲结点非常容易。
  
• 缺点：查找指定结点的孩子结点，需要扫描整个链表。
  

2）孩子链表存储结构

• 以一组地址连续的存储单元来存放树中的各个结点，每一个结点有两个域

• 数据域：存放该结点的值
  
• 指针域：用于存放该结点的孩子链表的头指针。
  

• 优点：便于实现查找树中指定结点的孩子结点
  
• 缺点：不便于查找指定结点的双亲结点
  

3）双亲孩子链表存储结构

• 与孩子链表存储结构类似，以一组地址连续的存储单元来存放树中的各个结点，每一个结点有三个域

• 数据域：存放该结点的值
  
• 父指针域：用于存放双亲结点在数组中的位置
  
• 子指针域：用于存放该结点的孩子链表的头指针。
  

4）孩子兄弟链表存储结构（重点掌握）

• 孩子兄弟链表存放，又称为“左子/右兄”二叉链式存储结构。

• 左指针：指向该结点的第一个孩子
  
• 右指针：指向该结点的右邻兄弟
  

结点类publicclassCSTreeNode {
publicObjectdata;                         //结点的数据域publicCSTreeNodefirstChild, nextsibling;   //左孩子、右兄弟}

5.6.6 树的遍历

• 数的遍历主要有：先根遍历、后根遍历、层次遍历。
  

1）先根遍历

• 若树为非空，则
  

1. 访问根节点
   
2. 从左到右依次先根遍历根节点的每一颗子树。
   

先根遍历序列：

ABEFCDGHIJK

publicvoidpreRootTraverse(CSTreeNodeT) {
if(T!=null) {
System.out.print(T.data);
preRootTraverse(T.firstChild);  //先根遍历树中根节点的第一个子树preRootTraverse(T.nextsibling); //先根遍历树中根节点的其他子树    }
}

2）后根遍历

• 若树为非空，则

1. 从左到右依次后根遍历根节点的每一棵子树
   
2. 访问根节点
   

后根遍历序列：

EFBCIJKHGDA

publicvoidpostRootTraverse(CSTreeNodet) {
if(T!=null) {
postRootTraverse(T.firstChild);     //后根遍历树中根节点的第一个子树System.out.print(T.data);           //访问数的根节点postRootTraverse(T.nextsibling);    //后根遍历树中根节点的其他子树    }
}