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 }

   

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

 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 }

• 线索二叉树结构实现
  

  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 }