类的声明及其构造析构函数：
#ifndef MIDTHREADBINTREE_H
#define MIDTHREADBINTREE_H

#include<iostream.h>
#include<stdlib.h>
#include"LinkedStack.h"

//////////////////////////////////////////////////
//ThreadNode结构
//中序线索二叉书树的结点定义
//////////////////////////////////////////////////
template<class T>
struct ThreadNode
{
    int ltag,rtag;              //是否存放前后驱还是左右子树的标志
    ThreadNode<T>* leftChild;   //左子树或者前驱结点指针
    ThreadNode<T>* rightChild;  //右子树或者后继结点指针
    T data;                     //数据区

    ThreadNode(const T item)    //构造函数
    {
        data=item;              //初始化数据域
        leftChild=NULL;         //初始化左子树指针
        rightChild=NULL;        //初始化右子树指针
        ltag=0;rtag=0;          //线索标志初始化为0, 表示存放的是子树的指针
    };
};
////////////////////////////ThreadNode结点定义结束

//////////////////////////////////////////////////
//MidThreadBinTree类模板
//线索二叉树类模板的声明和定义
//////////////////////////////////////////////////
template<class T>
class MidThreadBinTree
{
protected:
    //树根指针
    ThreadNode<T>* root;      
    T RefValue;

    //读入描述字符串建立二叉树
    void CreateBinTree(char* BinStr
        ,ThreadNode<T>*& subTree);
    //二叉树的中续线索化
    void CreateMidThread(ThreadNode<T>* current
        ,ThreadNode<T>*& pre);
    //递归释放当前线索二叉树的内存空间
    void Destroy(ThreadNode<T>* subTree);
    //判断指定内容的结点在以subTree为根的二叉树中是否存在
    bool Exist(T item,ThreadNode<T>* subTree);
    //在以subTree为根的二叉树中寻找指定内容的结点
    ThreadNode<T>* Find(T item,ThreadNode<T>* subTree);
public:
    //构造函数,构造一棵空线索二叉树
    MidThreadBinTree(T RV):root(NULL),RefValue(RV){};
    //构造函数通过描述字符串构造二叉树
    MidThreadBinTree(char* s,T value);
    //析构函数,释放二叉树的内存空间
    ~MidThreadBinTree()
    {Destroy(root);
    cout<<"线索二叉树的内存已经释放!"<<endl;};

    //得到当前线索二叉树的树根
    ThreadNode<T>* getRoot()
    {return root;};
    //中序线索化一棵二叉树
    void CreateMidThread();
    //寻找当前current所指向的二叉树中序序列中的第一个结点的指针
    ThreadNode<T>* First(ThreadNode<T>* current);
    //寻找当前current所指向的二叉树中序序列中的最后一个结点的指针
    ThreadNode<T>* Last(ThreadNode<T>* current);
    //寻找当前current结点的中序列的直接后继
    ThreadNode<T>* Next(ThreadNode<T>* current);
    //寻找当前current结点的中序列的直接前驱
    ThreadNode<T>* Prior(ThreadNode<T>* current);
    //利用中序线索前序遍历二叉树
    void preOder(void (*visit)(ThreadNode<T>* p));
    //利用中序线索进行二叉树的后续遍历
    void postOder(void (*visit)(ThreadNode<T>* p));
    //在二叉树中寻找指定内容的结点
    ThreadNode<T>* Find(T item)
    {return Find(item,root);};
    //寻找当前结点current的父结点                          
    ThreadNode<T>* Parent(ThreadNode<T>* current);
    //在指定结点s的右子结点的位置插入一结点r
    //，且保持现有的中序线索不变
    void InsertRight(ThreadNode<T>* s,ThreadNode<T>* r);
    //在指定结点s的左子结点的位置插入一结点r，
    //且保持现有的中序线索不变
    void InsertLeft(ThreadNode<T>* s,ThreadNode<T>* r);
    //删除s结点的右子结点
    void DeleteRight(ThreadNode<T>* s);
    //递归:建立中序的算法
    void CreateThread(ThreadNode<T>* subTree);
};
////////////////////MidThreadBinTree类模板声明结束

