线索二叉树
利用空指针域来真存放结点的前驱和后继信息
定义：
- 前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~
- 线索：指向前驱或后继结点的指针称为~
- 线索二叉树：加上线索的二叉链表表示的二叉树叫~
- 线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~
实现：
- 在有n个结点的二叉链表中必定有n+1个空链域
- 在线索二叉树的结点中增加两个标志域(0指结点，1左前右后)
- ltag :若 ltag=0, lchild 域指向左孩子；
- 若 ltar=1, lchild域指向其前驱
- rtag :若 rtag =0, rchild 域指向右孩子；
- 若 rtag=1, rchild域指向其后继
例如：遍历中序线索二叉树
在中序线索二叉树中找结点后继的方法：
（1）若rtag=1, 则rchild域直接指向其后继
（2）若rtag=0, 则结点的后继应是其右子树的左链尾（ltag=1)的结点
在中序线索二叉树中找结点前驱的方法：
（1）若ltag=1, 则lchild域直接指向其前驱
（2）若ltag=0, 则结点的前驱应是其左子树的右链尾（rtag=1)的结点
树和森林
树的存储结构有：双亲表示法、孩子表示法、孩子兄弟表示法。
1．双亲存储表示法
用一组地址连续的存储单元来存放树的结点，每个结点有两个域：
data域-----存放结点的信息；
parent域-----存放该结点唯一的双亲结点的位置（数组下标）
双亲表示法的存储结构描述为：
#define MaxTreeSize 100
typedef char DataType；
typedef struct{
DataType data；
int parent；
} PTreeNode；
typedef struct {
PTreeNode nodes[MaxTreeSize];
int r,n；//根结点的位置和结点个数
}PTree；
PTree T；
2、孩子表示法
把每个结点的孩子结点排列起来，看作线性表，且以单链表做存储结构。
孩子表示法的存储结构描述为：
typedef struct Cnode {
int child;
struct CNode *next;
} Cnode; /*孩子结点类型说明*/
typedef struct {
DataType data;
Cnode *firstchild;
} PTNode; /*数组的每个元素的类型说明*/
typedef struct {
PTNode nodes[MaxTreeSize];
int n,root;
} Ctree;
3、孩子兄弟表示法
用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。由于结点中的两个指针指示的分别为“孩子”和“兄弟”，故称为“孩子-兄弟链表”。( 左孩右兄 )
树的孩子兄弟链表的存储结构描述为：
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
} CSNode, *CSTree;
孩子兄弟存储结构的 优点 是可以方便地实现树和二叉树的相互转换和树的各种操作；
缺点 是查找当前结点的双亲结点比较麻烦。 解决方法：增设parent域。
森林转换成二叉树
转换原则：
(1)将森林中的每棵树转换成等价的二叉树；
(2)保留第一棵二叉树，从第二棵二叉树开始，依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，所有二叉树依此相连。
树转化为二叉树的意义 ：
1、因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。
2、所有的树中，2度树的链域（存储空间）利用率最高。
树和森林的遍历
1．树的遍历
所谓树的遍历，就是按照某种顺序依次访问树中各个结点，并使得每个结点只被访问一次。也就是把非线性结构的树结点变成线性序列的一种方式。
树的遍历方法有：
按广度优先遍历（即按层次遍历）
按深度优先遍历，又可分为：前序遍历和后序遍历
2．森林的遍历
森林的遍历可分为 前序遍历 与 中序遍历
