帖一个《二叉树线索化》程序，前几天才写的，还没查错！
前几天才写完，没查错，写成模板了，帮我看看程序 在线索化的理解上有无错误。对了今天到百度搜以前我的各种帖子，才发现我有很久没来这个论坛了（以前发的帖都是2007年的），sorry！！！
今天心血来潮，发下贴
程序代码：
/*******************************************************
*
* 二叉树线索化
*
* by Bghost
*
* 2010-06-24
*
*
*
*******************************************************/
template<class T>
class node
{
public:
T value;
int lTag; //0为节点， 1为线索
node *left;
int rTag;
node *right;
};
template<class T>
class BinaryTreeThread
{
private:
node<T> *buffer;
node<T> *pre;
private:
node<T>* createNode(); //创建节点
void visitNode(node<T> *one); //处理程序
void preThread(node<T> *p); //前序线索辅助
void inThread(node<T> *p); //中序线索辅助
void postThread(node<T> *p); //后序线索辅助
public:
BinaryTreeThread();
~BinaryTreeThread();
void createTree(); //创建树
void preOrderThread(); //前序线索化
void preOrderTraverse(); //前序线索化遍历
void inOrderThread(); //中序线索化
void inOrderTraverse(); //中序线索化遍历
void postOrderThread(); //后序线索化
void postOrderTraverse(); //后序线索化遍历
};
template<class T>
BinaryTreeThread<T>::BinaryTreeThread()
{
buffer = new node<T>();
buffer->lTag = 0;
buffer->rTag = 1;
buffer->left = NULL;
buffer->right = buffer;
}
template<class T>
BinaryTreeThread<T>::~BinaryTreeThread()
{
}
template<class T>
node<T>* BinaryTreeThread<T>::createNode()
{
T val;
cin>>val;
node<T> *now;
if(val == '*')
{
now = NULL;
}else
{
now = new node<T>();
now->value = val;
now->left = createNode();
now->right = createNode();
}
return now;
}
template<class T>
void BinaryTreeThread<T>::createTree()
{
buffer->left = createNode();
buffer->right = buffer;
}
template<class T>
void BinaryTreeThread<T>::visitNode(node<T> *one)
{
cout<<one->value;
}
template<class T>
void BinaryTreeThread<T>::preThread(node<T> *p)
{
if(p != NULL)
{
if(p->left == NULL)
{
p->lTag = 1;
p->left = pre;
}
if(pre->right == NULL)
{
pre->rTag = 1;
pre->right = p;
}
pre = p;
preThread(p->left);
preThread(p->right);
}
}
template<class T>
void BinaryTreeThread<T>::preOrderThread()
{
node<T> *p = buffer;
pre = NULL;
p->lTag = 0; //连接
p->rTag = 1; //线索
p->right = p;
if(buffer->left == NULL)
{//无root节点
p->left = p;
}else
{
p->left = buffer->left;
pre = p;
p = p->left;
preThread(p);
buffer->right = pre;
buffer->rTag = 1;
pre->right = buffer;
pre->rTag = 1;
}
}
template<class T>
void BinaryTreeThread<T>::preOrderTraverse()
{
node<T> *p = buffer->left;
while(p != buffer)
{
visitNode(p);
while(p->lTag == 0)
{
p = p->left;
visitNode(p);
}
p = p->right;
}
}
template<class T>
void BinaryTreeThread<T>::inThread(node<T> *p)
{
if(p != NULL)
{
inThread(p->left);
if(p->left == NULL)
{
p->lTag = 1;
p->left = pre;
}
if(pre->right == NULL)
{
pre->rTag = 1;
pre->right = p;
}
pre = p;
inThread(p->right);
}
}
template<class T>
void BinaryTreeThread<T>::inOrderThread()
{
node<T> *p = buffer;
pre = NULL;
p->lTag = 0; //连接
p->rTag = 1; //线索
p->right = p;
if(buffer->left == NULL)
{//无root节点
p->left = p;
}else
{
p->left = buffer->left;
pre = p;
p = p->left;
inThread(p);
buffer->right = pre;
buffer->rTag = 1;
pre->right = buffer;
pre->rTag = 1;
}
}
template<class T>
void BinaryTreeThread<T>::inOrderTraverse()
{
node<T> *p = buffer->left;
while(p != buffer)
{
while(p->lTag == 0)
p = p->left;
visitNode(p);
while(p->rTag == 1 && p->right != buffer)
{
p = p->right;
visitNode(p);
}
p = p->right;
}
}
template<class T>
void BinaryTreeThread<T>::postThread(node<T> *p)
{
if(p != NULL)
{
postThread(p->left);
if(p->left == NULL)
{
p->lTag = 1;
p->left = pre;
}
if(pre->right == NULL)
{
pre->rTag = 1;
pre->right = p;
}
postThread(p->right);
pre = p;
}
}
template<class T>
void BinaryTreeThread<T>::postOrderThread()
{
node<T> *p = buffer;
pre = NULL;
p->lTag = 0; //连接
p->rTag = 1; //线索
p->right = p;
if(buffer->left == NULL)
{//无root节点
p->left = p;
p->right = p;
}else
{
p->left = buffer->left;
pre = p;
p = p->left;
postThread(p);
buffer->right = pre;
buffer->rTag = 1;
pre->right = buffer;
pre->rTag = 1;
}
}
template<class T>
void BinaryTreeThread<T>::postOrderTraverse()
{
node<T> *p = buffer->left;
while(p != buffer)
{
while(p->lTag == 0)
p = p->left;
visitNode(p);
p = p->right;
}
}
