3bitree.c

一个二叉树的三叉链表运用实例

#define NULL 0
#define OVERFLOW -2
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#include <stdlib.h>


/*栈的结构*/
typedef struct STNode{
int data;
struct STNode *next;
}STNode,*StackPtr;
typedef struct LinkStack{
StackPtr top,base;
}*LinkStack,STRstack;
/*树的结构*/
typedef struct BiTPNode{
int data;
struct BiTPNode *lchild,*rchild,*parent;
}BiTPNode,*BiPTree;
/*队列的结构－其中的元素用来储存树结点的指针*/
typedef struct QNode{
BiPTree data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct LinkQueue{
QueuePtr front,rear;
}*LinkQueue,STRqueue;
/*定义全局变量LinkQueue,LinkStack*/
LinkQueue Q1,Q2;
STRqueue STRQ1,STRQ2;
STRstack STRS;
/*Q1是在Findleaf()生成，用于存储叶子结点的地址*/
/*Q2是在FindPTNode()生成，用于存储底层叶子的队列*/


/*　　　　　　　　　　　　　　　　　　　　　　　　　　　栈的操作定义　*/
InitStack(LinkStack S)
{

 S->top=(StackPtr)malloc(sizeof(STNode));

 S->base= S->top;

}

StackEmpty(LinkStack S)
{
 if(S->top==S->base)
 return TRUE;
 else return FALSE;
 }

int Pop(LinkStack S,int *e)
{
 StackPtr p=NULL;
 if(StackEmpty(S))
   {return ERROR;}
 else if (S->top->next==S->base)
    {
      (*e)=S->base->data;
      free(S->base);
      S->base=S->top;
      }
 else 
     { 
       p=S->top->next->next;
       (*e)=S->top->next->data;
       free(S->top->next);
       S->top->next=p;
      }
}

int Push(LinkStack S,int e)
{
 
 StackPtr p;
 p=(StackPtr)malloc(sizeof(STNode));
 p->data=e;
 if(S->top==S->base)
   S->base=p;
 p->next=S->top->next;
 S->top->next=p;
}


/*　　　　　　　　　　　　　　　　　　　　　　　　　　队列的操作定义*/
InitQueue(LinkQueue Q)
{
 
 Q->front=NULL;
 Q->rear=NULL;
}

QueueEmpty(LinkQueue Q)
{
 if(Q->front==NULL && Q->rear==NULL)
  return TRUE;
  else return FALSE;
}

EnQueue(LinkQueue Q,BiPTree T)
{
 QueuePtr p;
 p=(QueuePtr)malloc(sizeof(QNode));
 p->data=T;
 p->next=NULL;
 if(Q->front==NULL)
 {
  Q->front=p;
  Q->rear=p;
  }
 else
 {
  Q->rear->next=p;
  Q->rear=p;
 }
}

DeQueue(LinkQueue Q,BiPTree *T)
{
 QueuePtr p;
 if(QueueEmpty(Q))
   return ERROR;
 else if(Q->front==Q->rear)
    { 
      (*T)=Q->front->data;
      free(Q->front);
      Q->front=NULL;
      Q->rear=NULL;
     }
  else
      {
       (*T)=Q->front->data;
       p=Q->front->next;
       free(Q->front);
       Q->front=p;
      }
}

/*　　　　　　　　　　　　　　　　　　　　　　　　　　　　树的操作定义*/
InitBiPTree(BiPTree *T)
{
 (*T)=NULL;/*置 [ main()中的T值 ] 为NULL*/
}

 int Treehigh(BiPTree T)
{
 int lh,rh,h;
 if(T==NULL)
    h=0;
 else
    {
      lh=Treehigh(T->lchild);
      rh=Treehigh(T->rchild);
      h=(lh>rh ? lh:rh)+1;
      }
  return h;
}


void Create(BiPTree *T)
{
/*CreateBiPTree()中传递过来的是 [ main()中的T值,即NULL ]*/

 int ch;
 scanf("%d",&ch);
 if(ch==0)
 { (*T)=NULL;
  printf("%o@@@\n",*T);}
 else 
  {
   (*T)=(BiPTree)malloc(sizeof(BiTPNode));
 /*　[ main()中的T获得了新值 ]　*/
   if(!(*T))    
   exit(OVERFLOW);
   (*T)->data=ch;
 /* 在新分配的空间中置值，初始化*/
   printf("%d@@\n",ch);
   Create(&(*T)->lchild);
   Create(&(*T)->rchild);
  }
}

CreateBiPTree(BiPTree *MT)
{
/*main()中传递过来的是T的地址*/
 BiPTree *T;/*二重指针，方便使用，不方便阅读*/
 BiPTree a;
 LinkQueue Q=NULL; 
 /*定义了一个队列指针*/
 T=MT;
/*保存main()中传递过来的T的地址
(*T)则表示指向根结点的指针*/
 Create(MT);
 /* 传递main()中的T的地址给Creat(),构造二叉树　*/
 if((*T))/*此(*T)为 [ main()中的T的值，即根结点的地址 ] */
 {
  (*T)->parent=NULL;/*根结点没有父结点，置NULL*/
  InitQueue(Q);
  printf("%d",(*T)->data);
  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);
        }
    }
  }
}

void Findleaf(BiPTree T)
{
/*从main()中传递过来的是T的值，即根结点的地址。*/

  if(T!=NULL)
  {
    if (T->lchild==NULL && T->rchild==NULL)
        {
          EnQueue(Q1,T);/*叶子结点入队，此T为叶子的地址*/
	  	  }
   Findleaf(T->lchild);
   Findleaf(T->rchild);
  }
}

FindPTNode(int high)
{
 BiPTree p,a;
 int h;
 InitQueue(Q2);
 while(!QueueEmpty(Q1))
 {
  
  DeQueue(Q1,&a);
  p=a;
  h=0;/*自身所在一层*/
  while(p->parent!=NULL)
    { 
      p=p->parent;
      h++;
      }
  h++;/*再加上根结点上的那一层*/
  if(h==high)/*判断是否为底层叶子结点，是的话，入队Q*/
    EnQueue(Q2,a);
  }
}
    

PathOut()
{
 LinkStack S;
 BiPTree a;
 int b,i=1;
 S=&STRS;
 InitStack(S);
 while (!QueueEmpty(Q2))
  {
   DeQueue(Q2,&a);
   Push(S,a->data);
   while(a->parent!=NULL)
   {
    a=a->parent;
    Push(S,a->data);
   }
   printf("\nthe %dth path is ",i);
   while(!StackEmpty(S))
   {
    Pop(S,&b);
    printf("%5d",b);
   }
   i++;
  }
}

/*                                                        主函数main()*/
main()
{
 int high;
 BiPTree T,a;
 InitBiPTree(&T);
/*传递T的地址，以方便跟踪*/
 CreateBiPTree(&T);
/*T指向的地址传递过去后，将在CreateBiTree()中使T指向
新的地址*/ 
 high=Treehigh(T);
 printf("\nthe tree high is:%d",high);
/*传递的是T在CreateBiTree()中产生的新值*/
 Q1=&STRQ1;
 InitQueue(Q1);
 Findleaf(T);
/*找到叶子结点，并将它们存储在Q1中*/
 Q2=&STRQ2;
 FindPTNode(high);
 /*通过Q1找到底层的叶子结点，并将它们存储在Q2中*/
 PathOut();
}