正文

二叉树的相关操作(转载)2006-03-28 10:03:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/ljqy/11499.html

分享到:

二叉树的相关操作,转载http://www.programfan.com/club/showbbs.asp?id=135842

者:lyt8604@sohu.com

#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#define OK 1
#define MAXLEN 100
typedef int ElemType;
typedef struct bnode
{
  ElemType data;
  struct bnode *left,*right;
}bnode,*btree;

int creat(btree &b)//创建二叉树并向树输入结点
{
  void insert(btree &b,bnode *t);
  int x;
  bnode *s;
  b=NULL;
  scanf("%d",&x);
  while(x!=0)
  {
   s=(bnode *)malloc(sizeof(bnode));
   s->data=x;
   s->left=NULL;
   s->right=NULL;
   insert(b,s);
   scanf("%d",&x);
  }//输入结点以0结束
  return OK ;
}

void  insert(btree &b,bnode *s)//向树中插入结点
{
  if(b==NULL) b=s;
  else if(s->data==b->data)
          return;
  else if(s->data<b->data)
          insert(b->left,s);
  else if(s->data>b->data)
          insert(b->right,s);
}

void putout(btree b)//输出此二叉树结构
{
  if(b!=NULL)
  {
   printf("%d",b->data);
   if(b->left!=NULL||b->right!=NULL)
   {
    printf("(");//用广义表的形式输出树的结构
    putout(b->left);
    if(b->right!=NULL) printf(",");
    putout(b->right);
    printf(")");
   }
  }
}

void first(btree &b)//先序遍历
{
  if(b!=NULL)
  {
   printf("%d ",b->data);
   first(b->left);  
   first(b->right);
  }  
}

void middle(btree &b)//中序遍历
{
  if(b!=NULL)
  {   
   middle(b->left);
   printf("%d ",b->data);
   middle(b->right);
  } 
}

void last(btree &b)//后序遍历
{
  if(b!=NULL)
  {   
   last(b->left);  
   last(b->right);
   printf("%d ",b->data);
  } 
}
void midd(btree &b)//中序的非递归算法
{
  btree stack[255],p;
  int top=0; 
  p=b;
  do
  {
   while(p!=NULL)
   { 
    top++; stack[top]=p;
    p=p->left;
   }
   if(top>0)
   {         
    p=stack[top]; top--;
    printf("%d ",p->data);
    p=p->right;
   } 
  }while(p!=NULL||top!=0);
}

void leveltran(btree b)//二叉排序树的层次遍历
{                            
  struct node
  {
   btree vec[MAXLEN];
   int f,r;
  }q;
  q.f=0;
  q.r=0;
  if(b!=NULL) printf("%d ",b->data);
  q.vec[q.r]=b;
  q.r=q.r+1;
  while(q.f<q.r)//模拟队列,用q.r和q.f做标志,当两者相等时即队列为空
  {
   b=q.vec[q.f];
   q.f=q.f+1;
   if(b->left!=NULL)
   {
    printf("%d ",b->left->data);
    q.vec[q.r]=b->left;
    q.r=q.r+1;
   }
   if(b->right!=NULL)
   {
    printf("%d ",b->right->data);
    q.vec[q.r]=b->right;
    q.r=q.r+1;
   }
  }
}

bnode *search(btree q,int t)//查找结点,返回指向该结点的指针
{
  if(q==NULL) 
  {
   printf("找不到你要的结点或树为空\n");
   return(NULL);
  }
  else
  {
   if(q->data==t) return(q);
   if(t<q->data) q=search(q->left,t);
   else q=search(q->right,t);
  } return q;
}

bnode *swap(btree b)//交换左右子树产生新的树t返回到主函数
{
  btree t,t1,t2;
  if(b==NULL)
  t=NULL;
  else
  {
   t=(bnode *)malloc(sizeof(bnode));
   t->data=b->data;
   t1=swap(b->left);
   t2=swap(b->right);
   t->left=t2;
   t->right=t1;
  } return(t);
}

int depth(btree &b)//求树的深度
{
  int dep1,dep2;
  if(b==NULL) return 0;
  else
  {
   dep1=depth(b->left);
   dep2=depth(b->right);
   if(dep1>dep2) return(dep1+1);
   else return(dep2+1);
  } 
}

