线索二叉树

data_structure

一、简介

线索二叉树是在二叉树的基础上，把空指针加以利用，通过左右type域来标记类型。生成方法是先构造二叉树，再把二叉树线索化，线索化的过程稍候会介绍。

二、线索二叉树的节点构造

先贴代码：

enum BiThrNodeType{LINK,THREAD};
template<class T>
struct BiThrNode
{
    BiThrNodeType ltype, rtype;
    T data;
    BiThrNode<T> *lchild, *rchild;
};

明显，与二叉树相比，只是多了两个枚举类型的数据成员，通俗的解释，

• LINK标志表示接下来的是他的孩子，
• THREAD表示接下来的前驱或者后继。

同时贴上InBiThrTree的头文件，里面的函数，会在下面介绍。

template<class T>
class InBiThrTree
{
private:
    BiThrNode<T> *root;//根节点
    BiThrNode<T> *prenode;//前置点
    void InThreaded(BiThrNode<T> *&p);
    BiThrNode<T> *CreateByPre(vector<T> &pre, int &i);
public:
    InBiThrTree(){ root = NULL; }
    InBiThrTree(vector<T> &pre);                //根据先序序列创建二叉树
    void InThreaded();                          //中序线索化
    //~InBiThrTree();                              //析构函数
    BiThrNode<T> *GetNext(BiThrNode<T> *p);     //求中序遍历中的后继结点
    BiThrNode<T> *GetPrev(BiThrNode<T> *p);     //求中序遍历中的前驱结点
    void Travese();                             //利用线索进行中序遍历
    BiThrNode<T>* GetParent(BiThrNode<T> *p);   //求父结点地址
    BiThrNode<T>* GetRoot(){ return root; }     //求根结点
    BiThrNode<T>* Search(T e);          //根据值e查找结点1
    BiThrNode<T>* Search(BiThrNode<T> *p,T e); //在以p为根的树查找1
    void setPre(){prenode=NULL;}        //置空前置点     
};

三、函数介绍

3.1、根据先序序列创建二叉树

说明一下，这一块和前面的树基本没有差异，只是在其中多了个对枚举类型的置空，即默认所有标志位均为孩子位。

//根据先序序列创建二叉树
template<class T>
InBiThrTree<T>::InBiThrTree(vector<T> &pre)
{
    int i = 0;      //向量pre的下标变量
    root = CreateByPre(pre, i);
}
template<class T>
BiThrNode<T> *InBiThrTree<T>::CreateByPre(vector<T> &pre, int &i)
{
    T e = pre[i]; i++;//提取当前数据
    if (e == '*')
        return NULL;//若是特殊数据，返回空指针
    BiThrNode<T> *p = new BiThrNode<T>;//创建新结点
    p->data = e;
    p->ltype = LINK;
    p->rtype = LINK;
    p->lchild = CreateByPre(pre, i);//创建左子树
    p->rchild = CreateByPre(pre, i);//创建右子树
    return p;
}

3.2， 二叉树的线索化

//二叉树的中序线索化算法
template<class T>
void InBiThrTree<T>::InThreaded()
{
    InThreaded(root);
}
template<class T>
void InBiThrTree<T>::InThreaded(BiThrNode<T> *&p)
{
    if (p == NULL)                          //如果二叉链表p为空，则空操作返回
        return;
    InThreaded(p->lchild);                  //对p的左子树建立线索
    //对p所指结点建立线索
    if (p->lchild == NULL)                  //对p的左指针处理
    {
        p->ltype = THREAD;
        p->lchild = prenode;
    }
    if (p->rchild == NULL)                  //对p的右指针处理
        p->rtype = THREAD;
    if (prenode != NULL)
    {
        if (prenode->rtype == THREAD)       //设置prenode的后续线索
            prenode->rchild = p;
    }
    prenode = p;
    InThreaded(p->rchild);                  //对p的右子树建立线索
}

这边是比较关键的算法，书上是这么说的

• 如果二叉链表p为空，则空操作返回
• 对p的左子树建立线索
• 对p所指结点建立线索
  

  若p没有左孩子，则为p加上前驱线索
  若p没有右孩子，则将p右标志置为1
  若结点prenode右标志为1，则为prenode加上后继线索
  令prenode指向刚刚访问的结点p

• 对p的右子树建立线索

下面，就是这棵树线索化前后的图片：
线索前：

线索后：

3.3、一些查找函数

由于时间关系，下面这些函数不做详细介绍，都挺简单的。

