ツリーのツリーチェーンテーブルストレージ
16004 ワード
/* c6-2.h */
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild; /* */
}BiTNode,*BiTree;
/* bo6-2.c ( c6-2.h ) (22 ) */
Status InitBiTree(BiTree *T)
{ /* : T */
*T=NULL;
return OK;
}
void DestroyBiTree(BiTree *T)
{ /* : T 。 : T */
if(*T) /* */
{
if((*T)->lchild) /* */
DestroyBiTree(&(*T)->lchild); /* */
if((*T)->rchild) /* */
DestroyBiTree(&(*T)->rchild); /* */
free(*T); /* */
*T=NULL; /* 0 */
}
}
void CreateBiTree(BiTree *T)
{ /* 6.4: （ ， */
/* ）， T。 Nil （ ） 。 */
TElemType ch;
#ifdef CHAR
scanf("%c",&ch);
#endif
#ifdef INT
scanf("%d",&ch);
#endif
if(ch==Nil) /* */
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T)
exit(OVERFLOW);
(*T)->data=ch; /* */
CreateBiTree(&(*T)->lchild); /* */
CreateBiTree(&(*T)->rchild); /* */
}
}
Status BiTreeEmpty(BiTree T)
{ /* : T */
/* : T , TRUE, FALSE */
if(T)
return FALSE;
else
return TRUE;
}
#define ClearBiTree DestroyBiTree
int BiTreeDepth(BiTree T)
{ /* : T 。 : T */
int i,j;
if(!T)
return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild);
else
i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild);
else
j=0;
return i>j?i+1:j+1;
}
TElemType Root(BiTree T)
{ /* : T 。 : T */
if(BiTreeEmpty(T))
return Nil;
else
return T->data;
}
TElemType Value(BiTree p)
{ /* : T ，p T */
/* : p */
return p->data;
}
void Assign(BiTree p,TElemType value)
{ /* p value */
p->data=value;
}
typedef BiTree QElemType; /* */
#include"c3-2.h"
#include"bo3-2.c"
TElemType Parent(BiTree T,TElemType e)
{ /* : T ,e T */
/* : e T , , ＂ ＂ */
LinkQueue q;
QElemType a;
if(T) /* */
{
InitQueue(&q); /* */
EnQueue(&q,T); /* */
while(!QueueEmpty(q)) /* */
{
DeQueue(&q,&a); /* , a */
if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e)
/* e( ) */
return a->data; /* e */
else /* e, ( ) */
{
if(a->lchild)
EnQueue(&q,a->lchild);
if(a->rchild)
EnQueue(&q,a->rchild);
}
}
}
return Nil; /* e */
}
BiTree Point(BiTree T,TElemType s)
{ /* T s 。 */
LinkQueue q;
QElemType a;
if(T) /* */
{
InitQueue(&q); /* */
EnQueue(&q,T); /* */
while(!QueueEmpty(q)) /* */
{
DeQueue(&q,&a); /* , a */
if(a->data==s)
return a;
if(a->lchild) /* */
EnQueue(&q,a->lchild); /* */
if(a->rchild) /* */
EnQueue(&q,a->rchild); /* */
}
}
return NULL;
}
TElemType LeftChild(BiTree T,TElemType e)
{ /* : T ,e T */
/* : e 。 e , ＂ ＂ */
BiTree a;
if(T) /* */
{
a=Point(T,e); /* a e */
if(a&&a->lchild) /* T e e */
return a->lchild->data; /* e */
}
return Nil; /* */
}
TElemType RightChild(BiTree T,TElemType e)
{ /* : T ,e T */
/* : e 。 e , ＂ ＂ */
BiTree a;
if(T) /* */
{
a=Point(T,e); /* a e */
if(a&&a->rchild) /* T e e */
return a->rchild->data; /* e */
}
return Nil; /* */
}
TElemType LeftSibling(BiTree T,TElemType e)
{ /* : T ,e T */
/* : e 。 e T , ＂ ＂ */
TElemType a;
BiTree p;
if(T) /* */
{
a=Parent(T,e); /* a e */
p=Point(T,a); /* p a */
if(p->lchild&&p->rchild&&p->rchild->data==e) /* p e */
return p->lchild->data; /* p (e ) */
}
return Nil; /* e */
}
TElemType RightSibling(BiTree T,TElemType e)
{ /* : T ,e T */
/* : e 。 e T , ＂ ＂ */
TElemType a;
BiTree p;
if(T) /* */
{
a=Parent(T,e); /* a e */
p=Point(T,a); /* p a */
if(p->lchild&&p->rchild&&p->lchild->data==e) /* p e */
return p->rchild->data; /* p (e ) */
}
return Nil; /* e */
}
Status InsertChild(BiTree p,int LR,BiTree c) /* T */
{ /* : T ,p T ,LR 0 1, c T */
/* */
/* : LR 0 1, c T p 。p */
/* c */
if(p) /* p */
{
if(LR==0)
{
c->rchild=p->lchild;
p->lchild=c;
}
else /* LR==1 */
{
c->rchild=p->rchild;
p->rchild=c;
}
return OK;
}
return ERROR; /* p */
}
Status DeleteChild(BiTree p,int LR) /* T */
{ /* : T ,p T ,LR 0 1 */
/* : LR 0 1, T p */
if(p) /* p */
{
if(LR==0) /* */
ClearBiTree(&p->lchild);
else /* */
ClearBiTree(&p->rchild);
return OK;
}
return ERROR; /* p */
}
void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* : T ,Visit 。 6.1， */
/* : T, Visit */
if(T) /* T */
{
Visit(T->data); /* */
PreOrderTraverse(T->lchild,Visit); /* */
PreOrderTraverse(T->rchild,Visit); /* */
}
}
void InOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* : T ,Visit */
/* : T, Visit */
if(T)
{
InOrderTraverse(T->lchild,Visit); /* */
Visit(T->data); /* */
InOrderTraverse(T->rchild,Visit); /* */
}
}
typedef BiTree SElemType; /* */
#include"c3-1.h"
#include"bo3-1.c"
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType))
{ /* ，Visit 。 6.3 */
/* T ( )， Visit */
SqStack S;
InitStack(&S);
while(T||!StackEmpty(S))
{
if(T)
{ /* , */
Push(&S,T);
T=T->lchild;
}
else
{ /* , , */
Pop(&S,&T);
if(!Visit(T->data))
return ERROR;
T=T->rchild;
}
}
printf("
");
return OK;
}
Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType))
{ /* ，Visit 。 6.2 */
/* T ( )， Visit */
SqStack S;
BiTree p;
InitStack(&S);
Push(&S,T); /* */
while(!StackEmpty(S))
{
while(GetTop(S,&p)&&p)
Push(&S,p->lchild); /* */
Pop(&S,&p); /* */
if(!StackEmpty(S))
{ /* , */
Pop(&S,&p);
if(!Visit(p->data))
return ERROR;
Push(&S,p->rchild);
}
}
printf("
");
return OK;
}
void PostOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* : T ,Visit */
/* : T, Visit */
if(T) /* T */
{
PostOrderTraverse(T->lchild,Visit); /* */
PostOrderTraverse(T->rchild,Visit); /* */
Visit(T->data); /* */
}
}
void LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* ： T ,Visit */
/* ： T( ), Visit */
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(&q);
EnQueue(&q,T);
while(!QueueEmpty(q))
{
DeQueue(&q,&a);
Visit(a->data);
if(a->lchild!=NULL)
EnQueue(&q,a->lchild);
if(a->rchild!=NULL)
EnQueue(&q,a->rchild);
}
printf("
");
}
}
/* main6-2.c bo6-2.c , ( ) */
#define CHAR /* */
/* #define INT /* （ ） */
#include"c1.h"
#ifdef CHAR
typedef char TElemType;
TElemType Nil=' '; /* */
#endif
#ifdef INT
typedef int TElemType;
TElemType Nil=0; /* 0 */
#endif
#include"c6-2.h"
#include"bo6-2.c"
Status visitT(TElemType e)
{
#ifdef CHAR
printf("%c ",e);
#endif
#ifdef INT
printf("%d ",e);
#endif
return OK;
}
void main()
{
int i;
BiTree T,p,c;
TElemType e1,e2;
InitBiTree(&T);
printf(" , ？%d(1: 0: ) =%d
",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);
if(e1!=Nil)
#ifdef CHAR
printf(" : %c
",e1);
#endif
#ifdef INT
printf(" : %d
",e1);
#endif
else
printf(" ，
");
#ifdef CHAR
printf(" ( :ab a ,b )
");
#endif
#ifdef INT
printf(" ( :1 2 0 0 0 1 ,2 )
");
#endif
CreateBiTree(&T);
printf(" , ？%d(1: 0: ) =%d
",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);
if(e1!=Nil)
#ifdef CHAR
printf(" : %c
",e1);
#endif
#ifdef INT
printf(" : %d
",e1);
#endif
else
printf(" ，
");
printf(" :
");
InOrderTraverse(T,visitT);
printf("
:
");
InOrderTraverse1(T,visitT);
printf(" ( ):
");
InOrderTraverse2(T,visitT);
printf(" :
");
PostOrderTraverse(T,visitT);
printf("
:
");
LevelOrderTraverse(T,visitT);
printf(" : ");
#ifdef CHAR
scanf("%*c%c",&e1);
#endif
#ifdef INT
scanf("%d",&e1);
#endif
p=Point(T,e1); /* p e1 */
#ifdef CHAR
printf(" %c
",Value(p));
#endif
#ifdef INT
printf(" %d
",Value(p));
#endif
printf(" ， : ");
#ifdef CHAR
scanf("%*c%c%*c",&e2);
#endif
#ifdef INT
scanf("%d",&e2);
#endif
Assign(p,e2);
printf(" :
");
LevelOrderTraverse(T,visitT);
e1=Parent(T,e2);
if(e1!=Nil)
#ifdef CHAR
printf("%c %c
",e2,e1);
#endif
#ifdef INT
printf("%d %d
",e2,e1);
#endif
else
#ifdef CHAR
printf("%c
",e2);
#endif
#ifdef INT
printf("%d
",e2);
#endif
e1=LeftChild(T,e2);
if(e1!=Nil)
#ifdef CHAR
printf("%c %c
",e2,e1);
#endif
#ifdef INT
printf("%d %d
",e2,e1);
#endif
else
#ifdef CHAR
printf("%c
",e2);
#endif
#ifdef INT
printf("%d
",e2);
#endif
e1=RightChild(T,e2);
if(e1!=Nil)
#ifdef CHAR
printf("%c %c
",e2,e1);
#endif
#ifdef INT
printf("%d %d
",e2,e1);
#endif
else
#ifdef CHAR
printf("%c
",e2);
#endif
#ifdef INT
printf("%d
",e2);
#endif
e1=LeftSibling(T,e2);
if(e1!=Nil)
#ifdef CHAR
printf("%c %c
",e2,e1);
#endif
#ifdef INT
printf("%d %d
",e2,e1);
#endif
else
#ifdef CHAR
printf("%c
",e2);
#endif
#ifdef INT
printf("%d
",e2);
#endif
e1=RightSibling(T,e2);
if(e1!=Nil)
#ifdef CHAR
printf("%c %c
",e2,e1);
#endif
#ifdef INT
printf("%d %d
",e2,e1);
#endif
else
#ifdef CHAR
printf("%c
",e2);
#endif
#ifdef INT
printf("%d
",e2);
#endif
InitBiTree(&c);
printf(" c:
");
#ifdef CHAR
printf(" ( :ab a ,b )
");
#endif
#ifdef INT
printf(" ( :1 2 0 0 0 1 ,2 )
");
#endif
CreateBiTree(&c);
printf(" c:
");
PreOrderTraverse(c,visitT);
printf("
c T , T c c (0) (1) : ");
#ifdef CHAR
scanf("%*c%c%d",&e1,&i);
#endif
#ifdef INT
scanf("%d%d",&e1,&i);
#endif
p=Point(T,e1); /* p T c */
InsertChild(p,i,c);
printf(" :
");
PreOrderTraverse(T,visitT);
printf("
, (0) (1) : ");
#ifdef CHAR
scanf("%*c%c%d",&e1,&i);
#endif
#ifdef INT
scanf("%d%d",&e1,&i);
#endif
p=Point(T,e1);
DeleteChild(p,i);
printf(" :
");
PreOrderTraverse(T,visitT);
printf("
");
DestroyBiTree(&T);
}