07、数据结构与算法 - 基础：二叉树和森林

线索二叉树

利用空指针域来真存放结点的前驱和后继信息

定义：

• 前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~
• 线索：指向前驱或后继结点的指针称为~
• 线索二叉树：加上线索的二叉链表表示的二叉树叫~
• 线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~

实现：

• 在有n个结点的二叉链表中必定有n+1个空链域
• 在线索二叉树的结点中增加两个标志域(0指结点，1左前右后)

1、 ltag:若ltag=0,lchild域指向左孩子；
2、 若ltar=1,lchild域指向其前驱；
3、 rtag:若rtag=0,rchild域指向右孩子；
4、 若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、 所有的树中，2度树的链域（存储空间）利用率最高；

树和森林的遍历

1．树的遍历

所谓树的遍历，就是按照某种顺序依次访问树中各个结点，并使得每个结点只被访问一次。也就是把非线性结构的树结点变成线性序列的一种方式。

树的遍历方法有：

按广度优先遍历（即按层次遍历）

按深度优先遍历，又可分为：前序遍历和后序遍历

2．森林的遍历

森林的遍历可分为前序遍历与中序遍历