线索二叉树

---

一、简介

线索二叉树是在二叉树的基础上，把空指针加以利用，通过左右type域来标记类型。生成方法是先构造二叉树，再把二叉树线索化，线索化的过程稍候会介绍。

二、线索二叉树的节点构造

先贴代码：

enum BiThrNodeType{LINK,THREAD};

template<class T>
struct BiThrNode
{
	BiThrNodeType ltype, rtype;
	T data;
	BiThrNode<T> *lchild, *rchild;
};

明显，与二叉树相比，只是多了两个枚举类型的数据成员，通俗的解释，

• LINK标志表示接下来的是他的孩子，
• THREAD表示接下来的前驱或者后继。

同时贴上InBiThrTree的头文件，里面的函数，会在下面介绍。

template<class T>
class InBiThrTree
{
private:
	BiThrNode<T> *root;//根节点
	BiThrNode<T> *prenode;//前置点

	void InThreaded(BiThrNode<T> *&p);
	BiThrNode<T> *CreateByPre(vector<T> &pre, int &i);

public:
	InBiThrTree(){ root = NULL; }
	InBiThrTree(vector<T> &pre);				//根据先序序列创建二叉树
	void InThreaded();							//中序线索化
	//~InBiThrTree();								//析构函数
	BiThrNode<T> *GetNext(BiThrNode<T> *p);		//求中序遍历中的后继结点
	BiThrNode<T> *GetPrev(BiThrNode<T> *p);		//求中序遍历中的前驱结点
	void Travese();								//利用线索进行中序遍历
	BiThrNode<T>* GetParent(BiThrNode<T> *p);	//求父结点地址
	BiThrNode<T>* GetRoot(){ return root; }		//求根结点
	BiThrNode<T>* Search(T e);			//根据值e查找结点1
	BiThrNode<T>* Search(BiThrNode<T> *p,T e); //在以p为根的树查找1
	void setPre(){prenode=NULL;}		//置空前置点		
};

三、函数介绍

3.1、根据先序序列创建二叉树

说明一下，这一块和前面的树基本没有差异，只是在其中多了个对枚举类型的置空，即默认所有标志位均为孩子位。

//根据先序序列创建二叉树
template<class T>
InBiThrTree<T>::InBiThrTree(vector<T> &pre)
{
	int i = 0;		//向量pre的下标变量
	root = CreateByPre(pre, i);
}
template<class T>
BiThrNode<T> *InBiThrTree<T>::CreateByPre(vector<T> &pre, int &i)
{
	T e = pre[i]; i++;//提取当前数据
	if (e == '*')
		return NULL;//若是特殊数据，返回空指针
	BiThrNode<T> *p = new BiThrNode<T>;//创建新结点
	p->data = e;
	p->ltype = LINK;
	p->rtype = LINK;
	p->lchild = CreateByPre(pre, i);//创建左子树
	p->rchild = CreateByPre(pre, i);//创建右子树
	return p;
}

3.2， 二叉树的线索化

//二叉树的中序线索化算法
template<class T>
void InBiThrTree<T>::InThreaded()
{
	InThreaded(root);
}
template<class T>
void InBiThrTree<T>::InThreaded(BiThrNode<T> *&p)
{
	if (p == NULL)							//如果二叉链表p为空，则空操作返回
		return;
	InThreaded(p->lchild);					//对p的左子树建立线索
	//对p所指结点建立线索
	if (p->lchild == NULL)					//对p的左指针处理
	{
		p->ltype = THREAD;
		p->lchild = prenode;
	}
	if (p->rchild == NULL)					//对p的右指针处理
		p->rtype = THREAD;
	if (prenode != NULL)
	{
		if (prenode->rtype == THREAD)		//设置prenode的后续线索
			prenode->rchild = p;
	}
	prenode = p;
	InThreaded(p->rchild);					//对p的右子树建立线索
}

这边是比较关键的算法，书上是这么说的

• 如果二叉链表p为空，则空操作返回
• 对p的左子树建立线索
• 对p所指结点建立线索

  若p没有左孩子，则为p加上前驱线索
  若p没有右孩子，则将p右标志置为1
  若结点prenode右标志为1，则为prenode加上后继线索
  令prenode指向刚刚访问的结点p

• 对p的右子树建立线索

下面，就是这棵树线索化前后的图片：
线索前：

线索后：

###3.3、一些查找函数
由于时间关系，下面这些函数不做详细介绍，都挺简单的。