//////////////////////////////////////////////////
//构造函数
//通过描述字符串建立一棵二叉树
//////////////////////////////////////////////////
template<class T>
MidThreadBinTree<T>::MidThreadBinTree(char* s,T value)
{
    RefValue=value;          //初始化结束符号
    CreateBinTree(s,root);   //二叉树的创建
};
//////////////////////////////带参数的构造函数结束

中序线索二叉树的常用算法：
//////////////////////////////////////////////////
//First()公有成员函数
//得到以current为根结点的二叉树中序序列的第一个结点
//////////////////////////////////////////////////
template<class T>
ThreadNode<T>*
MidThreadBinTree<T>::First(ThreadNode<T>* current)
{
    ThreadNode<T>* p=current;
    //即从根结点开始不停从右子树进入
    while(p->ltag==0)
        p=p->leftChild;
    //返回指针
    return p;
};
///////////////////////////////////First()函数结束

//////////////////////////////////////////////////
//Last()公有成员函数
//寻找current根的线索二叉树中中序序列的最后一个结点
//////////////////////////////////////////////////
template<class T>
ThreadNode<T>*
MidThreadBinTree<T>::Last(ThreadNode<T>* current)
{
    ThreadNode<T>* p=current;
    //找最右边的结点即最后一个结点
    while(p->rtag==0)
        p=p->rightChild;
    //返回指针
    return p;
};
////////////////////////////////////Last()函数结束

//////////////////////////////////////////////////
//Next()公有成员函数
//找当前的current结点的后继结点的指针
//////////////////////////////////////////////////
template<class T>
ThreadNode<T>*
MidThreadBinTree<T>::Next(ThreadNode<T>* current)
{
    //把当前结点的右子树指针放入p
    ThreadNode<T>* p=current->rightChild;

    //如果存放的是子树指针
    if(current->rtag==0)
        //返回右子树的中序序列的第一个结点
        return First(p);
    //rtag==1就表示current的rightChild内放的就是后继结点的指针
    else
        return p;
};
////////////////////////////////////Next()函数结束

//////////////////////////////////////////////////
//prior()公有成员函数
//得到当前结点current的前驱结点的指针
//////////////////////////////////////////////////
template<class T>
ThreadNode<T>* MidThreadBinTree<T>::Prior(
            ThreadNode<T>* current)
{
    ThreadNode<T>* p=current->leftChild;
    //如果是指向左子树的指针
    if(current->ltag==0)
        //返回左子树的中序序列的最后一个结点
        return Last(p);
    else
        return p;
};
///////////////////////////////////prior()函数结束

//////////////////////////////////////////////////
//preOder()公有成员函数
//利用中序线索前序遍历二叉树
//////////////////////////////////////////////////
template<class T>
void MidThreadBinTree<T>::preOder(void
            (*visit)(ThreadNode<T>* p))
{
    ThreadNode<T>* p=root;                  //从根结点开始遍历
 
    while(p!=NULL)
    {
        visit(p);                           //访问当前结点
        if(p->ltag==0)                      //如果当前结点p有左子树且不空
            p=p->leftChild;                 //进入左子树

        else if(p->ltag==1 && p->rtag==0)   //如果当前结点没有左子树
            p=p->rightChild;                //进入右子树

        else if(p->ltag==1 && p->rtag==1)   //如果当前的结点是叶子结点
        {
            while(p->rtag==1 && p->rightChild!=NULL)
                p=p->rightChild;            //顺着后继线索寻找当前结点p的后继
            p=p->rightChild;                //进入右子树
        }
    }
};
/////////////////////////////////preOder()函数结束

ps:利用中序线索进行后续遍历还没写出来。

//////////////////////////////////////////////////
//Find()公有成员函数
//在二叉树中寻找指定内容的结点
//////////////////////////////////////////////////
template<class T>
ThreadNode<T>* MidThreadBinTree<T>::Find(
            T item,ThreadNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        //如果subTree里的内容就是x
        if(subTree->data==item)
            return subTree;
        //如果不是
        else
        {
            ThreadNode<T>* pl=
                Find(item,subTree->leftChild);
            ThreadNode<T>* pr=
                Find(item,subTree->rightChild);
            //递归搜索左右子树
            if(pl!=NULL)
                return pl;
            else if(pr!=NULL)
                return pr;
            //左右子树中都没有x结点就返回NULL
            else
                return NULL;
        }
    }
    else
        return NULL;
};
////////////////////////////////////Find()函数结束

