http://hi.baidu.com/fire_man/blog/item/32831f0f6a04f8286159f3ab.html
typedef struct BiTPNode
{
TElemType data;
struct BiTPNode *parent,*lchild,*rchild;
}BiTPNode,*BiPTree;
Status InitBiTree(BiPTree *T)
{
*T=NULL;
return OK;
}
void DestroyBiTree(BiPTree *T)
{
if(*T)
{
if((*T)->lchild)
DestroyBiTree(&(*T)->lchild);
if((*T)->rchild)
DestroyBiTree(&(*T)->rchild);
free(*T);
*T=NULL;
}
}
void Create(BiPTree *T)
{
TElemType ch;
#ifdef CHAR
scanf("%c",&ch);
#endif
#ifdef INT
scanf("%d",&ch);
#endif
if(ch==Nil)
*T=NULL;
else
{
*T=(BiPTree)malloc(sizeof(BiTPNode));
if(!*T)
exit(OVERFLOW);
(*T)->data=ch;
Create(&(*T)->lchild);
Create(&(*T)->rchild);
}
}
typedef BiPTree QElemType;
#include"c3-2.h"
#include"bo3-2.c"
Status CreateBiTree(BiPTree *T)
{
LinkQueue q;
QElemType a;
Create(T);
if(*T)
{
(*T)->parent=NULL;
InitQueue(&q);
EnQueue(&q,*T);
while(!QueueEmpty(q))
{
DeQueue(&q,&a);
if(a->lchild)
{
a->lchild->parent=a;
EnQueue(&q,a->lchild);
}
if(a->rchild)
{
a->rchild->parent=a;
EnQueue(&q,a->rchild);
}
}
}
return OK;
}
#define ClearBiTree DestroyBiTree
Status BiTreeEmpty(BiPTree T)
{
if(T)
return FALSE;
else
return TRUE;
}
int BiTreeDepth(BiPTree 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(BiPTree T)
{
if(T)
return T->data;
else
return Nil;
}
TElemType Value(BiPTree p)
{
return p->data;
}
void Assign(BiPTree p,TElemType value)
{
p->data=value;
}
BiPTree Point(BiPTree T,TElemType e)
{
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(&q);
EnQueue(&q,T);
while(!QueueEmpty(q))
{
DeQueue(&q,&a);
if(a->data==e)
return a;
if(a->lchild)
EnQueue(&q,a->lchild);
if(a->rchild)
EnQueue(&q,a->rchild);
}
}
return NULL;
}
TElemType Parent(BiPTree T,TElemType e)
{
BiPTree a;
if(T)
{
a=Point(T,e);
if(a&&a!=T)
return a->parent->data;
}
return Nil;
}
TElemType LeftChild(BiPTree T,TElemType e)
{
BiPTree a;
if(T)
{
a=Point(T,e);
if(a&&a->lchild)
return a->lchild->data;
}
return Nil;
}
TElemType RightChild(BiPTree T,TElemType e)
{
BiPTree a;
if(T)
{
a=Point(T,e);
if(a&&a->rchild)
return a->rchild->data;
}
return Nil;
}
TElemType LeftSibling(BiPTree T,TElemType e)
{
BiPTree a;
if(T)
{
a=Point(T,e);
if(a&&a!=T&&a->parent->lchild&&a->parent->lchild!=a)
return a->parent->lchild->data;
}
return Nil;
}
TElemType RightSibling(BiPTree T,TElemType e)
{
BiPTree a;
if(T)
{
a=Point(T,e);
if(a&&a!=T&&a->parent->rchild&&a->parent->rchild!=a)
return a->parent->rchild->data;
}
return Nil;
}
Status InsertChild(BiPTree p,int LR,BiPTree c)
{
if(p)
{
if(LR==0)
{
c->rchild=p->lchild;
if(c->rchild)
c->rchild->parent=c;
p->lchild=c;
c->parent=p;
}
else
{
c->rchild=p->rchild;
if(c->rchild)
c->rchild->parent=c;
p->rchild=c;
c->parent=p;
}
return OK;
}
return ERROR;
}
Status DeleteChild(BiPTree p,int LR)
{
if(p)
{
if(LR==0)
ClearBiTree(&p->lchild);
else
ClearBiTree(&p->rchild);
return OK;
}
return ERROR;
}
void PreOrderTraverse(BiPTree T,Status(*Visit)(BiPTree))
{
if(T)
{
Visit(T);
PreOrderTraverse(T->lchild,Visit);
PreOrderTraverse(T->rchild,Visit);
}
}
void InOrderTraverse(BiPTree T,Status(*Visit)(BiPTree))
{
if(T)
{
InOrderTraverse(T->lchild,Visit);
Visit(T);
InOrderTraverse(T->rchild,Visit);
}
}
void PostOrderTraverse(BiPTree T,Status(*Visit)(BiPTree))
{
if(T)
{
PostOrderTraverse(T->lchild,Visit);
PostOrderTraverse(T->rchild,Visit);
Visit(T);
}
}
void LevelOrderTraverse(BiPTree T,Status(*Visit)(BiPTree))
{
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(&q);
EnQueue(&q,T);
while(!QueueEmpty(q))
{
DeQueue(&q,&a);
Visit(a);
if(a->lchild!=NULL)
EnQueue(&q,a->lchild);
if(a->rchild!=NULL)
EnQueue(&q,a->rchild);
}
}
}