二叉树的应用举例实验报告(燕山大学)(7)

#define OVERFLOW -1

typedef char TElemType ;

typedef int Status ;

typedef enum { Link, Thread } PointerThr; //Link==0指针, Thread ==1线索 typedef struct BiThrNode {

TElemType data;

BiThrNode *lchild, *rchild; //左右指针

PointerThr LTag, RTag; //左右标志

} BiThrNode, *BiThrTree;

Status InitBiThrTree(BiThrTree &T)

{ if (!(T=new BiThrNode)) return ERROR;

T->lchild=NULL; T->rchild=NULL;

T->LTag=Link;

T->RTag=Link;

return OK;

}

void CreateBiThrTree(BiThrTree &T)

{ TElemType e;

cin>>e;

T->data=e;

if(e!='#'){

InitBiThrTree(T->lchild);

InitBiThrTree(T->rchild);

CreateBiThrTree(T->lchild);

CreateBiThrTree(T->rchild);

}

}

void InThreading(BiThrTree &pre, BiThrTree &p) {

if(p->data!='#'){

InThreading(pre,p->lchild);

if (p->lchild->data=='#'){

p->LTag=Thread;

p->lchild = pre;

}

if (pre->rchild->data=='#'){

pre ->RTag=Thread;