int leafs(btree b)//求树的叶子结点数
{
  int num1,num2;
  if(b==NULL) return 0;
  else 
      if(b->left==NULL&&b->right==NULL)
      return 1; 
      else  
      {
       num1=leafs(b->left);
       num2=leafs(b->right);
       return (num1+num2);
      }
}
int deletet(btree &b)//删除结点
{                    
  btree s,p,q;
  int x;
  printf("请输入你要删除的结点:\n");
  scanf("%d",&x);
  if((b->data==x)&&(b->left==NULL)&&(b->right==NULL))
  {
   b=NULL;return OK;
  }//只有根结点时并删除的情况
  if(b->data==x&&(b->left!=NULL)&&(b->right==NULL))
  {
   s=b;b=b->left;
   free(s); return OK;
  }//根结点只有左子树时删除根的情况
  if(b->data==x&&(b->left==NULL)&&(b->right!=NULL))
  {
   s=b; b=b->right;
   free(s); return OK;
  }//根结点只有右子树时删除根的情况
  p=b;
  q=NULL;
  while(p!=NULL&&p->data!=x)
  {
   if(x<p->data)
   {
    q=p; p=p->left;
   }
   else
   {
    q=p; p=p->right;
   }
  }//while,q指向要删除结点的前驱,p指向被删除的结点
  if(p==NULL)
  {
   printf("找不到你要删除的结点\n");
   return -1;
  }//if
  if(!p->right)//右子树为空接左子树
  {
   if(q->left==p)//q是p的前驱,看看p是q的左子树还是q右子树
   {
    s=p; q->left=p->left;
    free(s);
   }
   else
   {
    s=p; q->right=p->left;
    free(s);
   } return OK;
  }//if
  if(!p->left)//左子树为空接右子树
  {
   if(q->left==p)//q是p的前驱,看看p是q的左子树还是q右子树
   {
    s=p; q->left=p->right;
    free(s);
   }
   else
   {
    s=p; q->right=p->right;
    free(s);
   } return OK;
  }//if 
  else//左右子树都不为空,此时不是删除p而是用s指向的结点代替
  {
     q=p; s=p->left;
     while(s->right)
     {
      q=s; s=s->right;
     }
     p->data=s->data;
     if(q!=p) q->right=s->left;
     else q->left=s->left;
     free(s); return OK;
  }//else 
}

//主函数
void main()
k{ 
  btree b,t,n;
  int k,x,dep,leaf;
  while(1)
  {
    printf("请输入你要执行的操作:\n");
    printf("0------------------------结束此次操作\n");
    printf("1-----输入结点并建二叉排序树(以0结束)\n");
    printf("2--------------广义表形式输出树的结构\n");
    printf("3----------------------------先序遍历\n");
    printf("4----------------------------中序遍历\n");
    printf("5----------------------------后序遍历\n");
    printf("6----------------------中序非剃归遍历\n");
    printf("7----------------------------层次遍历\n");
    printf("8----------------------查找你要的结点\n");
    printf("9------------------------交换左右子树\n");
    printf("10---------------求此二叉排序树的深度\n");
    printf("11---------求此二叉排序树的叶子结点数\n");
    printf("12---------------------------删除结点\n");
    scanf("%d",&k);
    switch(k)
    {
     case 0:
           system("cls");
           return;       
     case 1:
           system("cls");
           printf("请输入结点(以0结束输入):\n");
           creat(b);
           break;
     case 2:
           system("cls");
           printf("树的结构为:\n");
           putout(b);
           printf("\n");
           break; 
     case 3:
           system("cls");
           printf("先序遍历为:\n");  
           first(b);
           printf("\n");
           break;
     case 4:
           system("cls");
           printf("中序遍历为:\n");  
           middle(b);
           printf("\n");
           break;
     case 5:
         system("cls");
           printf("后序遍历为:\n");  
           last(b);
           printf("\n");
           break;
     case 6:
           system("cls");
           printf("中序非剃归遍历为:\n");
           midd(b);
           printf("\n");
           break;
     case 7:
           system("cls");
           printf("层次遍历为:\n");
           leveltran(b);
           printf("\n");
           break;
     case 8:
           system("cls");
           printf("请输入你要查找的结点:\n");
           scanf("%d",&x);
           t=search(b,x);
           if(t!=NULL)
           printf("你要查找的结点为: %d\n",t->data);
           break;
     case 9:
           system("cls");
           printf("交换左右子树后树的结构为:\n"); 
           n=swap(b);
           putout(n);
           printf("\n");
           break; 
     case 10:
           system("cls");
           printf("树的深度为:\n");
           dep=depth(b);
           printf("%d\n",dep);
           break; 
     case 11:
           system("cls");
           printf("此树的叶子结点数为:\n");
           leaf=leafs(b);
           printf("%d\n",leaf);
           break;
     case 12:
           system("cls");
           deletet(b);
           break;
    }
  }
}

 

 

阅读(2377) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册