数据结构C语言实现12.线索二叉树

引言

　　我们知道，二叉树遍历的实质是对非线性结构的树进行线性化的过程，它使得每个节点(除了第一个和最后一个节点外)在这种线性序列中有且仅有一个直接前驱和一个直接后继．但是在二叉链表的存储方式中，我们只能找到每个节点的左右孩子信息，而不能直接得到一个节点在先序，中序和后序遍历这一序列中的前驱和后继信息，这些信息只有在遍历二叉树的动态过程中才能获得．为了保留节点在某种遍历序列中其直接前驱和直接后继的位置信息，可以在每个节点中增加两个指针域来存放在遍历时所得到的有关前驱和后继的信息，但这种方法却降低了存储空间的利用率．
　　对于采用二叉链表存储结构的二叉树来说，如果该二叉树有n个节点，则存放这n个节点的二叉链表中就有2n个指针域，且只有n-1个指针域用来存储孩子节点地址的，而另外n+1个指针域为空．因此，可以利用节点空的左指针域(lchild)来指向该节点在某种遍历序列中的直接前驱节点；利用节点空的右指针域(rchild)来指向该节点在某种遍历序列中的直接后继节点．对于那些非空的指针域，则仍然存放指向该节点左右孩子的指针．这些指向直接前驱节点或直接后继节点的指针被称为线索(Thread)，加了线索的二叉树被称为　线索二叉树．
　　为二叉树中所有节点排列成一个线性序列可采用不同的遍历方法(即先序，中序，后序)得到．因此,线索二叉树将先序线索二叉树,中序线索二叉树和后序线索二叉树三种.并且,我们把二叉树改造成线索二叉树的过程成为线索化.
　　　　
　　　　对下图中(a)所示二叉树进行线索化,得到的先序线索二叉树,中序线索二叉树,后序线索二叉树分别如图(b)(c)(d)所示,图中的实线表示指针,虚线表示线索.
　　　　
　　　　接下来的问题是:在二叉链表存储中如何区分一个节点的指针域存放的是指针还是线索?这种区分可以用下面两种方法实现.
　　　　(1).为每个节点增加两个标志位,left_flag和right_flag,并另:
　　　　
　　　　left_flag = { $^{0\ \ \ left_child 指向节点的左孩子}
_{1\ \ \ left_child 指向节点的右孩子}$

　　　　right_flag = { $^{0\ \ \ right_child 指向节点的左孩子}
_{1\ \ \ right_child 指向节点的右孩子}$
　　　　
　　　　每个标志位只占一个bit,这样就只需增加很少的存储空间,这种情况下的节点结构为:

| left_flag | left_child | data | right_child | right_flag |
|: —– :|: —– :|: —– :|: —– :|: —– :|: – :|

　　　　(2). 不改变节点的结构,仅在作为线索的地址前加一个负号.也即,负地址表示线索而正地址表示指针.

在此,我们按照第一种方法来介绍线索二叉树的存储.为了将二叉树中所有的空指针都利用起来以及操作方便的需要,在存储线索二叉树时通常增加一个头节点,其结构与其他线索二叉树的节点结构完全一样,只是其存储域不存储数据而已.这个头节点的左指针指向二叉树的根节点,而右指针则指向某种遍历序列的最后一个节点.并且,二叉树在某种遍历下的第一个节点的前驱节点和最后一个节点的后继节点都指向这个头节点.

---

一． 线索化二叉树

为了实现线索化二叉树,我们将二叉树节点的类型定义修改为:

typedef struct Tree_node
{
    char data;                     //节点数据
    int left_flag;                 //线索标记
    int right_flag;
    struct *Tree_node *left_child; //左孩子或直接前驱线索指针
    struct *Tree_node *right_child;//右孩子或直接后继线索指针
}

将二叉树线索化的过程,实际上是在二叉树遍历过程中用线索取代空指针的过程.对同一颗二叉树遍历的方式不同,所得到的线索树也不同.但无论哪种遍历,实现线索的方法是一样的,即都是设置一个指针pre始终指向刚被访问过的节点,而指针p则用来指向正在访问的节点,由此记录下遍历过程中访问节点的先后顺序,并对当前访问的节点*p做如下处理:

1. 若p所指节点有空指针域,则置相应标记位为1.
2. 若pre != NULL,则看pre所指节点的右标志是否为1,若为1则pre->right_child指向p所指向的当前节点(即节点*pre的直接后继).
3. 若p所指当前节点的左标志为1,则p->left_child指向pre所指向的节点(即节点*pre是节点*p的直接前驱).
4. 将指针pre指向刚访问过的当前节点*p(即pre = p;),而p则下移指向新的当前节点.
   需要注意的是,在给一棵二叉树添加线索时先要创建一个头节点,并建立头节点与二叉树根节点的线索.当二叉树线索化之后,还需建立最后一个节点与头节点之间的线索.

下面,我们将建立中序线索二叉树的算法为例予以说明,该算法分为Thread(p)算法和Creat_Thread(p)算法两部分.

Thread(p)算法用于对*p为根节点的二叉树进行中序线索化.在该算法中,p总指向当前被线索化的节点,而pre作为全局变量则指向刚访问过的节点.也即,*pre是*p的前驱节点,而*p是*pre的后继节点.Thread(p)算法类似中序遍历的递归算法,在p指针不线索化为指向其前驱节点*pre并将其标志位left_flag置为1;否则left_child指向左孩子节点.若*pre节点的right_child指针为NULL,则将right_child指针线索化为指向其后继节点*p并将其标志位right_child置为1;否则right_child指向其右孩子节点.然后将pre指向*p节点,再对*p节点的右子树进行线索化.

Create_Thread(b)算法是对以二叉树存储的二叉树b进行中序线索化,并返回线索化后的头节点指针root.实现方法是:先创建头节点*root,其right_child域为线索,left_child域为链指针并指向二叉树根节点*b.如果二叉树b为空,则将left_child指向头节点自身;否则将*root的left_child指向*b节点,并将pre也指向*root节点.然后调用Thread(b)对整个二叉树线索化,即将指针b传给形参p,从而使得*pre是*p的前驱节点.最后,加入指向头节点的线索,并将头节点的right_child指针域线索化为指向最后一个节点(由于线索化过程是进行到p等于NULL为止,所以最后一个节点就是*pre).

中序线索二叉树算法如下:

TBTree *pre;                          //全局变量
void Thread(TBTree *p)                //对二叉树进行中序线索化
{
    if(p != NULL)
    {
        Thread(p->left_child);        //先对*p的左子树线索化
        //到此,*p节点的左子树不存在或已线索化,接下来对*p线索化
        if(p->left_child == NULL)     //*p的左孩子不存在则进行前驱线索
        {
            p->left_child = pre;      //建立当前节点*p的前驱线索
            p->left_flag = 1;
        }
        else
        {
            p->left_flag = 0;          //置*p的left_child指针为指向左孩子标志
        }
        if(pre->right_child == NULL)   //*pre的右孩子不存在则进行后继线索
        {
            pre->right_child = p;      //建立节点*pre的后继线索
            pre->right_flag = 1;
        }
        else
        {
            pre->right_flag = 0;        //置*p的right_child指针为指向右孩子标志
        }
        pre = p;                       //pre移至*p节点
        Thread(p->right_child);        //对*p的右子树线索化
    }
}

TBTree *Create_Thread(TBTree *b)            //建立中序线索二叉树
{
    TBTree *root;
    root = (TBTree *)malloc(sizeof(TBTree));//创建头节点
    root->left_flag = 0;
    root->right->flag = 1;
    if(b == NULL)                           //二叉树为空
    {
        root->left_child = root;
    }
    else
    {
        root->left_child = b;               //root是left_child指针指向二叉树根节点*b
        pre = root;                         //*pre是*p的前驱节点,pre指针用于线索
        Thread(b);                          //对二叉树b进行中序线索化
        pre->right_child = root;            //最后处理,加入指向头节点的线索
        pre->right_flag = 1;
        root->right_child = pre;            //头节点的right_child指针线索化为指向最后一个节点
    }
    return root;                             //返回线索化后指向二叉树的头节点的指针
}

二．访问线索二叉树

线索二叉树建立之后,就可以通过线索访问某个节点的前驱节点或后继节点了.但是,由于这种线索是通过二叉树存储结构中的空指针实现的.因此这种线索只是不完整的部分线索,即并不是每个节点的前驱和后继都有指针指向.所以,在访问某个节点的前驱或后继节点时也要分有线索和无线索两种情况来考虑.

1. 在中序线索二叉树上查找任意节点的中序前驱节点
   对中序线索二叉树上的任一节点*p,寻找其中序前驱节点可分为下面两种情况:
   (1). 若p->left_flag等于1,则p->left_child即指向前驱节点(p->left_child为线索指针).
   (2). 若p->left_flag等于0,则表明*p有左孩子.根据中序遍历的定义,*p的前驱节点是以*p的左孩子为根节点的子树的最右节点.也即,沿*p左子树的右指针链向下查找,直到某个节点的右标志right_flag为1时,则该节点就是所找的前驱节点.
   在中序线索树上查找*p的中序前驱节点算法如下:

   TBTree *Inpre(TBTree *p)
   {
       TBTree *pre;
       pre = p ->left_child;
       if(p->left_flag == 0)            //*p有左孩子时
       {
           while(pre->right_flag == 0)  //沿*p左子树的右指针链向下查找直到某节点的right_flag为1
           {
               pre = pre->right_child;  //返回指向*p的中序前驱节点的指针值
           }
       }
       return pre;
   }

2.在中序线索二叉树上查找任意节点的中需后续节点
对于中序线索二叉树上的任一节点*p,寻找其中序后继节点可分为下面两种情况:
(1). 若p->right_flag等于1,则p->right_child即指向后继节点.
(2). 若p->left_flag等于0,则表明*p有右孩子.根据中序遍历的定义,*p的后继节点是以*p的右孩子为根节点的子树的最左节点.也即,沿*p右子树的左指针链向下查找,直到某个节点的左标志left_flag为1时,则该节点就是所找的后继节点.
在中序线索树上查找*p的中序后继节点算法如下:

TBTree *InPost(TBTree *p)
{
    TBTree *post;
    post = p ->right_child;
    if(p->right_flag == 0)           //*p有右孩子时
    {
        while(post->left_flag == 0)  //沿*p右子树的左指针链向下查找直到某节点的left_flag为1
        {
            pre = pre->left_child;   //返回指向*p的中序后继节点的指针值
        }
    }
    return post;
}	
```	
3.中序遍历中序线索二叉树
   在中序线索二叉树中,开始节点就是根节点的最左下节点,而求当前节点在中序序列中的后继和前驱节点方法如前所述,并且最后一个节点的`right_child`指针被线索化为指向头节点.利用这些条件,在中序线索二叉树中实现中序遍历的算法如下:
```c
void Inorder(TBTree *b)             //中序遍历中序线索二叉树
{                                   //*b为中序线索二叉树的头节点
    TBTree *p;
    p = b->left_child;              //p指向根节点
    while(p != b)                   //当p不等于指向头节点的指针b时
    {
        while(p->left_flag == 0)   //寻找中序序列中的第一个节点
        {
            p = p ->left_child;
        }
        printf("%3c", p->data);    //输出中序序列的第一个节点数据
        while(p->right_flag == 1 && p->right_child != b)
        {                          //后续线索存在且后续线索不为头节点时
            p = p->right_child;    //根据后继线索找到后继节点
            printf("%3c", p->data);//输出后继节点信息
        }
        p = p->right_child;        //无后继线索则p指向右孩子节点
    }
}

三．线索二叉树的接口

• thread_tree.h

  #ifndef _THREAD_TREE_H_
  #define _THREAD_TREE_H_
  
  #include "tools.h"
  
  #define ONE    ( 1 )
  #define THREAD ( 1 )
  #define LINK   ( 0 )
  #define END    ('#')
  
  typedef struct Tree_node Tree_node;
  
  struct Tree_node{
      char              data;                                                 //数据区域
      int          left_flag;
      int         right_flag;
      Tree_node * left_child;    
      Tree_node *right_child;
  };                 
  
  typedef Tree_node *Bin_tree;                                                //二叉树的根节点
  
  
  Tree_node *find_parent(Bin_tree root, Tree_node *node);
  Tree_node *get_parent(Bin_tree root, Tree_node *kid);
  //二叉树的接口
  Bin_tree create_tree(char **str);                                           //一.1.创建二叉树
  void pre_order_print(Bin_tree root);                                        //三.1.前序递归遍历
  void mid_order_print(Bin_tree root);                                        //三.2.中序递归遍历
  void last_order_print(Bin_tree root);                                       //三.3.后序递归遍历
  
  //线索二叉树的接口
  
  //一.先序线索二叉树
  
  //一.1 先序线索化
  void pre_thread(Bin_tree tree);
  //一.2 创建先序线索二叉树
  Bin_tree create_pre_thread(Bin_tree tree);
  //一.3 先序线索二叉树中节点的前驱
  Bin_tree front_in_pre(Bin_tree root, Tree_node *p_node);
  //一.4 先序线索二叉树中节点的后继
  Bin_tree behind_in_pre(Bin_tree root, Tree_node *p_node);
  //一.5 遍历输出先序线索二叉树
  void pre_order_print_thread(Bin_tree root);
  //一.6 销毁先序线索二叉树
  void destroy_pre(Bin_tree root);
  
  //二.中序线索二叉树
  //二.1 中序线索化
  void mid_thread(Bin_tree tree);
  //二.2 创建中序线索二叉树
  Bin_tree create_mid_thread(Bin_tree tree);
  //二.3 中序线索二叉树中节点的前驱
  Bin_tree front_in_mid(Bin_tree root, Tree_node *p_node);
  //二.4 中序线索二叉树中节点的后继
  Bin_tree behind_in_mid(Bin_tree root, Tree_node *p_node);
  //二.5 遍历输出中序线索二叉树
  void mid_order_print_thread(Bin_tree root);         
  //二.6 销毁中序线索二叉树
  void destroy_mid(Bin_tree root);
  
  //三.后序线索二叉树
  //三.1 后序线索化
  void last_thread(Bin_tree tree);
  //三.2 创建后序线索二叉树
  Bin_tree create_last_thread(Bin_tree tree);
  //三.3 后序线索二叉树中节点的前驱
  Bin_tree front_in_last(Bin_tree root, Tree_node *p_node);
  //三.4 后序线索二叉树中节点的后继
  Bin_tree behind_in_last(Bin_tree root, Tree_node *p_node);
  //三.5 遍历输出后序线索二叉树
  void last_order_print_thread(Bin_tree root);
  //三.6 销毁后序线索二叉树
  void destroy_last(Bin_tree root);
                        
  #endif //_THREAD_TREE_H_

  四. 线索二叉树的接口实现

• -

• thread_tree.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <unistd.h>
#include <math.h>
#include "thread_tree.h"
#include "tools.h"
#include "queue.h"
#include "stack.h"

//二叉树的接口
static int max(int a, int b);
static Tree_node *create_node(void);
static int get_index(char *string, char value);
static void destroy(Bin_tree root);
static Tree_node *find_common(Bin_tree root,
                              Tree_node *node1, Tree_node *node2);

static int max(int a, int b)
{ 
    return b > a ? b : a;
}
static Tree_node *create_node(void)
{
    Tree_node *node = (Tree_node *)Malloc(sizeof(Tree_node));
    bzero(node, sizeof(Tree_node));
 
    return node;
}
static int get_index(char *string, char value)
{
    // abcdefg
    //
    //     e
    char *local = strchr(string, value);
    return local == NULL ? -1 : (local - string) / sizeof(char);
}

Tree_node *find_parent(Bin_tree root,
                       Tree_node *kid)    //找到指定节点的双亲节点
{
    Tree_node *temp = root;
    if(temp->left_child == kid)
    {
        return temp;
    }
    else
    {
        temp = temp->left_child;
        while(temp->left_child != kid && temp->right_child != kid)
        {
            if(temp->left_flag == LINK)
            {
                temp = temp->left_child;
            }
            else
            {
                temp = temp->right_child;
            }
        }
    }
    return temp;
}

Tree_node *get_parent(Bin_tree root, Tree_node *kid)
{
    if(root == NULL || kid == NULL)
    {
        printf("can't find.\n");
        return NULL;
    }
    Tree_node *temp = root;
    if(temp->left_child == kid)
    {
        return temp;
    }
    else
    {
        temp = temp->left_child;
        while(temp->left_child != kid && temp->right_child != kid)
        {
            if(temp->right_flag == LINK)
            {
                temp = temp->right_child;
            }
            else
            {
                temp = temp->left_child;
            }
        }
    }
    return temp;
}
//创建二叉树

//二叉树的接口

//一.创建二叉树
Bin_tree create_tree(char **str)
{
    Bin_tree root = NULL;

    if(str != NULL && *str != NULL && **str != END){
        root = create_node();  
        root->data = **str;
        root->left_flag = LINK;
        root->right_flag = LINK;
   
        //处理完当前节点，然后递归地创建其左右孩子
        //++*str;
        (*str)++;
        root->left_child = create_tree(str);
        //++*str;
        (*str)++;
        root->right_child = create_tree(str);
    }

    return root;
}


//三.1.前序递归遍历
//void pre_order_print(Bin_tree root);                                  
void pre_order_print(Bin_tree root)    //前序递归遍历
{
    if(root != NULL){
         printf("%c ", root->data);
         pre_order_print(root->left_child);
         pre_order_print(root->right_child);
    }
}

//三.2.中序递归遍历
//void mid_order_print(Bin_tree root);                                       
void mid_order_print(Bin_tree root)    //中序递归遍历
{
    if(root != NULL){
         mid_order_print(root->left_child);
         printf("%c ", root->data);
         mid_order_print(root->right_child);
    }

}
//三.3.后序递归遍历
//void last_order_print(Bin_tree root);                                       
void last_order_print(Bin_tree root)    //后序递归遍历
{
    if(root != NULL){
         last_order_print(root->left_child);
         last_order_print(root->right_child);
         printf("%c ", root->data);
    }

}

Tree_node *pre = NULL;      //全局变量

//一.1 先序线索化
//先对根节点进行线索化,再对左右孩子进行线索化.
void pre_thread(Bin_tree tree)
{
    if(tree != NULL)
    {
        if(!tree->left_child)
        {
            tree->left_child = pre;
            tree->left_flag = THREAD;
        }
        else
        {
            tree->left_flag = LINK;
        }
        if(pre->right_child == NULL)
        {
            pre->right_child = tree;
            pre->right_flag = THREAD;
        }
        else
        {
            pre->right_flag = LINK;
        }
        pre = tree;
        if(tree->left_flag == LINK)
            pre_thread(tree->left_child);
        if(tree->right_flag == LINK)
            pre_thread(tree->right_child);
    }
}
//一.2 创建先序线索二叉树
Bin_tree create_pre_thread(Bin_tree tree)
{
    Bin_tree root = NULL;
    root = create_node();                      //创建头节点root
    root->left_flag = LINK;
    root->right_flag = THREAD;
    if(tree == NULL)                           //二叉树为空
    {
        root->left_child = root;
    }
    else
    {
        pre = root;
        root->left_child = tree;               //root的左孩子指向tree
        pre_thread(tree);                      //线索化二叉树tree
        pre->right_child = root;               //遍历完后最后一个pre指向root
        pre->right_flag = THREAD;
        root->right_child = pre;
    }
    return root;
}
//在前序线索二叉树中找到节点p_node的前一个节点
//
//            A
//          /   \
//         B     G
//        / \   /  \
//       C   D H   J 
//          / \ \
//         E   F I 
//    在前序线索二叉树中,遍历顺序为"根左右",
//    对上面这个二叉树转化为前序线索二叉树之后,前序遍历为 A B C D E F G H I J 
//    对节点而言,先根A然后左子树B,B作为根,左子树C,右子树D,D作为根节点,左子树E,右子树F...
//    某一节点的前一个节点,
//    1.作为左子树,前一个节点即是其父节点.
//    2.作为右子树,因为是"根左右"的顺序,于是,其前一个节点为兄弟的最右节点.
//
//一.3 先序线索二叉树中节点的前驱
Bin_tree front_in_pre(Bin_tree root, Tree_node *p_node)
{
    Tree_node *front = NULL;
    Tree_node *parent = NULL;
    front = p_node->left_child;              //先指向p_node左孩子
    if(p_node->left_flag == LINK)
    {
        parent = find_parent(root, p_node);  //查找p_node的父节点
        if(parent->left_child == p_node)     //情况1. 作为左节点
        {
            front = parent;
        }
        else                                 //情况2.
        {
            front = parent->left_child;      //查找左子树的最右节点
            while(front->right_flag == LINK)
            {
                front = front->right_child;
            }
        }
    }
    return front;
}
//在前序线索二叉树中找到节点p_node的后一个节点
//
//            A
//          /   \
//         B     G
//        / \   /  \
//       C   D H   J 
//          / \ \
//         E   F I 
//    在前序线索二叉树中,遍历顺序为"根左右",
//    对上面这个二叉树转化为前序线索二叉树之后,前序遍历为 A B C D E F G H I J 
//    对节点而言,先根A然后左子树B,B作为根,左子树C,右子树D,D作为根节点,左子树E,右子树F...
//    某一节点的后一个节点,
//    1.如果有左孩子,按照根左右的顺序,找当前节点的左节点.
//    2.如果有后继(left_flag == 1),则其right_child其后继.
//    
//
//一.4 先序线索二叉树中节点的后继
Bin_tree behind_in_pre(Bin_tree root, Tree_node *p_node)
{
    Tree_node *behind = NULL;
    behind = p_node->left_child;

    if(p_node->left_flag == LINK)          //p_node有左孩子
    {
        behind = p_node->left_child;
    }
    else                                   //有线索后继
    {
        behind = p_node->right_child;
    }
    return behind;
}
//一.5 遍历输出先序线索二叉树
//根左右的顺序
//先输出根节点,然后找其左孩子,若没有左孩子,根据后继寻找下一个节点
void pre_order_print_thread(Bin_tree root)
{                                           //root为前序线索二叉树的头节点
    Tree_node *p_node = NULL;
    p_node = root->left_child;              //p_node指向根节点tree
    while(p_node != root)                   //当p_node不等于指向头节点的指针root时
    {
        printf("%3c", p_node->data);        //输出前序序列的一个根节点数据
        if(p_node->left_flag == LINK)       //前序序列中根节点的左孩子
        {
            p_node = p_node ->left_child;
        }
        else
        {                                   
            p_node = p_node->right_child;   //根据后继线索找到后继节点
        }
    }
}   
//一.6 销毁先序线索二叉树
//与遍历顺序相同,保存当前节点,得到下一个时释放当前资源
void destroy_pre(Bin_tree root)    
{
    if(NULL == root)
    {
        return;
    }
    Tree_node *p_node = root->left_child;
    Tree_node *pre = p_node;

    while(p_node != root)
    {
        pre = p_node;                          //保存当前根节点
        if(p_node->left_flag == LINK)          //找其左子树
        {
            p_node = p_node->left_child;
        }
        else                                   //寻找其后继
        {
            p_node = p_node->right_child;
        }
        free(pre);
    }
}
////////////////////////////////////////////////////////////////////////////////////////////////////
//二.中序线索二叉树
//二.1 中序线索化
//按"左根右"的顺寻进行
void mid_thread(Bin_tree tree)                //对二叉树进行中序线索化
{
    if(tree != NULL)
    {
        mid_thread(tree->left_child);        //先对tree的左子树线索化
        //到此,tree节点的左子树不存在或已线索化,接下来对tree线索化
        if(tree->left_child == NULL)         //tree的左孩子不存在则进行前驱线索
        {
            tree->left_child = pre;          //建立当前节点tree的前驱线索
            tree->left_flag = THREAD;
        }
        else
        {
            tree->left_flag = LINK;          //置tree的left_child指针为指向左孩子标志
        }
        if(pre->right_child == NULL)         //pre的右孩子不存在则进行后继线索
        {
            pre->right_child = tree;         //建立节点pre的后继线索
            pre->right_flag = THREAD;
        }
        else
        {
            pre->right_flag = LINK;          //置p的right_child指针为指向右孩子标志
        }
        pre = tree;                          //pre移至tree节点
        mid_thread(tree->right_child);       //对tree的右子树线索化
    }
}

//二.2 创建中序线索二叉树
//创建一个root根节点,对tree进行中序线索化
Bin_tree create_mid_thread(Bin_tree tree)  
{
    Bin_tree root = NULL;
    root = create_node();                   //创建头节点
    root->left_flag = LINK;
    root->right_flag = THREAD;
    if(tree == NULL)                        //二叉树为空
    {
        root->left_child = root;
    }
    else
    {
        root->left_child = tree;            //root的left_child指针指向二叉树根节点tree
        pre = root;
        mid_thread(tree);                   //对二叉树tree进行中序线索化
        pre->right_child = root;            //最后处理,加入指向头节点的线索
        pre->right_flag = THREAD;
        root->right_child = pre;            //头节点的right_child指针线索化为指向最后一个节点
    }
    return root;                            //返回线索化后指向二叉树的头节点的指针root
}
//在中序线索二叉树中查找某节点的前一个节点
//按"左根右"的顺序而言,
//若p_node的left_flag为1,则p_node的left_child即为其前驱节点
//若p_node的left_flag为0,则p_node有左子树,前驱则在其左子树的最右孩子节点
//                   
//          A        
//        /   \
//       B     G     
//      / \    / \
//     C   D  H   J  
//        / \  \
//       E   F  I        
//
// 中序: C B E D F A H I G J 
//二.3 中序线索二叉树中节点的前驱
Bin_tree front_in_mid(Bin_tree root, Tree_node *p_node)
{
    Tree_node *front = NULL;
    front = p_node->left_child;
    if(p_node->left_flag == LINK)
    {
        while(front->right_flag == LINK)      //查找最右孩子
        {
            front = front->right_child;
        }
    }
    return front;
}
//中序线索二叉树中查找某节点后继节点
//按"左根右"的顺序而言,
//若p_node的right_flag为1,则p_node的right_child即为其后继节点
//若p_node的right_flag为0,则p_node有右子树,前驱则在其右子树的最左孩子节点
//二.4 中序线索二叉树中节点的后继
Bin_tree behind_in_mid(Bin_tree root, Tree_node *p_node)
{
    Tree_node *behind = NULL;
    behind = p_node->right_child;
    if(p_node->right_flag == LINK)
    {
        while(behind->left_flag == LINK)
        {
            behind = behind->left_child;
        }
    }
    return behind;
}
//中序遍历中序线索二叉树
//          A        
//        /   \
//       B     G     
//      / \    / \
//     C   D  H   J  
//        / \  \
//       E   F  I        
//
// 中序: C B E D F A H I G J 
//二.5 遍历输出中序线索二叉树
void mid_order_print_thread(Bin_tree root)             
{                                      //root为中序线索二叉树的头节点
    Tree_node *p = NULL;
    p = root->left_child;              //p指向根节点
    while(p != root)                   //当p不等于指向头节点的指针root时
    {
        while(p->left_flag == LINK)    //寻找中序序列中的第一个节点
        {
            p = p ->left_child;        //最左孩子
        }
        printf("%3c", p->data);        //输出中序序列的第一个节点数据
        while(p->right_flag == THREAD && p->right_child != root)
        {                              //后续线索存在且后续线索不为头节点时
            p = p->right_child;        //根据后继线索找到后继节点
            printf("%3c", p->data);    //输出后继节点信息
        }
        p = p->right_child;            //无后继线索则p指向右孩子节点
    }
}   
//二.6 销毁中序线索二叉树
//以遍历的顺序依次销毁释放资源
void destroy_mid(Bin_tree root)
{
    Tree_node *p_node = NULL;
    Tree_node *pre_node = NULL;                  //用pre_node保存上一个节点
    p_node = root->left_child;
    while(p_node != root)
    {
        while(p_node->left_flag == LINK)
        {
            p_node = p_node->left_child;         //最左孩子
        }
        pre_node = p_node;                       //保存当前节点
        while(p_node->right_flag == THREAD && p_node->right_child != root)
        {
            p_node = p_node->right_child;        //p_node指向新的后继节点后,释放上一个节点
            free(pre_node);
            pre_node = p_node;
        }
        p_node = p_node->right_child;
        free(pre_node);
    }
}
//三.后序线索二叉树
//三.1 后序线索化
//按照"左右根"的顺序进行
void last_thread(Bin_tree tree)
{
    if(tree != NULL)
    {
        last_thread(tree->left_child);
        last_thread(tree->right_child);
        if(tree->left_child == NULL)
        {
            tree->left_child = pre;
            tree->left_flag = THREAD;
        }
        if(pre->right_child == NULL)
        {
            pre->right_child = tree;
            pre->right_flag = THREAD;
        }
        pre = tree;
    }
}
//三.2 创建后序线索二叉树
//创建新节点root指向原来的tree
Bin_tree create_last_thread(Bin_tree tree)
{
    Bin_tree root = NULL;
    root = create_node();                     //新节点root
    root->right_flag = LINK;
    root->right_child = root;
    if(tree == NULL)                          //无二叉树时
    {
        root->left_child = root;
    }
    else
    {
        pre = root;
        root->left_child = tree;              //root指向tree
        root->left_flag = LINK;
        last_thread(tree);                    //后序线索化tree
        root->right_child = pre;
    }
    return root;
}
//在后序线索二叉树中寻找某节点的前驱节点
//由于是后序遍历,以"左右根"的顺序遍历,所以,
//某节点若为根,其right_flag为0,即有右孩子则其right_child即为其前驱.
//否则,找其左孩子.
//三.3 后序线索二叉树中节点的前驱
Bin_tree front_in_last(Bin_tree root, Tree_node *p_node)
{
    Tree_node *front = NULL;
    if(p_node->right_flag == LINK)
    {
        front = p_node->right_child;
    }
    else
    {
        front = p_node->left_child;
    }
    return front;
}
//在后序线索二叉树中寻找某节点的后继节点
//
//          A        
//        /   \
//       B     G     
//      / \    / \
//     C   D  H   J  
//        / \  \
//       E   F  I     
//
// C E F D B I H J G A 
// (左右根)
// 1. 若right_flag == 1, 即为线索,则其right_child即为后继;
// 2. 找到当前节点的父节点,若当前节点为其父节点的右孩子,即此父节点为其后继
// 3. 上图中的B,其后继节点为I,即其兄弟节点左子树里的最深节点
//三.4 后序线索二叉树中节点的后继
Bin_tree behind_in_last(Bin_tree root, Tree_node *p_node)
{
    Tree_node *behind = NULL;
    Tree_node *parent = NULL;
    if(p_node->right_flag == THREAD)      //1. 后继
    {
        behind = p_node->right_child;
    }
    else
    {
        parent = find_parent(root, p_node);
        if(parent->right_child == p_node)
        {
            behind = parent;              //2. 父节点为其后继
        }
        else                              //3. 跨越子树的后继节点
        {
            behind = parent->right_child;
            while(behind->left_flag == LINK || behind->right_flag == LINK)
            {
                if(behind->left_flag == LINK)
                {
                    behind = behind->left_child;
                }
                else
                {
                    behind = behind->right_child;
                }
            }
        }
    }
    return behind;
}
//输出后序线索二叉树
//按"左右根"的顺序,自底向上输出
//          A        
//        /   \
//       B     G     
//      / \    / \
//     C   D  H   J  
//        / \  \
//       E   F  I     
//
// C E F D B I H J G A 
// (左右根)
//                                  取得C,输出C,找到C的父节点B,
// C不是B的右孩子,向下查找,到D,     再到E,输出E,找到E的父节点D,
// E不是D的右孩子,向下查找,         取得F,输出F,找到F的父节点D,
// F为D的右孩子,                    取得D,输出D,找到D的父节点B,
// D为B的右孩子,                    取得B,输出B,找到B的父节点A,
// B不是A的右孩子,向下查找,到G,到H, 取得I,输出I,找到I的父节点H,
// I为H的右孩子,                    取得H,输出H,找到H的父节点G,
// H不是G的右孩子,                  取得J,输出J,找到J的父节点G,
// J为G的右孩子,                    取得G,输出G,找到G的父节点A,
// G为A的右孩子,                    取得A,输出A;  
//三.5 遍历输出后序线索二叉树
void last_order_print_thread(Bin_tree root)
{
    Tree_node *temp = root->left_child;
    Tree_node *parent = NULL;
    while(TRUE)
    {
        while(temp->left_flag == LINK)
        {
            temp = temp->left_child;
        }
        if(temp->right_flag == LINK)
        {
            temp = temp->right_child;
        }
        else
        {
            break;                        //1.找到左子树中最深的节点
        }
    }
    while(temp != root)
    {
        printf("%3c", temp->data);        //2. 输出节点信息 
        parent = get_parent(root, temp);  //3. 获取父节点
        if(parent == root)
        {
            temp = root;                  //完毕
        }
        else if(parent->right_flag == THREAD || temp == parent->right_child)
        {
            temp = parent;                //当前节点为父节点的右孩子
        }
        else
        {
            while(parent->right_flag == LINK)
            {
                parent = parent->right_child;
                while(parent->left_flag == LINK)
                {
                    parent = parent->left_child;
                }
            }
            temp = parent;
        }
    }
}
//三.6 销毁后序线索二叉树
//通过遍历的顺序,依次保存上一个并销毁
void destroy_last(Bin_tree root)
{
    Tree_node *temp = root->left_child;
    Tree_node *parent = NULL;
    while(TRUE)
    {
        while(temp->left_flag == LINK)
        {
            temp = temp->left_child;
        }
        if(temp->right_flag == LINK)
        {
            temp = temp->right_child;
        }
        else
            break;                           //找到最左节点
    }
    while(temp != root)
    {
        parent = get_parent(root, temp);
        if(parent == root)
        {
            free(temp);
            temp = root;
        }
        else if(parent->right_flag == THREAD || temp == parent->right_child)
        {
            free(temp);
            temp = parent;
        }
        else
        {
            while(parent->right_flag == LINK)
            {
                parent = parent->right_child;
                while(parent->left_child == LINK)
                {
                    parent = parent->left_child;
                }
            }
            free(temp);
            temp = parent;
        }
    }
}

五. 函数功能检测

• main.c

#include <stdio.h>
#include "thread_tree.h"

#define _PRINT_TREE_  1

int main(int argc, char **argv)
{
    Bin_tree root0 = NULL;
    Bin_tree root1 = NULL;
    Bin_tree root2 = NULL;
    Bin_tree root3 = NULL;
    Bin_tree root4 = NULL;
    Bin_tree root5 = NULL;
//  char *str = "ABC####";
    char *str0 = "ABC##DE##F##GH#I##J##";
    char *str1 = "ABCE###DF##G##HI##J##";
    char *str2 = "ABCD###E#F##G#HI##J##";
    Boolean equal = FALSE;

    Tree_node *p_node = NULL;

    printf("\n**********************************************************************************\n");
    printf("一.1.创建二叉树\n");

    root0 = create_tree(&str0);    //二叉树的创建
    root1 = create_tree(&str1);    //二叉树的创建
    root2 = create_tree(&str2);    //二叉树的创建

#if _PRINT_TREE_
    printf("     root0:                root1:                 root2:             \n");   
    printf("                  A                   A               A              \n");
    printf("                /   \\               /   \\           /   \\         \n");
    printf("               B     G             B     H         B     G           \n");
    printf("              / \\    / \\          / \\   /         / \\     \\     \n");
    printf("             C   D  H   J        C   D  I        C   E     H         \n");
    printf("                / \\  \\          /   / \\  \\      /    \\    / \\  \n");
    printf("               E   F  I        E   F   G  J    D      F  I   J       \n");            

    printf("\n**********************************************************************************\n");
#endif

    printf("二.遍历二叉树：\n");
    printf("pre order root0 :\n");
    pre_order_print(root0);
    printf("\n");


    printf("mid order root1 :\n");
    mid_order_print(root1);
    printf("\n");


    printf("last order root2 :\n");
    last_order_print(root2);
    printf("\n");

    printf("\n**********************************************************************************\n");
    printf("\n遍历前序线索二叉树:\n");
    root3 = create_pre_thread(root0);

    pre_order_print_thread(root3);
    printf("\n");

    p_node = root3->left_child->left_child->right_child;
    printf("front is : %c  ,",front_in_pre(root3, p_node)->data);
    printf("The node: %c  ,",p_node->data);
    printf("behind is : %c\n",behind_in_pre(root3, p_node)->data);


    printf("\n遍历中序线索二叉树:\n");
    root4 = create_mid_thread(root1);

    mid_order_print_thread(root4);
    printf("\n");

    p_node = root4->left_child->left_child->right_child;
    printf("front is : %c  ,",front_in_mid(root4, p_node)->data);
    printf("The node: %c  ,",p_node->data);
    printf("behind is : %c\n",behind_in_mid(root4, p_node)->data);

    printf("\n遍历后序线索二叉树:\n");
    root5 = create_last_thread(root2);
    
    last_order_print_thread(root5);
    printf("\n");
    
    p_node = root5->left_child->left_child->right_child;
    printf("front is : %c  ,",front_in_last(root5, p_node)->data);
    printf("The node: %c  ,",p_node->data);
    printf("behind is : %c\n",behind_in_last(root5, p_node)->data);

    //destroy_tree(&root);
    destroy_pre(root3);
    destroy_mid(root4);
    destroy_last(root5);
    printf("\n");
    return 0;
}

• 运行结果

root@aemonair:~thread_tree# cc.sh *.c
Compiling ...
-e CC      dlist.c main.c queue.c stack.c thread_tree.c tools.c -g -lpthread -lm
-e         Completed .
-e         Wed Aug 10 19:01:18 CST 2016
root@aemonair:~thread_tree# ./dlist 

**********************************************************************************
一.1.创建二叉树
     root0:                root1:                 root2:             
                  A                   A               A              
                /   \               /   \           /   \         
               B     G             B     H         B     G           
              / \    / \          / \   /         / \     \     
             C   D  H   J        C   D  I        C   E     H         
                / \  \          /   / \  \      /    \    / \  
               E   F  I        E   F   G  J    D      F  I   J       

**********************************************************************************
二.遍历二叉树：
pre order root0 :
A B C D E F G H I J 
mid order root1 :
E C B F D G A I H J 
last order root2 :
D C F E B I J H G A 

**********************************************************************************

遍历前序线索二叉树:
  A  B  C  D  E  F  G  H  I  J
front is : C  ,The node: D  ,behind is : E

遍历中序线索二叉树:
  E  C  B  F  D  G  A  I  H  J
front is : F  ,The node: D  ,behind is : G

遍历后序线索二叉树:
  D  C  F  E  B  I  J  H  G  A
front is : F  ,The node: E  ,behind is : B

六. 总结

线索二叉树,将二叉树之间用线索相连,将没用到的指针用起来,将各个节点见关系串联起来.
在实现的过程中,某一个节点的顺序和其父节点或者兄弟节点之间的关系由节点之间的指针关系相当密切.
线索二叉树作为一种数据结构,各种操作思想也是很重要的~