另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。‘’
打开IDE
我们创建一个工程如下
创建一个二叉树基本类
#if !defined(AFX_TBSTREE_H__734128DD_1E78_4C94_B09C_BB135D79A339__INCLUDED_)#define AFX_TBSTREE_H__734128DD_1E78_4C94_B09C_BB135D79A339__INCLUDED_#if _MSC_VER > 1000#pragma once#endif // _MSC_VER > 1000//线索二叉树结点类型存储结构体TBSTree.htemplateclass 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 THNode *First()=0; virtual void Next()=0; virtual void Last()=0; virtual void Prior()=0; int EndOfNext() {return nextC;} int EndOfPrior() {return priorC;} //数据检索与修改成员函数 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)root=GetTreeNode('X',null);if(num==2){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);}if(num==3){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;}#endif // !defined(AFX_TBSTREE_H__734128DD_1E78_4C94_B09C_BB135D79A339__INCLUDED_)
创建一个二叉线索树派生二叉树
#if !defined(AFX_ITBSTREE_H__8F1F1BC6_2A9C_4B63_9293_7FE5AD325AA7__INCLUDED_)#define AFX_ITBSTREE_H__8F1F1BC6_2A9C_4B63_9293_7FE5AD325AA7__INCLUDED_#if _MSC_VER > 1000#pragma once#endif // _MSC_VER > 1000#include "TBSTree.h"//派生类ITBSTree.htemplateclass ITBSTree:public TBSTree {private: //中序线索化二叉树 void InThread(THNode *&root,THNode *&pre); public: //构造函数 ITBSTree(THNode *&tree):TBSTree (tree) {} //中序线索化二叉树 void CreatInThread(); //定位到中序下的第一个结点 virtual THNode *First(); //将当前指针移到中序下的后继结点 virtual void Next(); //定位到中序下的最后一个结点 virtual void Last(); //将当前指针移到中序下的前驱结点 virtual void Prior(); //插入结点 void InsertR(THNode *&s,THNode *&r);};template void ITBSTree ::InThread(THNode *&root,THNode *&pre){if(root!=NULL) {InThread(root->left,pre);//中序线索化左子树二叉树 if(root->left==NULL)//当前结点左指针为空指针时 {root->lflag=1; //建立左线索指针 root->left=pre;//建立左线索标志 } if(pre->right==NULL)//前驱结点右指针为空指针时 {pre->rflag=1; //建立右线索标志 pre->right=root;//建立右线索指针 } pre=root;//前驱结点右指针等于当前结点指针 InThread(root->right,pre);}//中序线索化右子树二叉树}template void ITBSTree ::CreatInThread(){THNode *t=root;//保存原根结点指针 root=new THNode ;//建立头结点 root->lflag=0; root->rflag=1; if(t==NULL)//当为空树时 {root->left=root; root->right=root; } else //当为非空树时 {curr=root->left=t;//置头结点的左指针 root->lflag=0; //置头结点的左标志 THNode *pre=root;//定义临时指针 InThread(curr,pre);//中序线索化二叉树 pre->right=root;//置最后一个结点的右线索 pre->rflag=1; //置最后一个结点的右标志 root->right=pre;//置头结点的右线索 root->rflag=1;//置头结点的右标志 }}template THNode *ITBSTree ::First(){curr=root;//从根结点开始 while(curr->lflag==0) curr=curr->left; if(curr==root) nextC=1;//当二叉树为空时 else nextC=0;//当二叉树为非空时 return curr;}template void ITBSTree ::Next(){if(nextC==1) {cerr<<"已到二叉树尾!\n";exit(1);} THNode *p=curr->right;//将当前指针移到中序下的后继结点 if(curr->rflag==0) while(p->lflag==0) p=p->left; curr=p; if(curr==root) nextC=1;}template void ITBSTree ::Last(){curr=root->right;//使curr定位到中序下的最后一个结点 if(curr==root) priorC=1; else priorC=0;}template void ITBSTree ::Prior(){if(priorC==1) {cerr<<"已到二叉树头!\n";exit(1);} THNode *p=curr->left; if(curr->lflag==0) while(p->rflag==0) p=p->right; curr=p; if(curr==root) priorC=1;}template void ITBSTree ::InsertR(THNode *&s,THNode *&r){//将r当做s的右子女插入 r->right=s->right;//s的右子女指针或后继线索传给r r->rflag=s->rflag;//传送标志 r->left=s;r->lflag=1;//r的left成为指向s的前驱线索 s->right=r;s->rflag=0;//r成为s的右子女 if(r->rflag==0)//s原来有右子女 {curr=r->right; THNode *temp=First();//在s原来的右子树中找中序下第一个结点 temp->left=r;//建立指向r的前驱线索 }}#endif // !defined(AFX_ITBSTREE_H__8F1F1BC6_2A9C_4B63_9293_7FE5AD325AA7__INCLUDED_)
代码调用如下，
void main(){cout<<"运行结果:\n";THNode *q,*p,*r;q=MakeCharT(q,3);ITBSTree t(q);t.CreatInThread();cout<<"线索二叉树的中序正向遍历序列为:\n";for(t.First();!t.EndOfNext();t.Next())cout< <<" ";cout<<"\n线索二叉树的中序反向遍历序列为:\n";for(t.Last();!t.EndOfPrior();t.Prior())cout< <<" ";p=MakeCharT(p,2);ITBSTree d(p);d.CreatInThread();cout<<"\n线索二叉树的中序正向遍历序列为:\n";for(d.First();!d.EndOfNext();d.Next())cout< <<" ";cout<<"\n线索二叉树的中序反向遍历序列为:\n";for(d.Last();!d.EndOfPrior();d.Prior())cout< <<" ";r=MakeCharT(r,1);ITBSTree h(r);h.CreatInThread();cout<<"\n线索二叉树的中序正向遍历序列为:\n";for(h.First();!h.EndOfNext();h.Next())cout< <<" ";d.InsertR(p,r);cout<<"\n插入结点后线索二叉树的中序正向遍历序列为:\n";for(d.First();!d.EndOfNext();d.Next())cout< <<" ";cin.get();} 效果如下
代码下载如下