ps:这个算法我写的和很多教材上的思想不一样，教材上的代码我看不懂，就自己写了
但确实费了不少心血。
//////////////////////////////////////////////////
//Parent()私有成员函数
//利用中序线索寻找指定结点current的父结点
//////////////////////////////////////////////////
template<class T>
ThreadNode<T>* MidThreadBinTree<T>::Parent(
                ThreadNode<T>* current)
{
    //如果根结点没有父结点
    if(current==NULL || current==root)
    {
        cout<<"当前结点没有父结点!"<<endl;
        return NULL;
    }
    //定义一个指针从指定结点current开始寻找其父结点
    ThreadNode<T>* p=current;

    //从当前结点的左结点开始找
    
    int out=p->ltag;    //用于记录当前的结点p是子树结点
                        //还是前驱结点(0:子树结点,1:前驱结点)
    p=p->leftChild;     //先从左边走一个结点
    while(p!=NULL && !(p->ltag==0 && p->leftChild==current)
        && !(p->rtag==0 && p->rightChild==current))
    {
        if(out==0)      //如果当前的结点是上个结点的右子结点     
        {
            out=p->ltag;//表示下次要从左边走
            p=p->leftChild;
        }
        else if(out==1) //如果当前的结点是上个结点的前驱结点
        {
            out=0;      //表示下次从右边走
            p=p->rightChild;
        }
    }
    if(p!=NULL)
        return p;

    //如果从左边找不到，则从当前结点的右结点开始找
    p=current;
    out=p->rtag;         //用于记录当前的结点p是子树结点
                         //还是后继结点(0:子树结点,1:后继结点)
    p=p->rightChild;     //先从右边走一个结点
    while(p!=NULL && !(p->ltag==0 && p->leftChild==current)
        && !(p->rtag==0 && p->rightChild==current))
    {
        if(out==0)      //如果当前的结点是上个结点的左子结点     
        {
            out=p->rtag;//表示下次要从右边走
            p=p->rightChild;
        }
        else if(out==1) //如果当前的结点是上个结点的后继结点
        {
            out=0;      //表示下次从左边走
            p=p->leftChild;
        }
    }
    return p;
};    
//////////////////////////////////Parent()函数结束

结点插入和删除的算法：
//////////////////////////////////////////////////
//公有成员函数InsertRight()
//在指定结点s的右子结点的位置插入一结点r，
//且保持现有的中序线索不变
//////////////////////////////////////////////////
template<class T>
void MidThreadBinTree<T>::InsertRight(
            ThreadNode<T>* s,ThreadNode<T>* r)
{
    //如果原来该结点s没有右子女结点
    if(s->rtag==1)
    {
        //处理后继
        r->rightChild=s->rightChild;//新结点r的后继就是原来s结点的后继
        r->rtag=1;                  //r结点的后继标志
        s->rtag=0;                  //s结点的右指针域变成了子树指针

        //挂入
        s->rightChild=r;            //把结点r挂入s的右子结点的位置

        //处理前驱
        r->leftChild=s;             //s结点是r结点的前驱
        r->ltag=1;                  //r结点的左指针域变成了前驱结点的指针
    }
    //如果原来的结点s有自己的子女结点
    else                           
    {
        //把右子树挂入结点r
        r->rightChild=s->rightChild;  //把s结点的右子树根结点挂入r结点的右指针域
        r->rtag=0;                    //修改r结点对应的标志

        //把r结点挂入s结点的右子树的位置
        s->rightChild=r;
        
        //处理前驱
        First(r->rightChild)->leftChild=r;//r成为原来的右子树的新的前驱结点

        //s是r的前驱
        r->leftChild=s;               
        r->ltag=1;
    }
};
/////////////////////////////InsertRight()函数结束