//在中序线索二叉树中求结点的后继指针的算法
template<class T>
BiThrNode<T> *InBiThrTree<T>::GetNext(BiThrNode<T> *p)
{
    if (p->rtype == THREAD)
        return p->rchild;
    p = p->rchild;
    while (p->ltype == LINK)
        p = p->lchild;
    return p;
}
//在中序线索二叉树中求结点的前驱指针的算法
template<class T>
BiThrNode<T> *InBiThrTree<T>::GetPrev(BiThrNode<T> *p)
{
    if (p->ltype == THREAD)
        return p->lchild;
    p = p->lchild;
    while (p->rtype == LINK)
        p = p->rchild;
    return p;
}
//中序遍历中序线索二叉树
string result;
template<class T>
void InBiThrTree<T>::Travese()
{
    BiThrNode<T> *p = root;
    while (p->ltype == LINK)            //找到中序遍历的起点
        p = p->lchild;
    while (p != NULL)
    {
        result+=p->data;
        cout << p->data;
        p = GetNext(p);
    }
}
//在中序线索化树中，查找结点的父结点
template<class T>
BiThrNode<T> *InBiThrTree<T>::GetParent(BiThrNode<T> *p)
{
    if (p == NULL)
        return NULL;
    BiThrNode<T> *parent;
    parent = p;
    while (parent->rtype == LINK)
        parent = parent->rchild;
    parent = parent->rchild;            //parent是*p的最右下方结点的后继指针
    if (parent && parent->lchild == p)
        return parent;                  //猜测*p是否是*parent的左孩子
    parent = p;
    while (parent->ltype == LINK)
        parent = parent->lchild;
    parent = parent->lchild;            //parent是*p的最左下方结点的前驱指针
    return parent;                      //parent一定是*p的父指针
}
/*根据值e查找结点*/
template <class T>
BiThrNode<T>* InBiThrTree<T>::Search(T e)
{
    return Search(root,e);
}
template<class T>
BiThrNode<T>* InBiThrTree<T>::Search(BiThrNode<T> *p,T e)
{
    if(p==NULL)         //整棵树空。查找失败，返回上一层
        return NULL;
    if(p->data==e)      //当前节点值正确，返回当前节点
        return p;
    BiThrNode <T> *q=NULL;
    if (p->ltype!=THREAD)
        q=Search(p->lchild,e);  //若此节点不空，并且此节点数据不匹配，找左子树
    if(q!=NULL)         //若左边找到了，返回找到的节点给上一层。
        return q;
    if (p->rtype!=THREAD)
        return Search(p->rchild,e); //若左边没找到，返回右子树找到的结果，可以为NULL,可以为节点、
    return NULL;
}

需要注意一点，不能把按值查找直接搬过来，需要改下判断条件就可以了，其他的函数，书本上都有，不做过多解释。

四、测试函数

int main()
{
    vector<char> a;
    //char c[20]="ab*c**de**f**";
    //char c[20]="abd**e**cf***";
    char c[20]="abd**e**cf***";
    cout<<"树的前序向量："<<c<<endl;
    for (int i = 0; i < strlen(c); i++)
    {
        a.push_back(c[i]);
    }
    InBiThrTree <char> A(a);
    A.setPre();//置空
    A.InThreaded();
    cout<<"中序遍历打印：";
    A.Travese();    //  
    cout<<endl;
    for (i=0;i<result.length();i++)
    {
        cout<<endl;
        char c=result.at(i);
        cout<<"查找的值"<<c<<"所在节点并输出地址:";
        BiThrNode<char> *tmp = A.Search(c);
        cout<<tmp<<endl;
        cout<<tmp->data<<"节点的前驱:";
        if (A.GetPrev(tmp)!=NULL)
        {
            cout<<A.GetPrev(tmp)<<" 值为："<<A.GetPrev(tmp)->data<<endl;
        }
        else
            cout<<NULL<<endl;
        cout<<tmp->data<<"节点的后继:";
        if (A.GetNext(tmp)!=NULL)
        {
            cout<<A.GetNext(tmp)<<" 值为："<<A.GetNext(tmp)->data<<endl;
        }
        else
            cout<<NULL<<endl;
        cout<<tmp->data<<"节点的父节点:";
        if (A.GetParent(tmp)!=NULL)
        {
            cout<<A.GetParent(tmp)<<" 值为："<<A.GetParent(tmp)->data<<endl;
        }
        else
            cout<<NULL<<endl;
        cout<<endl;
    }
    return 0;
}

这边需要注意一下，在线索化之前，需要把PreNode置空，便于第一个THREAD节点的操作。

测试树是这棵：

测试结果如下：

2015年5月4日晚