再发一些中序线索二叉树抽象数据类型及算法实现代码，俺的代码都是自己写的，大家参考。
类的声明及其构造析构函数：#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); //二叉树的创建
};
//////////////////////////////带参数的构造函数结束
