depth.c

来自「C程序自动测试程序系统,主要是测试数据结构中的几个经典算法:关于排序,树的遍历等」· C语言 代码 · 共 86 行

/*Function:void search,查找结点*/
/*Function:void creat,建树*/
/*Function:int depth,计算树高*/
/*Function:void r_posorder,后序遍历*/
/*Start*/

#include "Stdio.h"
#include "Conio.h"
#define M 10

typedef struct node{
                     int data;
                     struct node *lchild,*rchild;
                   }NODE;

void search(NODE *t,int a,NODE **p_p,NODE **p_q)
{
  *p_p=NULL;
  *p_q=t;
  while(*p_q!=NULL)
  {
    if((*p_q)->data==a)return;
    *p_p=*p_q;
    if(a<(*p_q)->data)
      *p_q=(*p_q)->lchild;
    else *p_q=(*p_q)->rchild;
  }
}

void creat(NODE **p_t,int a)
{
  NODE *p,*q,*r;
  search(*p_t,a,&p,&q);
  if(q!=NULL)return;
  r=(NODE*)malloc(sizeof(NODE));
  r->data=a;
  r->lchild=r->rchild=NULL;
  if(p==NULL) *p_t=r;
  else if(p->data>a)
     p->lchild=r;
  else
     p->rchild=r;
}

int depth(NODE *t)
{
  int dep1,dep2;
  if(t==NULL)return(-1);
  else
  {
    dep1=depth(t->lchild);
    dep2=depth(t->rchild);
    if(dep1>=dep2) return(dep1+1);
    else return(dep2+1);
  }
}

void r_posorder(NODE *t)
{
  if(t!=NULL)
  {
    r_posorder(t->lchild);
    r_posorder(t->rchild);
    printf("%d ",t->data);
  }
 
}

main()
{
  NODE *tree;
  int i,s[M];
  for(i=0;i<M;i++)
     scanf("%d",&s[i]);
  tree=(NODE*)malloc(sizeof(NODE));
  tree->data=s[0];
  tree->lchild=tree->rchild=NULL;
  for(i=1;i<M;i++)
     creat(&tree,s[i]);
  i=depth(tree);
  r_posorder(tree); printf("\n");
  printf("The depth is:");
  printf("%d",i);
  printf("\n");
}