Question

建立中序线索二叉树，并且中序遍历； 2. 求中序线索二叉树上已知结点中序的前驱和后继

谢了

Answer 1

在线索二叉树中，结点的结构可以定义为如下形式：
template<class T>
{
T data;//数据域
int lflag;//左标志域
int rflag;//右标志域
BiThrNode<T>*lchild;//左指针域
BiThrNode<T>*rchild;//右指针域
};
建立一棵中序线索二叉树。
建立线索二叉树或者说对二叉树线索化，实质就是遍历一棵二叉树。
template<class T>
void CThrBiTree<T>::In_ThreadBiTree()
{//生成中序线索二叉链表
BiThrNode<T>*p,*q=NULL;
p=BT;
In_Thread(p,&q);
}
template<class T>
void CThrBiTree<T>::In_Thread(BiThrNode<T>*p,BiThrNode<T>**h)
{
if(p)//判断p指向的结点是否空
{
In_Thread(p->lchild,h);//访问左子树
//若上次访问的结点的右指针为空，则将当前访问到的结点指针赋给其右指针，
//并置右标志域为1
if((*h!=NULL)&&((*h)->rchild==NULL))
{
(*h)->rchild=p; //h即是刚被访问过的结点指针，p是当前被访问的结点指针
(*h)->rflag=1;
}
//若当前访问的结点的左指针为空，则将上次访问的指针赋给当前结点的左指针域
//并置右标志域为1
if(p->lchild==NULL)
{
p->lchild=(*h);
p->lflag=1;
}
*h=p; //保存当前被访问的结点指针
In_Thread(p->rchild,h); //访问右子树
}
}
在中序线索二叉树上查找任意结点的中序前驱结点。
步骤一：对于中序线索二叉树上的任一结点，寻找其中序遍历序列中的前驱结点。
步骤二：判断前驱结点左标志值：
2.1 如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点。
2.2 如果该结点的左标志为0，表明该结点有左孩子。沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。
C++语言描述：
BiThrNode<T>*InPreNode(BiThrNode<T>*p)
{ //在中序线索二叉树上寻找结点p的中序前驱结点
BiThrNode<T>*pre;
pre=p->lchild;
if(p->lflag!=1)
while(pre->rflag==0) pre=pre->rchild;
return pre;
}
在中序线索二叉树上查找任意结点的中序后继结点
BiThrNode<T>*InPostNode(BiThrNode<T>*p)
{
BiThrNode<T>*post;
post=p->rchild;
if(p->rflag!=1)
while(post->rflag==0) post=post->lchild;
return post;
}

Answer 2

/*二叉树的二叉线索存储表示*/
typedef enum PointerTag{Link,Thread};//Link==0:指针； Thread==1：线索
typedef struct CTNode{
int data;
struct CTNode *firstchild;
struct CTNode *nextsibling;
PointerTag LTag,RTag;
}CTNode,*CTree;

CTree pre=NULL;

void InThreading(CTree p) /*线索化*/
{
if(p)
{
InThreading(p->firstchild);// 左子树线索化
if(!p->firstchild ) /*前驱线索*/
{
p->LTag =Thread;
p->firstchild =pre;
}
if(!pre->nextsibling ) /*后继线索*/
{
pre->RTag =Thread;
pre->nextsibling =p;
}
pre=p;//保持pre指向p
InThreading(p->nextsibling );//右子树线索化
}
}

CTree InOrderThreading(CTree Thrt,CTree ct)
{//中序遍历二叉树ct，并将其中序线索化，Thrt指向头结点
Thrt=(CTree)malloc(sizeof(CTNode));
if(!Thrt)exit(0);
Thrt->LTag =Link;//建立头结点
Thrt->RTag =Thread;
Thrt->nextsibling =Thrt;//右指针回指
if(!ct)
Thrt->firstchild =Thrt;
else
{
Thrt->firstchild =ct;
pre=Thrt;
InThreading(ct);//中序遍历进行中序遍历线索化
pre->nextsibling =Thrt;//最后一个结点线索化
pre->RTag =Thread;
(Thrt)->nextsibling =pre;
}
return Thrt;
}

int print(int e)
{//输出结点
printf("%3d",e);return 1;
}

/*中序遍历线索化二叉树*/
int InOrderTraverse(CTree ct,int(*visit)(int e))/*中序遍历线索化二叉树*/
{//ct指向头结点，头结点的做指针firstchild指向根结点，中序遍历二叉树
CTree p;
p=ct->firstchild ;//p指向根结点
while(p!=ct)//空树或遍历结束时，p==ct
{
while(p->LTag ==Link)p=p->firstchild ;
if(!visit(p->data )) return 0; //打印
while(p->RTag ==Thread&&p->nextsibling !=ct)
{
p=p->nextsibling ;visit(p->data); //访问后继结点
}
p=p->nextsibling ;
}
return 1;
}

追问

有完整的吗？ 谢了

Answer 3

引用小鬼出来混的回答：
/*二叉树的二叉线索存储表示*/
typedef enum PointerTag{Link,Thread};//Link==0:指针； Thread==1：线索
typedef struct CTNode{
int data;
struct CTNode *firstchild;
struct CTNode *nextsibling;
PointerTag LTag,RTag;
}CTNode,*CTree;

CTree pre=NULL;

void InThreading(CTree p) /*线索化*/
{
if(p)
{
InThreading(p->firstchild);// 左子树线索化
if(!p->firstchild ) /*前驱线索*/
{
p->LTag =Thread;
p->firstchild =pre;
}
if(!pre->nextsibling ) /*后继线索*/
{
pre->RTag =Thread;
pre->nextsibling =p;
}
pre=p;//保持pre指向p
InThreading(p->nextsibling );//右子树线索化
}
}

CTree InOrderThreading(CTree Thrt,CTree ct)
{//中序遍历二叉树ct，并将其中序线索化，Thrt指向头结点
Thrt=(CTree)malloc(sizeof(CTNode));
if(!Thrt)exit(0);
Thrt->LTag =Link;//建立头结点
Thrt->RTag =Thread;
Thrt->nextsibling =Thrt;//右指针回指
if(!ct)
Thrt->firstchild =Thrt;
else
{
Thrt->firstchild =ct;
pre=Thrt;
InThreading(ct);//中序遍历进行中序遍历线索化
pre->nextsibling =Thrt;//最后一个结点线索化
pre->RTag =Thread;
(Thrt)->nextsibling =pre;
}
return Thrt;
}

int print(int e)
{//输出结点
printf("%3d",e);return 1;
}

/*中序遍历线索化二叉树*/
int InOrderTraverse(CTree ct,int(*visit)(int e))/*中序遍历线索化二叉树*/
{//ct指向头结点，头结点的做指针firstchild指向根结点，中序遍历二叉树
CTree p;
p=ct->firstchild ;//p指向根结点
while(p!=ct)//空树或遍历结束时，p==ct
{
while(p->LTag ==Link)p=p->firstchild ;
if(!visit(p->data )) return 0; //打印
while(p->RTag ==Thread&&p->nextsibling !=ct)
{
p=p->nextsibling ;visit(p->data); //访问后继结点
}
p=p->nextsibling ;
}
return 1;
}

能用C#实现吗