1. /*
    2.     该文件用于创建三类线索二叉树，即中序线索二叉树、先序线索二叉树、后序线索二叉树
    3. */
    4. struct biTree {
    5.     char data;
    6.     struct biTree *lchild;
    7.     struct biTree *rchild;
    8.     int ltag, rtag;//用于进行标记
    9. };
    10. #include <stdio.h>
    12. void inThread(biTree *p, biTree *pre ) {//中序线索二叉树
    13.     if (p!=NULL) {
    14.         inThread(p->lchild,pre);
    15.         if (p->lchild==NULL) {//如果左子树为空，建立前驱线索
    16.             p->lchild = pre;
    17.             p->ltag = 1;
    18.         }
    19.         if (pre!=NULL && pre->rchild==NULL) {//建立前驱结点的后继线索
    20.             pre->rchild = p;
    21.             pre->rtag = 1;
    22.         }
    23.         pre = p;
    24.         inThread(p->rchild,pre);
    25.     }
    26. }
    27. void preThread(biTree *p, biTree *pre) {//先序线索二叉树
    28.     if (p != NULL) {
    30.         if (p->lchild == NULL) {//如果左子树为空，建立前驱线索
    31.             p->lchild = pre;
    32.             p->ltag = 1;
    33.         }
    34.         if (pre != NULL && pre->rchild == NULL) {//建立前驱结点的后继线索
    35.             pre->rchild = p;
    36.             pre->rtag = 1;
    37.         }
    38.         pre = p;
    39.         inThread(p->lchild, pre);
    40.         inThread(p->rchild, pre);
    41.     }
    42. }
    43. void postThread(biTree *p, biTree *pre) {//后序线索二叉树
    44.     if (p != NULL) {
    45.         inThread(p->lchild, pre);
    46.         inThread(p->rchild, pre);
    47.         if (p->lchild == NULL) {//如果左子树为空，建立前驱线索
    48.             p->lchild = pre;
    49.             p->ltag = 1;
    50.         }
    51.         if (pre != NULL && pre->rchild == NULL) {//建立前驱结点的后继线索
    52.             pre->rchild = p;
    53.             pre->rtag = 1;
    54.         }
    55.         pre = p;
    57.     }
    58. }