线索二叉树的插入和删除

*****
*****我这有个线索二叉树的例子：
*****
*****首先需要定义线索二叉树，定义如下：
//线索二叉树结点类型存储结构体TBSTree2.h
template class TBSTree;
template class ITBSTree;
template struct THNode
{public:
int lflag,rflag;//标志域
THNode *left;//第一个孩子结点指针域
THNode *right;//下一个兄弟结点指针域
T data;//数据域
friend class TBSTree;//线索二叉树类为友元
friend class ITBSTree;//派生类
//构造函数
THNode():left(NULL),right(NULL),lflag(0),rflag(0){ }
THNode(int la,int ra,T value,THNode *fc=NULL,
THNode *ns=NULL):data(value),left(fc),
right(ns){lflag=la;rflag=ra;}
//访问指针域的成员函数
THNode* &FirstChild()
{return left;}
THNode* &NextSibling()
{return right;}
};
//线索二叉树类
template class TBSTree
{protected:
THNode *root;//根结点指针
THNode *curr;//当前结点指针
int nextC;
int priorC;
public:
//构造函数与析构函数
TBSTree(){root=curr=NULL;}
TBSTree(THNode *&tree)
{root=tree;
curr=root;
if(tree==NULL)
{nextC=1;priorC=1;}
else {nextC=0;priorC=0;}
}
//纯虚函数
virtual void First()=0;
virtual void Last()=0;
//数据检索与修改成员函数
T &Data();
};
//线索二叉树类的实现
template
T &TBSTree::Data()
{if(root==NULL)
{cout<<"二叉树空!\n";exit(1);}
return curr->data;
}
//由结点构造线索二叉树的类外一般函数
template
THNode *GetTreeNode(T item,THNode *le=NULL,
THNode *ri=NULL,int lf=0,int rf=0)
{THNode *p=new THNode;
p->data=item;p->left=le;p->right=ri;
p->lflag=lf;p->rflag=rf;
if(p==NULL)
{cerr<<"内存分配失败!\n";exit(1);}
return p;
}
//创建特定线索二叉树的类外一般函数
template
THNode *MakeCharT(THNode *&root,int num)
{THNode *b,*c,*d,*e,*f,*g,*null=NULL;
if(num==1)
{e=GetTreeNode('R');
f=GetTreeNode('W');
d=GetTreeNode('P',e,f);
g=GetTreeNode('Q');
b=GetTreeNode('N',d,g);
c=GetTreeNode('O');
root=GetTreeNode('M',b,c);
}
else {
g=GetTreeNode('G');
d=GetTreeNode('D',null,g);
b=GetTreeNode('B',d);
e=GetTreeNode('E');
f=GetTreeNode('F');
c=GetTreeNode('C',e,f);
root=GetTreeNode('A',b,c);
}
return root;
}
*****
*****接着是测试程序，代码如下：
//线索二叉树类相关操作的测试TBSTree2M.cpp
#include
#include
#include
#include
#include "TBSTree2.h"
#include "ITBSTree2.h"
void main()
{cout<<"TBSTree2M.cpp运行结果:\n";
THNode *q,*p;
q=MakeCharT(q,2);
ITBSTree t(q);
t.CreatInThread();
cout<<"二叉树的中序正向遍历序列为:\n";
t.First();
cout<<"\n二叉树的中序反向遍历序列为:\n";
t.Last();
p=MakeCharT(p,1);
ITBSTree d(p);
d.CreatInThread();
cout<<"\n二叉树的中序正向遍历序列为:\n";
d.First();
cout<<"\n二叉树的中序反向遍历序列为:\n";
d.Last();
cin.get();
}
*****
*****以下是程序运行结果，自己试试吧，先跑起来，然后慢慢看懂它：
TBSTree2M.cpp运行结果:
二叉树的中序正向遍历序列为:
D G B A E C F
二叉树的中序反向遍历序列为:
F C E A B G D
二叉树的中序正向遍历序列为:
R P W N Q M O
二叉树的中序反向遍历

咦？悬赏分没有吗？