数据结构笔记：树

• 树的抽象数据结构

  ADT 树（tree）
  Data
  Operation
      InitTree(*T): 构造空树T
      DestroyTree(*T): 销毁树T
      CreateTree(*T, definition): 按definition中给出树的定义来构造树
      ClearTree(*T): 若树T存在，则将树T清为空树
      TreeEmpty(T): 若T为空树，返回true，否则返回false
      TreeDepth(T): 返回T的深度
      Root(T): 返回T的根结点
      Value(T, cur_e): cur_e是树T中一个结点，返回此结点的值
      Assign(T, cur_e, value): 给树T的结点cur_e赋值为value
      Parent(T, cur_e): 若cur_e是树T的非根结点，则返回它的双亲，否则返回空
      LeftChild(T, cur_e): 若cur_e是树T的非叶结点，则返回它的最左孩子，否则返回空
      RightSibling(T, cur_e): 若cur_e有右兄弟，则返回它的右兄弟，否则返回空
      InsertChild(*T, *p, i, c): 其中p指向树T的某个结点，i为p所指结点的度加上1，
                                  非空树c与T不相交，操作结果为插入c为树T中p所指
                                  结点的第i棵子树
      DeleteChild(*T, *p, i): 其中p指向树T的某个结点，i为p所指结点的度，操作结果
                              结果为删除T中p所指结点的第i棵子树
  endADT

• 三种不同的表示法

  • 双亲表示法

     1 // 双亲表示法的结点结构
     2 #define MAX_TREE_SIZE 100
     3 typedef int TElemType; // 树结点的数据类型，目前暂定为整型
     4 typedef struct PTNode { // 结点结构
     5     TElemType data; // 结点数据
     6     int parent; // 双亲位置
     7 } PTNode;
     8 typedef struct { // 树结构
     9     PTNode nodes[MAX_TREE_SIZE]; // 结点数组
    10     int r, n; // 根的位置和结点数
    11 } PTree;

  • 孩子表示法（多重链表表示法）

     1 // 树的孩子表示法结构
     2 #define MAX_TREE_SIZE 100
     3 typedef struct CTNode { // 孩子结点
     4     int child;
     5     struct CTNode *next;
     6 } *ChildPtr;
     7 typedef struct { // 表头结构
     8     TElemType data;
     9     ChildPtr firstchild;
    10 } CTBox;
    11 typedef struct { // 树结构
    12     CTBox nodes[MAX_TREE_SIZE]; // 结点数组
    13     int r, n; // 根的位置和结点数
    14 } CTree;

  • 孩子兄弟表示法

    1 // 树的孩子兄弟表示法结构
    2 typedef struct CSNode {
    3     TElemType data;
    4     struct CSNode *firstchild, *rightsib;
    5 } CSNode, *CSTree;

• 二叉树

  • 二叉树顺序存储结构（适用性不强）
    一般只用于完全二叉树

  • 二叉链表

    1 // 二叉树的二叉链表结点结构定义
    2 typedef struct BiTNode { // 结点结构
    3     TElemType data; // 结点数据
    4     struct BiTNode *lchild, *rchild; // 左右孩子指针
    5 } BiTNode, *BiTree;

• 遍历二叉树

  • 前序遍历算法

    规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树

    1 // 二叉树的前序遍历递归算法
    2 void PreOrderTraverse(BiTree T) {
    3     if (T == NULL)
    4         return;
    5     printf("%c", T->data); // 显示结点数据，可以更改为其他对结点操作
    6     PreOrderTraverse(T->lchild); // 再先序遍历左子树
    7     PreOrderTraverse(T->rchild); // 最后先序遍历右子树
    8 }

  • 中序遍历算法

    规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后再访问根结点，最后中序遍历右子树

    1 // 二叉树的中序遍历递归算法
    2 void InOrderTraverse(BiTree T) {
    3     if (T == NULL)
    4         return;
    5     InOrderTraverse(T->lchild); // 中序遍历左子树
    6     printf("%c", T->data); // 显示结点数据，可以更改为对其他对结点操作
    7     InOrderTraverse(T->rchild); // 最后中序遍历右子树
    8 }

  • 后序遍历算法

    规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点

    1 // 二叉树的后序遍历递归算法
    2 void PostOrderTraverse(BiTree T) {
    3     if (T == NULL)
    4         return;
    5     PostOrderTraverse(T->lchild); // 先后序遍历左子树
    6     PostOrderTraverse(T->rchild); // 再后序遍历右子树
    7     printf("%c", T->data); // 显示结点数据，可以更改为其他对结点操作
    8 }

  • 层序遍历
    规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历
    

