线索二叉树的线索化跟析构
前段时间学习的二叉树的相关操作，现在又开始学习线索二叉树的相关操作，发现网的一些代码有问题，所以写了这篇博客与大家分享，以下这些代码都是我亲自编写以及调试运行过，有什么错的还请大家指出。
线索二叉树结点的定义如下：
template <class T>
class ThreadNode{//线索二叉树结点声明
private:
int LThread,RThread;
ThreadNode<T>* left;
ThreadNode<T>* right;
T data;
public:
ThreadNode(const T& item):data(item),left(NULL),right(NULL),LThread(0),RThread(0){}
ThreadNode<T>* GetLeft()const{return left;}
ThreadNode<T>* GetRight()const{return right;}
void SetLeft(ThreadNode<T>* t){left=t;}
void SetRight(ThreadNode<T>* t){right=t;}
void SetData(const T& item){data=item;}
void SetLThread(const int l){LThread=l;}
void SetRThread(const int r){RThread=r;}
T& GetData(){return data;}
int GetLThread(){return LThread;}
int GetRThread(){return RThread;}
};
在使用类似于二叉树的构建方法的情况下，构建一个二叉树，然后再使用线索二叉树的中序线索化函数来线索化二叉树。二叉树的线索化算法为：
算法 Inorder_threading(p) //初始调用Inorder_threading(root)
IF p≠Λ THEN
( Inorder_threading ( Left(p) ). //中序线索化p的左子树
IF Left(p) =Λ THEN //如果p没有左孩子
( Lthread(p) ← 1; //p的左指针是线索域
Left(p) ← pre; //p的左指针指向p的中根前驱
)
IF pre≠ Λ AND Right(pre) =Λ THEN //如果pre没有右孩子
( Rthread(pre) ← 1; //pre的右指针是线索域
Right(pre) ← p; //pre的右指针指向其中根后继p
)
pre ← p; //将当前访问的结点作为pre
Inorder_threading ( Right(p) );
)
按照这个算法的思想可以写出二叉树的中序线索化函数，如下：
template <class T>
void ThreadTree<T>::Inorder_threading(ThreadNode<T>* t){
//ThreadNode<T>* pred=NULL;
if(t!=NULL){
Inorder_threading(t->GetLeft());//中序化root的左子树
if(t->GetLeft()==NULL){ //如果root没有左子树
t->SetLThread(1); //root的左指针是线索域
t->SetLeft(pre); //root的左指针指向root的前驱结点
}
if (pre!=NULL&& pre->GetRight()==NULL) {//如果pre没有右孩子
pre->SetRThread(1); //pre的右指针是线索域
pre->SetRight(t); //pre的右指针指向其中根
//后继结点root
}
pre=t;//请将当前访问的结点作为pred
Inorder_threading(t->GetRight());
pre->SetRThread(1);
}
}
这个函数是我自己亲自写的并且运行过之后显示正确，但是在网上的大部分二叉树中序线索化的函数中，都少了最后一个语句pre->SetRThread(1);，经过我调试之后发现如果没有这个语句，会导致在线索化的中序遍历的最后一个结点时，最后一个结点如果没有右子树，这个结点的右线索仍然会为0，这就为以后遍历等相关操作带来了麻烦。下面讨论一下线索二线树的析构，与二叉树的析构没有什么差别，只是在析构的时候要讨论结点的左线索与右线索是否为0，代码如下：
template <class T>
ThreadTree<T>::~ThreadTree(){
DeSubTree(root);
}
template <class T>
void ThreadTree<T>::Del(ThreadNode<T>* t){
/*删除给定结点t及其左右子树*/
if (t==NULL) {
return ;
}
if (t->GetLThread()==0) {
Del(t->GetLeft());
}
if (t->GetRThread()==0) {
Del(t->GetRight());
}
cout<<"成功删除结点"<<t->GetData()<<"及其子树"<<endl;
delete t;
}
template <class T>
void ThreadTree<T>::DeSubTree(ThreadNode<T>* t){
/*删除结点时还需要考虑修改父结点的指针域*/
if (t==NULL) {
return;
}
if (t==root) { //判断给定结点是否为根结点
Del(t);
root=NULL;
return;
}
ThreadNode<T>* p=t;
ThreadNode<T>* q=Father(root, p);//找p得父结点q修改父结点q的指针域
if (q->GetLeft()==p) { //只知道其父结点为
q->SetLeft(NULL);
}
if (q->GetRight()==p) {
q->SetRight(NULL);
}
Del(p);
}