//在中序线索二叉树中求结点的后继指针的算法
template<class T>
BiThrNode<T> *InBiThrTree<T>::GetNext(BiThrNode<T> *p)
{
	if (p->rtype == THREAD)
		return p->rchild;
	p = p->rchild;
	while (p->ltype == LINK)
		p = p->lchild;
	return p;
}

//在中序线索二叉树中求结点的前驱指针的算法
template<class T>
BiThrNode<T> *InBiThrTree<T>::GetPrev(BiThrNode<T> *p)
{
	if (p->ltype == THREAD)
		return p->lchild;
	p = p->lchild;
	while (p->rtype == LINK)
		p = p->rchild;
	return p;
}

//中序遍历中序线索二叉树
string result;
template<class T>
void InBiThrTree<T>::Travese()
{
	BiThrNode<T> *p = root;
	while (p->ltype == LINK)			//找到中序遍历的起点
		p = p->lchild;
	while (p != NULL)
	{
		result+=p->data;
		cout << p->data;
		p = GetNext(p);
	}
}

//在中序线索化树中，查找结点的父结点
template<class T>
BiThrNode<T> *InBiThrTree<T>::GetParent(BiThrNode<T> *p)
{
	if (p == NULL)
		return NULL;
	BiThrNode<T> *parent;
	parent = p;
	while (parent->rtype == LINK)
		parent = parent->rchild;
	parent = parent->rchild;			//parent是*p的最右下方结点的后继指针
	if (parent && parent->lchild == p)
		return parent;					//猜测*p是否是*parent的左孩子
	parent = p;
	while (parent->ltype == LINK)
		parent = parent->lchild;
	parent = parent->lchild;			//parent是*p的最左下方结点的前驱指针
	return parent;						//parent一定是*p的父指针
}
/*根据值e查找结点*/
template <class T>
BiThrNode<T>* InBiThrTree<T>::Search(T e)
{
	return Search(root,e);
}

template<class T>
BiThrNode<T>* InBiThrTree<T>::Search(BiThrNode<T> *p,T e)
{
	if(p==NULL)			//整棵树空。查找失败，返回上一层
		return NULL;
	if(p->data==e)		//当前节点值正确，返回当前节点
		return p;
	BiThrNode <T> *q=NULL;
	if (p->ltype!=THREAD)
		q=Search(p->lchild,e);	//若此节点不空，并且此节点数据不匹配，找左子树
	if(q!=NULL)			//若左边找到了，返回找到的节点给上一层。
		return q;
	if (p->rtype!=THREAD)
		return Search(p->rchild,e); //若左边没找到，返回右子树找到的结果，可以为NULL,可以为节点、
	return NULL;
}

需要注意一点，不能把按值查找直接搬过来，需要改下判断条件就可以了，其他的函数，书本上都有，不做过多解释。

四、测试函数

int main()
{
	vector<char> a;
	//char c[20]="ab*c**de**f**";
	//char c[20]="abd**e**cf***";
	char c[20]="abd**e**cf***";
	cout<<"树的前序向量："<<c<<endl;
	for (int i = 0; i < strlen(c); i++)
	{
		a.push_back(c[i]);
	}
	InBiThrTree <char> A(a);
	A.setPre();//置空
	A.InThreaded();
	cout<<"中序遍历打印：";
	A.Travese();	//	
	cout<<endl;
	for (i=0;i<result.length();i++)
	{
		cout<<endl;
		char c=result.at(i);
		
		
		cout<<"查找的值"<<c<<"所在节点并输出地址:";
		BiThrNode<char> *tmp = A.Search(c);
		cout<<tmp<<endl;
		
		cout<<tmp->data<<"节点的前驱:";
		if (A.GetPrev(tmp)!=NULL)
		{
			cout<<A.GetPrev(tmp)<<" 值为："<<A.GetPrev(tmp)->data<<endl;
		}
		else
			cout<<NULL<<endl;
		
		cout<<tmp->data<<"节点的后继:";
		if (A.GetNext(tmp)!=NULL)
		{
			cout<<A.GetNext(tmp)<<" 值为："<<A.GetNext(tmp)->data<<endl;
		}
		else
			cout<<NULL<<endl;

		cout<<tmp->data<<"节点的父节点:";
		if (A.GetParent(tmp)!=NULL)
		{
			cout<<A.GetParent(tmp)<<" 值为："<<A.GetParent(tmp)->data<<endl;
		}
		else
			cout<<NULL<<endl;
		cout<<endl;
	}
	
	return 0;
}

这边需要注意一下，在线索化之前，需要把PreNode置空，便于第一个THREAD节点的操作。

测试树是这棵：

测试结果如下：

2015年5月4日晚