程序填空题：线索二叉树
线索二叉树中序线索化及遍历。
```c++
#include
using namespace std;
typedef struct BiThrNode
{
char data;
struct BiThrNode *lchild,*rchild;
int LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrNode *pre=new BiThrNode;
void CreateBiTree(BiThrTree &T)
{
char ch;
cin >> ch;
if(ch=='#') T=NULL;
else
{
T=new BiThrNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void InThreading(BiThrTree p)
{
if(p)
{
InThreading(p->lchild);
if(!p->lchild)
{
@@[p->LTag=1](2);
@@[p->lchild=pre](2);
}
else
p->LTag=0;
if(!pre->rchild)
{
@@[pre->RTag=1](2);
@@[pre->rchild=p](2);
}
else
pre->RTag=0;
@@[pre=p](2);
InThreading(p->rchild);
}
}
void InOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p;
p=T;
while(p)
{
while(p->LTag==0)
@@[p=p->lchild](2);
cout<data;
while(p->RTag==1)
{
@@[p=p->rchild](2);
cout<data;
}
@@[p=p->rchild](2);
}
}
int main()
{
pre->RTag=1;
pre->rchild=NULL;
BiThrTree tree;
CreateBiTree(tree);
InThreading(tree);
InOrderTraverse_Thr(tree);
return 0;
}
```
答案：
第1空：p->LTag=1
第2空：p->lchild=pre
第3空：pre->RTag=1
第4空：pre->rchild=p
第5空：pre=p
第6空：p=p->lchild
第7空：p=p->rchild
第8空：p=p->rchild
```c++
#include
using namespace std;
typedef struct BiThrNode
{
char data;
struct BiThrNode *lchild,*rchild;
int LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrNode *pre=new BiThrNode;
void CreateBiTree(BiThrTree &T)
{
char ch;
cin >> ch;
if(ch=='#') T=NULL;
else
{
T=new BiThrNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void InThreading(BiThrTree p)
{
if(p)
{
InThreading(p->lchild);
if(!p->lchild)
{
@@[p->LTag=1](2);
@@[p->lchild=pre](2);
}
else
p->LTag=0;
if(!pre->rchild)
{
@@[pre->RTag=1](2);
@@[pre->rchild=p](2);
}
else
pre->RTag=0;
@@[pre=p](2);
InThreading(p->rchild);
}
}
void InOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p;
p=T;
while(p)
{
while(p->LTag==0)
@@[p=p->lchild](2);
cout<
while(p->RTag==1)
{
@@[p=p->rchild](2);
cout<
}
@@[p=p->rchild](2);
}
}
int main()
{
pre->RTag=1;
pre->rchild=NULL;
BiThrTree tree;
CreateBiTree(tree);
InThreading(tree);
InOrderTraverse_Thr(tree);
return 0;
}
```
答案：
第1空：p->LTag=1
第2空：p->lchild=pre
第3空：pre->RTag=1
第4空：pre->rchild=p
第5空：pre=p
第6空：p=p->lchild
第7空：p=p->rchild
第8空：p=p->rchild