//////////////////////////////////////////////////
//公有成员函数InsertLeft()
//在指定结点s的左子结点的位置插入一结点r，
//且保持现有的中序线索不变
//////////////////////////////////////////////////
template<class T>
void MidThreadBinTree<T>::InsertLeft(
            ThreadNode<T>* s,ThreadNode<T>* r)
{
    //如果原来该结点s没有左子女结点
    if(s->ltag==1)
    {
        //处理前驱
        r->leftChild=s->leftChild;  //新结点r的前驱就是原来s结点的前驱
        r->ltag=1;                  //r结点的前驱标志
        s->ltag=0;                  //s结点的左指针域变成了子树指针

        //挂入
        s->leftChild=r;             //把结点r挂入s的左子结点的位置

        //处理后继
        r->rightChild=s;            //s结点是r结点的后继
        r->rtag=1;                  //r结点的右指针域变成了后继结点的指针
    }
    //如果原来的结点s有自己的子女结点
    else                           
    {
        //把左子树挂入结点r
        r->leftChild=s->leftChild;  //把s结点的左子树根结点挂入r结点的左指针域
        r->ltag=0;                  //修改r结点对应的标志

        //把r结点挂入s结点的左子树的位置
        s->leftChild=r;
        
        //处理后继
        Last(r->leftChild)->rightChild=r;//r成为原来的左子树的新的后继结点

        //s是r的后继
        r->rightChild=s;               
        r->rtag=1;
    }
};
/////////////////////////////InsertRight()函数结束

//////////////////////////////////////////////////
//公有DeleteRight()函数
//删除指定结点s的右子女结点
//////////////////////////////////////////////////
template<class T>
void MidThreadBinTree<T>::DeleteRight(ThreadNode<T>* s)
{
    //得到被删结点的指针r
    ThreadNode<T>* r=s->rightChild;
    if(r==NULL)
    {
        cout<<"本结点没有右子结点!"<<endl;
        exit(1);
    };

    //如果被删除的结点r是个叶子结点
    if(r->rightChild==NULL && r->leftChild==NULL)
    {
        //s结点的后继就是原来r结点的后继
        s->rightChild=r->rightChild;
        //修改标志
        s->rtag=1;
    }
    //被删除的结点r只有右子树,没有左子树
    else if(r->ltag!=0 && r->rtag==0 && r->rightChild!=NULL)
    {
        //s成为了r的右子树中序序列的第一个前驱
        First(r->rightChild)->leftChild=s;
        //s的右子树就是原来r的右子树
        s->rightChild=r->rightChild;
    }
    //被删除的结点r只有左子树,没有右子树
    else if(r->ltag==0 && r->leftChild!=NULL && rtag!=0)
    {
        //修改后继线索
        Last(r->lefChild)->rightChild=r->rightChild;
        //修改后继标志
        Last(r->lefChild)->rtag=1;
        //把原来结点r的左子树移到s的右子树的位置
        s->rightChild=r->leftChild;
    }
    //如果被删除的结点r既有左子树又有右子树
    else if(r->ltag=0 && r->atag=0)
    {
        //找到结点r的左子树的中序最后一个结点
        ThreadNode<T>* la=Last(r->leftChild);
        //找到结点r的右子树的中序第一个结点
        ThreadNode<T>* fr=First(r->rightChild);
        //利用中序线索把fr连接到la的前面
        fr->leftChild=la;
        //把r的右子树连接到结点la的右子树位置
        la->rightChild=r->rightChild;
        la->rtag=0;
        //把原来r的左子树连接到s的右子树位置
        s->rightChild=r->leftChild;
    }
};
/////////////////////////////DeleteRight()函数结束

通过广义表描述字符串创建表的算法：
//////////////////////////////////////////////////
//CreateBinTree()私有成员函数
//通过广义表描述字符串建立一棵二叉树,通过指针返回
//////////////////////////////////////////////////
template<class T>
void MidThreadBinTree<T>::CreateBinTree(
                char* BinStr,ThreadNode<T>*& subTree)
{
    //逐个读取字符串
    int i=0;               //游标
    int k=0;               //处理标志,0表示根结点,1表示左子树,2表示
    char s;                //存放每次取出的字符
    LinkedStack<ThreadNode<char>*> LS;
                           //创建二叉树过程中用到的结点指针堆栈
    ThreadNode<char>* p;   //结点指针变量
    ThreadNode<char>* t;   //存放从堆栈中弹出的内容
    ThreadNode<char>* top; //用于存放从堆栈中取出的栈顶元素
    
    while(BinStr[i]!='#')
    {
        s=BinStr[i];
        switch(s)
        {
        case '(':
            LS.Push(p);  //把当前p的内容入栈
            k=1;         //进入左子树的处理
            break;
        case ',':
            k=2;         //进入右子树的处理
            break;
        case ')':
            LS.Pop(t);   //弹出堆栈的内容
            break;
        default:
            //如果取出的字母
            {
                //如果处理的是根结点
                if(k==0)
                {
                    //新建一个结点
                    p=new ThreadNode<char>(s);
                    //把该指针作为树的指针返回
                    subTree=p;
                }
                //如果处理的是右子树
                else if(k==1)
                {
                    //新建一个接点
                    p=new ThreadNode<char>(s);
                    //取得栈顶结点
                    LS.getTop(top);
                    //把该结点挂入栈顶的左指针域
                    top->leftChild=p;
                }
                //如果处理的是左子树
                else
                {
                    //新建一个接点
                    p=new ThreadNode<char>(s);
                    //取得栈顶结点
                    LS.getTop(top);
                    //把该结点挂入栈顶的左指针域
                    top->rightChild=p;
                };
                break;
            };
        };
        i++;
    }
};
///////////////////////////////CreateBinTree()结束

