注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

倚楼听风雨

没有理想的人,永远也不能翱翔与蓝天白云之上~

 
 
 

日志

 
 

二叉树各种基本运算的实现  

2007-11-28 01:12:48|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

#include<stdio.h>
#include<malloc.h>
#define maxsize 100
typedef char elemtype ;
typedef struct node
{
 elemtype data;
 struct node *lchild;
 struct node *rchild;
} BTNode;
void CreateBTNode(BTNode *&b,char *str)
{
 BTNode *St[maxsize],*p=NULL;
 int top=-1,k,j=0;
 char ch;
 b=NULL;
 ch=str[j];
 while(ch!='\0')
 {
  switch(ch)
  {
  case '(':top++;St[top]=p;k=1;
   break;
  case ')':top--;
   break;
  case ',':k=2;
   break;
  default:p=(BTNode*)malloc(sizeof(BTNode));
   p->data=ch;
   p->lchild=p->rchild=NULL;
   if(b==NULL)
    b=p;
   else
   {
    switch(k)
    {
    case 1:St[top]->lchild=p;
     break;
    case 2:St[top]->rchild=p;
     break;
    }
   }
  }
  j++;
  ch=str[j];
 }
}
void DispBTNode(BTNode *b)
{
 if(b!=NULL)
 {
  printf("%c",b->data);
  if(b->lchild!=NULL || b->rchild!=NULL)
  {
   printf("(");
   DispBTNode(b->lchild);
   if(b->rchild!=NULL)
    printf(",");
   DispBTNode(b->rchild);
   printf(")");
  }
 }
}
int Nodes(BTNode *b)
{
 int num1,num2;
 if(b==NULL)
  return 0;
 else if(b->lchild==NULL && b->rchild==NULL)
  return 1;
 else
 {
  num1=Nodes(b->lchild);
  num2=Nodes(b->rchild);
  return(num1+num2+1);
 }
}
int LeafNodes(BTNode *b)
{
 int num1,num2;
 if(b==NULL)
  return 0;
 else if(b->lchild==NULL && b->rchild==NULL)
  return 1;
 else
 {
  num1=LeafNodes(b->lchild);
  num2=LeafNodes(b->rchild);
  return(num1+num2);
 }
}
int BTNodeDepth(BTNode *b)
{
 int lchilddep,rchilddep;
 if(b==NULL)
  return 0;
 else
 {
  lchilddep=BTNodeDepth(b->lchild);
  rchilddep=BTNodeDepth(b->rchild);
  return lchilddep>rchilddep?(lchilddep+1):(rchilddep+1);
 }
}
BTNode *FindNode(BTNode *b,elemtype x)
{
 BTNode *p;
 if(b==NULL)
  return NULL;
 else if(b->data==x)
  return b;
 else
 {
  p=FindNode(b->lchild,x);
  if(p!=NULL)
   return p;
  else return FindNode(b->rchild,x);
 }
}
BTNode *LchildNode(BTNode *p)
{
 return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
 return p->rchild;
}
void main()
{
 BTNode *b,*p,*lp,*rp;
 CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
 printf("(1)输出二叉树:");
 DispBTNode(b);
 printf("\n");
 printf("(2)H节点");
 p=FindNode(b,'H');
 if(p!=NULL)
 {
  lp=LchildNode(p);
  if(lp!=NULL)
   printf("左孩子为%c",lp->data);
  else
   printf("无左孩子");
  rp=RchildNode(p);
  if(rp!=NULL)
   printf("右孩子为%c",rp->data);
  else
   printf("无右孩子");
 }
 printf("\n");
 printf("(3)二叉树b的深度:%d\n",BTNodeDepth(b));
 printf("(4)二叉树b叶子节点个数:%d\n",LeafNodes(b));
 printf("(5)二叉树b节点个数:%d\n",Nodes(b));
}
   

 

  评论这张
 
阅读(437)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017