树和森林的定义

树的定义

树的含有n个结点的有限集合，在任意一棵非空树中：

  • 有且仅有一个特定的根结点
  • 当n>1时，其余结点可分为m个互不相交的有限集T1,T2…,Tn，其中每个集合本身也是一棵树，并且是根结点的子树

image.png

森林的定义

森林是m(m>=0)棵互不相交的树的集合，可记作F=(T1,T2,…,Tn)。对于书的结点而言，其子树的集合即为子树森林。
image.png

双亲表示法

在树中，除了根结点外，其它结点的双亲都是唯一确定的。根据这一特征，可以用数组存储树中结点的值及其双亲结点的位置。数组的每个元素都含有两个域：数值域data和双亲的位置parent。如果数值域是根结点，那么parent域为-1。如图所示：
image.png

  1. /* 树的双亲表法结点结构定义*/
  2. #define MAX_TREE_SIZE 100
  3. typedef int  ElemeType;
  5. typedef struct PTNode{ // 结点结构
  6.     ElemeType data; //结点数据
  7.     int parent;    // 双亲位置
  8. }PTNode;
  10. typedef struct { // 树结构
  11.     PTNode nodes[MAX_TREE_SIZE];   // 结点数组
  12.     int r; // 根的位置
  13.     int n; // 结点数
  14. }PTree;

双亲孩子表示法

双亲孩子表示法是双亲表示法的扩展，双亲表示法可以很快的定位到双亲结点，但是很难定位到孩子节点，而双亲孩子表示法则可以弥补这一缺陷，既能很快定位到双亲结点，也能很快地定位到孩子结点。它地操作是在原来地数据结构上加上一个指针域，这个指针指向一个链表，这个链表存储地是该结点的孩子。如图所示：
image.png

  1. /* 树的双亲孩子表示法结构定义*/
  2. #define MAX_TREE_SIZE 100
  3. typedef int  ElemeType;
  5. typedef struct CTNode{  // 孩子结点
  6.     int child;  // 孩子结点的下标
  7.     struct CTNode * next;  // 指向下一结点的指针
  8. }*ChildPtr;
  10. typedef struct {  // 表头结构
  11.     ElemeType data;  // 存放在数中的结点数据
  12.     int parent;      // 存放双亲的下标
  13.     ChildPtr firstchild;  // 指向第一个孩子的指针
  14. }CTBox;
  16. typedef struct {  // 树结构
  17.     CTBox nodes[MAX_TREE_SIZE]; // 结点数组
  18.     int r;  // 根的位置
  19.     int n;  // 结点树
  20. }CTree;

孩子兄弟表示法

对于一个结点而言，如果在它的最左孩子和右边的第一个兄弟结点存在前提下，则它的最左孩子和右边第一个兄弟结点都是唯一的。按照这个唯一性，可以设置一个指针指向它的最左孩子，另一个指针指向它的兄弟结点的链表。如图所示：
image.png

  1. /* 树的孩子兄弟表示法结构定义*/
  2. #define MAX_TREE_SIZE 100
  3. typedef int  ElemeType;
  5. typedef struct CSNode{
  6.     ElemeType data;
  7.     struct CSNode * firstchild;
  8.     struct CSNode * rightsib;
  10. }CSNode, *CSTree;

注意： 上面三种存储结构应该根据使用场景并结合其数据结构的特点来合理使用

树、森林与二叉树的转化

二叉树和树的转化

树转二叉树

由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。将树转换成二叉树的步骤是：

  1. 在所有兄弟结点之间加一条连线
  2. 对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线
  3. 以树的根结点为轴心，将整棵树顺时针旋转一定角度(45°)，使之结构层次分明。

image.png

二叉树转树

二叉树转换为树是树转换为二叉树的逆过程，其步骤是：

  1. 若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来
  2. 删除原二叉树中所有结点与其右孩子结点的连线
  3. 整理前两步得到的树，使之结构层次分明

image.png

二叉树和森林的转化

森林转二叉树

森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。将森林转换为二叉树的步骤是：

  1. 先把每棵树转换为二叉树
  2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树

image.png

二叉树转森林

二叉树转森林就是森林转二叉树的逆过程，其步骤如下：

  1. 先将二叉树的右孩子的右孩子的右孩子…..之间的连线取消
  2. 依据二叉树转树的规则将上一步出来的几颗二叉树转成树
  3. 整理格式

参考文章： https://blog.csdn.net/linraise/article/details/11745559