中序线索化的算法：
//////////////////////////////////////////////////
//CreateMidThread()私有成员函数
//二叉树的中序线索化
//current是遍历的当前节点的指针，pre是前驱结点指针
//////////////////////////////////////////////////
template<class T>
void MidThreadBinTree<T>::CreateMidThread(
        ThreadNode<T>* current,ThreadNode<T>*& pre)
{
    //如果当前结点为空则返回
    if(current==NULL)
        return;
    //如果当前结点不空
    else
    {
        //中序线索化左子树
        CreateMidThread(current->leftChild,pre);

        //建立当前结点的前驱线索
        if(current->leftChild==NULL)          //如果当前结点的左指针域为空
        {
            current->leftChild=pre;           //在左子树的指针域里放前驱结点pre指针   
            current->ltag=1;                  //把标志置为1,表示存放的是前驱结点的指针
        };
        //建立当前结点的后继线索
        if(pre!=NULL && pre->rightChild==NULL)//如果前驱结点pre不空,且pre右指针域为空
        {
            pre->rightChild=current;          //把当前结点的指针赋值给前驱结点pre的右指针域
            pre->rtag=1;                      //把标志置为1,表示存放的是pre的后继结点的指针
        };
        pre=current;                          //前驱结点按找中序序列向后推进一格
        
        //中序线索化右子树
        CreateMidThread(current->rightChild,pre);
    };
};
/////////////////////////CreateMidThread()函数结束

//////////////////////////////////////////////////
//CreateMidThread()共有成员函数
//中序线索化一棵二叉树
//////////////////////////////////////////////////
template<class T>
void MidThreadBinTree<T>::CreateMidThread()
{
    ThreadNode<T>* pre=NULL;      //前驱结点的指针
    
    if(root!=NULL)
    {
        CreateMidThread(root,pre);//中序线索化
        pre->rightChild=NULL;     //最后处理中序最后一个结点  
        pre->rtag=1;              //把标志清置为1
    };
};
/////////////////////////CreateMidThread()函数结束

[[it] 本帖最后由 geninsf009 于 2008-11-30 20:22 编辑 [/it]]

//////////////////////////////////////////////////
//Destroy()私有成员函数
//把线索二叉树对应的结点的内存空间释放
//////////////////////////////////////////////////
template<class T>
void MidThreadBinTree<T>::Destroy(ThreadNode<T>* subTree)
{
    if(subTree!=NULL)
    {
        //释放左右子树的内存空间
        if(subTree->leftChild!=NULL
            && subTree->ltag==0)
            Destroy(subTree->leftChild);
        if(subTree->rightChild!=NULL
            && subTree->rtag==0)
            Destroy(subTree->rightChild);
        //释放当前结点的内存空间
        delete subTree;
    };
};
/////////////////////////////////Destroy()函数结束

//////////////////////////////////////////////////
//Exist()私有成员函数
//判断指定内容的结点在以subTree为根的二叉树中是否存在
//////////////////////////////////////////////////
template<class T>
bool MidThreadBinTree<T>::Exist(
        T item,ThreadNode<T>* subTree)
{
    //如果根结点就含有item
    if(item==subTree->data)
        return true;
    else
    {
        //递归搜索左右子树,只要其中一个含有就返回true
        return Exist(item,subTree->leftChild)
            ||Exist(item,subTree->rightChild);
    }
};
///////////////////////////////////Exist()函数结束

#endif

digni