• 推导遍历结构
  已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
  已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
  已知前序和后序遍历，不能确定一棵二叉树。

• 二叉树的建立（以前序遍历为例）

  上图的前序遍历序列就为：AB#D##C##

  假设二叉树的结点均为一个字符，我们用键盘输入前序遍历数列。实现的算法如下：

   1 // 按前序输入二叉树中结点的值（一个字符）
   2 // #表示空树，构造二叉链表示二叉树T
   3 void CreateBiTree(BiTree *T) {
   4     TElemType ch;
   5     scanf("%c", &ch);
   6     if (ch == '#')
   7         *T = NULL;
   8     else {
   9         *T = (*BiTree)malloc(sizeof(BiTNode));
  10         if (!*T)
  11             exit(OVERFLOW);
  12         (*T)->data = ch; // 生成根结点
  13         CreateBiTree(&(*T)->lchild); // 构造左子树
  14         CreateBiTree(&(*T)->rchild); // 构造右子树
  15     }
  16 }

• 线索二叉树

  利用线索二叉树，我们能将空指针域充分地利用起来。

  指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。

  对二叉树以某种次序遍历使其变为线索二叉树的过程称作线索化。

  结点结构如下图：

  其中：ltag为0时lchild指向该结点的左孩子，为1时lchild指向该结点的前驱。

  　　 ltag为0时rchild指向该结点的右孩子，为1时rchild指向该结点的后继。

  这样一来，下图这样的二叉链表图↓↓

  就改成了下图的线索二叉树啦↓↓

  • 线索二叉树结构实现

    1 // 二叉树的二叉线索存储结构定义
    2 typedef enum {Link, Thread} PointerTag; // Link==0表示指向左右孩子指针
    3                                         Thread==1表示指向前驱或后继的线索
    4 typedef struct BiThrNode { // 二叉线索存储结点结构
    5     TElemType data; // 结点数据
    6     struct BiThrNode *lchild, *rchild; // 左右孩子指针
    7     PointerTag LTag;
    8     PointerTag RTag; // 左右标志
    9 } BiThrNode, *BiThrTree;

  • 线索化

    线索化的过程就是在遍历的过程中修改空指针的过程。

    中序遍历线索化的递归函数代码如下：

     1 BiThrTree pre; // 全局变量，始终指向刚刚访问过的结点
     2 // 中序遍历进行中序线索化
     3 void InThreading(BiThrTree p) {
     4     if (p) {
     5         InThreading(p->lchild); // 递归左子树线索化
     6         if (!p->lchild) { // 没有左孩子
     7             p->LTag = Thread; // 前缀线索
     8             p->lchild = pre; // 左孩子指针指向前驱
     9         }
    10         if (!pre->rchild) { // 前驱没有右孩子
    11             pre->RTag = Thread; // 后继线索
    12             pre->rchild = p; // 前驱右孩子指针指向后继（当前结点p）
    13         }
    14         pre = p; // 保持pre指向p的前驱
    15         InThreading(p->rchild); // 递归右子树线索化
    16     }
    17 }

    有了线索二叉树后，我们对它进行遍历时就等于是在操作一个双向链表结构。和双线链表结构一样，我们在二叉树线索链表上添加一个头结点，如下图所示：
    
    反之，令二叉树的中序序列中的第一个节点的lchild域指针和最后一个结点的rchild域指针均指向头结点（图中的③和④)。这样定义的好处时我们既可以从第一个结点起顺着后继进行遍历，也可以从最后一个结点起顺着前驱进行遍历。

  • 遍历

     1 // T指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向
     2    中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树T
     3 Status InOrderTraverse_Thr(BiThrTree T) {
     4     BiThrTree p;
     5     p = T->lchild; // p指向根结点
     6     while (p != T) { // 空树或遍历结束时，p==T
     7         while (p->LTag == Link) // 当LTag==0时循环到中序序列第一个结点
     8             p = p->lchild;
     9         printf("%c", p->data); // 显示结点数据，可以更改为其他对结点操作
    10         while (p->RTag == Thread && p->rchild != T) {
    11             p = p->rchild;
    12             printf("%c", p->data);
    13         }
    14         p = p->rchild; // p进至其右子树根
    15     }
    16     return OK;
    17 }