二叉树的相关操作,转载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 100typedef 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;    }  }}    

评论