本文主要是对普通树的存储结构、树与森林与二叉树之间的转换的总结笔记，以及学习一下回溯法和试探求最优解的方法。

树的存储结构

双亲表示法

  1. 连续空间存储树的结点。
  2. 结点中附设指示器指示双亲结点在空间中的位置。

缺点：求结点的孩子时需要遍历整个结构。

#define MAX_TREE_SIZE 100
typedef struct PTNode  // 结点结构
{
    int data;
    int parent;  // 双亲位置
} PTNode;

typedef struct  // 树结构
{
    PTNode nodes[MAX_TREE_SIZE];
    int r, n;  // 根的位置和结点数
} PTree;

孩子表示法

  1. 将每个结点的孩子结点排列起来，看成一个线性表，且以单链表作为存储结构，则 $n$ 个结点有 $n$ 个孩子链表。
  2. $n$ 个头指针组成线性表，可以采用顺序存储结构。

缺点：不适合查找父结点的操作。

// 树的孩子链表表示法
typedef struct CTNode  // 孩子结点
{
    int child;  // 指向孩子结点在头指针的线性表中的位置
    struct CTNode* next;
}* ChildPtr;
typedef struct
{
    int data;
    ChildPtr firstchild;  // 孩子链表表头指针
} CTBox;
typedef struct
{
    CTBox nodes[MAX_TREE_SIZE];  // 头指针组成的线性表
    int n, r;                    // 结点树和根的位置
} CTree;

可以将双亲表示法和孩子表示法结合起来。

孩子兄弟表示法

  1. 链表中结点的两个链域分别指向该结点的第一孩子结点和下一个兄弟结点，分别命名为firstchild和nextsibling。
// 孩子兄弟表示法
typedef struct CSNode
{
    int data;
    struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;

若要访问结点x的第i个孩子，则只需要先从firstchild域找到第1个孩子结点，然后沿着孩子结点的nextsibling域连续走i-1步，便可找到x的第i个孩子。

树、森林、二叉树的转换

二叉树和树都支持二叉链表为存储结构，则以二叉链表为媒介可导出树与二叉树之间的对应关系。

给定一棵树，可以找到惟一的一颗二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同。

树与二叉树的转换关系示意图

由此可以看出，任何一颗与树对应的二叉树的右子树必为空。

若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则可以导出森林和二叉树的关系，如下图：

森林转换为二叉树

如果 $F=\lbrace T_1, T_2,…,T_m \rbrace$ 是森林，则可按如下规则将其转换为一颗二叉树 $B=(root, LB, RB)$。规则如下：

  1. 若 $F$ 为空，则 $m=0$，则 $B$ 为空树。
  2. 若 $F$ 非空，则 $m \ne 0$，则 $B$ 的根 $root$ 为森林中第一棵树的根 $ROOT(T_1)$；$B$ 的左子树 $LB$ 是从 $T_1$ 中根结点的子树森林 $F_1= \lbrace T_11,T_12,…,T_{1m1} \rbrace$ 转换而来的二叉树；右子树 $RB$ 是从森林 $F’= \lbrace T_2,…,T_m \rbrace$ 转换而成的二叉树。

二叉树转换为森林

如果 $B=(root,LB,RB)$ 是一颗二叉树，则可按如下规则转换成森林 $F=\lbrace T_1, T_2,…,T_m \rbrace$ 。转换规则如下：

  1. 若 $B$ 为空，则 $F$ 为空。
  2. 若 $B$ 为非空，则 $F$ 中第一棵树 $T_1$ 的根 $ROOT(T_1)$ 即为二叉树 $B$ 的根 $root$；$T_1$ 中根结点的子树森林 $F_1$ 是由 $B$ 的左子树 $LB$ 转换而来的森林；$F$ 中除 $T_1$ 之外的其余树组成的森林 $F’=\lbrace T_2, T_3,…,T_m \rbrace$ 是由 $B$ 的右子树 $RB$ 转换而成的森林。

树和森林的遍历

先序遍历森林

  1. 访问森林中第一棵树的根节点。
  2. 先序遍历第一棵树中根节点的子树森林。
  3. 先序遍历出去第一棵树之后剩余的树构成的森林。

中序遍历森林

  1. 中序遍历森林中第一棵树的根节点的子树森林。
  2. 访问第一棵树的根结点。
  3. 中序遍历除去第一棵树之后剩余的树构成的森林。

树的计数

回溯法与八皇后问题