中序线索化二叉树及遍历。
函数接口定义：
void InThreading(BiThrTree p);// 以结点P为根的子树中序线索化
void InOrderTraverse_Thr(BiThrTree T);// 中序遍历二叉线索树T的非递归算法，对每个数据元素直接输出
裁判测试程序样例：
#include<iostream>
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);
void InOrderTraverse_Thr(BiThrTree T);
int main()
{
pre->RTag=1;
pre->rchild=NULL;
BiThrTree tree;
CreateBiTree(tree);
InThreading(tree);
InOrderTraverse_Thr(tree);
return 0;
}
/* 请在这里填写答案 */
输入样例:
ABD###CEG###FH##I##
输出样例:
DBAGECHFI
分析：从裁判样例入手
- 先序遍历建树
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 root)/* 对root所指的二叉树进行中序线索化，其中pre始终指向刚访问过的结点，其初值为NULL*/
{
if (root!=NULL)
{
InThreading(root->lchild); /* 线索化左子树 */
if (root->lchild==NULL)/*没有左孩子指向前驱*/
{
root->LTag=1;
root->lchild=pre->rchild; /*置前驱线索 */
/*主函数是对pre->rchild=NULL，赋值为空。第一个结点的前驱为空，此时要把pre->rchild赋给root->lchild，而不是把pre赋给root->lchild*/
}
if (pre!=NULL&&pre->rchild==NULL) /* 置后继线索 */
{
pre->rchild=root;
pre->RTag=1;
}
pre=root;
InThreading(root->rchild); /*线索化右子树*/
}
}
- 找到中序遍历的第一个结点，并不断找后继，此时输出的就是中序遍历
BiThrNode * InNext(BiThrNode *p)
/*在中序线索二叉树中查找p的中序后继结点，并用next指针返回结果*/
{
BiThrNode *Next;
BiThrNode *q;
if (p->RTag==1)
Next=p->rchild; /*直接利用线索*/
else
{
/*在p的右子树中查找"最左下端"结点*/
if(p->rchild!=NULL)
{
for(q=p->rchild; q->LTag==0 ; q=q->lchild);
Next=q;
}
else
Next = NULL;
}
return Next;
}
BiThrNode* TinFirst(BiThrTree root)
{
BiThrNode *q=root;
q=root;
if(q)
while(q->lchild!=NULL)/*找左子树的左子树。。。*/
q=q->lchild;
return q;
}
void InOrderTraverse_Thr(BiThrTree root)
{
BiThrNode *p;
p=TinFirst(root);/*找到第一个结点*/
while(p!=NULL)
{
printf("%c",p->data);
p=InNext(p);
}
}
完整代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
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 root)/* 对root所指的二叉树进行中序线索化，其中pre始终指向刚访问过的结点，其初值为NULL*/
{
if (root!=NULL)
{
InThreading(root->lchild); /* 线索化左子树 */
if (root->lchild==NULL)/*没有左孩子指向前驱*/
{
root->LTag=1;
root->lchild=pre->rchild; /*置前驱线索 */
}
if (pre!=NULL&&pre->rchild==NULL) /* 置后继线索 */
{
pre->rchild=root;
pre->RTag=1;
}
pre=root;
InThreading(root->rchild); /*线索化右子树*/
}
}
BiThrNode * InNext(BiThrNode *p)
/*在中序线索二叉树中查找p的中序后继结点，并用next指针返回结果*/
{
BiThrNode *Next;
BiThrNode *q;
if (p->RTag==1)
Next=p->rchild; /*直接利用线索*/
else
{
/*在p的右子树中查找"最左下端"结点*/
if(p->rchild!=NULL)
{
for(q=p->rchild; q->LTag==0 ; q=q->lchild);
Next=q;
}
else
Next = NULL;
}
return Next;
}
BiThrNode* TinFirst(BiThrTree root)
{
BiThrNode *q=root;
q=root;
if(q)
while(q->lchild!=NULL)/*找左子树的左子树。。。*/
q=q->lchild;
return q;
}
void InOrderTraverse_Thr(BiThrTree root)
{
BiThrNode *p;
p=TinFirst(root);/*找到第一个结点*/
while(p!=NULL)
{
printf("%c",p->data);
p=InNext(p);
}
}
int main()
{
pre->RTag=1;
pre->rchild=NULL;
BiThrTree tree;
CreateBiTree(tree);
InThreading(tree);
InOrderTraverse_Thr(tree);
return 0;
}
若在主函数初始化pre为NULL，则建立中序线索二叉树时
void Inthread(BiTree root)/* 对root所指的二叉树进行中序线索化，其中pre始终指向刚访问过的结点，其初值为NULL*/
{
if (root!=NULL)
{
Inthread(root->LChild); /* 线索化左子树 */
if (root->LChild==NULL)/*没有左孩子指向前驱*/
{
root->Ltag=1;
root->LChild=pre; /*置前驱线索*/
/*第一个结点没有前驱，则直接把pre赋值给root->LChild*/
}
if (pre!=NULL&& pre->RChild==NULL) /* 置后继线索 */
{
pre->RChild=root;
pre->Rtag=1;
}
pre=root;
Inthread(root->RChild); /*线索化右子树*/
}
}
完整代码：
#include <stdio.h>
#include <malloc.h>
#include <conio.h>
typedef char DataType;
typedef struct Node
{
DataType data;
int Ltag;
int Rtag;
struct Node *LChild;
struct Node *RChild;
} BiTNode, *BiTree;
BiTree pre;
void CreateBiTree(BiTree *bt)/*先序遍历建立二叉树*/
{
char ch;
ch = getchar();
if(ch=='#')
*bt=NULL;
else
{
*bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点
(*bt)->data=ch;
(*bt)->Ltag=0;/*相当于初始化*/
(*bt)->Rtag=0;
CreateBiTree(&((*bt)->LChild)); //生成左子树
CreateBiTree(&((*bt)->RChild)); //生成右子树
}
}
void Inthread(BiTree root)/* 对root所指的二叉树进行中序线索化，其中pre始终指向刚访问过的结点，其初值为NULL*/
{
if (root!=NULL)
{
Inthread(root->LChild); /* 线索化左子树 */
if (root->LChild==NULL)/*没有左孩子指向前驱*/
{
root->Ltag=1;
root->LChild=pre; /*置前驱线索 */
}
if (pre!=NULL&& pre->RChild==NULL) /* 置后继线索 */
{
pre->RChild=root;
pre->Rtag=1;
}
pre=root;
Inthread(root->RChild); /*线索化右子树*/
}
}
BiTNode * InNext(BiTNode * p)
/*在中序线索二叉树中查找p的中序后继结点，并用next指针返回结果*/
{
BiTNode *Next;
BiTNode *q;
if (p->Rtag==1)
Next = p->RChild; /*直接利用线索*/
else
{
/*在p的右子树中查找"最左下端"结点*/
if(p->RChild!=NULL)
{
for(q=p->RChild; q->Ltag==0 ; q=q->LChild);
Next=q;
}
else
Next = NULL;
}
return(Next);
}
BiTNode* TinFirst(BiTree root)
{
BiTNode *p;
p = root;
if(p)
while(p->LChild!=NULL)
p=p->LChild;
return p;
}
void TinOrder(BiTree root)
{
BiTNode *p;
p=TinFirst(root);
while(p!=NULL)
{
printf("%c",p->data);
p=InNext(p);
}
}
int main()
{
BiTree T;
BiTree p,q;
CreateBiTree(&T);
pre=NULL;
Inthread(T);
TinOrder(T);
return 0;
}
