二叉树

梦里伊人 posted @ 2007年7月30日 06:46 in c语言笔记 with tags c , 1667 阅读

下面写的是有关二叉树的一些算法（二叉树的建立、遍历、深度的计算、输出叶结点、删除想要删除的叶结点）： 

  1. #include<malloc.h>
  2. #include<stdio.h>
  3. #define max 20
  4.  
  5. typedef struct BiTree
  6. {
  7.     struct BiTree *l;
  8.     double value;
  9. }*node,Node;
  10.  
  11. typedef struct stud
  12. {
  13.         int a[max];
  14. }stud;
  15.  
  16. node insert(double key,node root)
  17. {
  18.     node p,f;
  19.     p=root;
  20.     while(p!=NULL)
  21.         {
  22.                 if(key<p->value)
  23.         {
  24.             f=p;
  25.             p=p->l;
  26.         }
  27.         else
  28.             if(key>p->value)
  29.                 {
  30.                     f=p;
  31.                     p=p->r;
  32.                 }
  33.             else
  34.             {
  35.                                 printf("The number has been input,please input another.\n");
  36.                        break;
  37.             }
  38.         }
  39.         if(p==NULL)
  40.         return (f);
  41.         else
  42.                 return NULL;
  43. }
  44.  
  45. node creadBiTree()
  46. {
  47.       int n;
  48.       node root,f,p;
  49.       double m,data;
  50.       printf("Please input one number:");
  51.       scanf("%lf",&data);
  52.       root=malloc(sizeof(Node));
  53.        if(data==0)
  54.               root=NULL;
  55.        else
  56.         {
  57.               root->value=data;
  58.               root->l=root->r=NULL;
  59.               printf("Please input one number:");
  60.               scanf("%lf",&data);
  61.               while(data!=0)
  62.               {
  63.                     f=insert(data,root);
  64.                     p=malloc(sizeof(Node));
  65.                     p->value=data;
  66.                     p->l=p->r=NULL;
  67.                     if(f!=NULL)
  68.                   ｛
  69.                          if(data<f->value)
  70.                          {
  71.                               f->l=p;
  72.                               f=p->parents;
  73.                         }
  74.                         else
  75.                         {
  76.                               f->r=p;
  77.                               f=p->parents;
  78.                         }
  79.                     }
  80.                     printf("Please input one number:");
  81.                     scanf("%lf",&data);
  82.                }
  83.          }
  84.     return (root);
  85. }
  86.  
  87. int depth(node root)
  88. {
  89.         int ld,rd;
  90.         if(root==NULL)
  91.         return 0;
  92.         else
  93.         {
  94.                 ld=depth(root->l);
  95.                 rd=depth(root->r);
  96.         }
  97.         if(ld>rd)
  98.             return ld+1;
  99.         else
  100.             return rd+1;
  101. }
  102.  
  103. node search(node root,double k)
  104. {
  105.     node p;
  106.     p=root;
  107.     while(p!=NULL)
  108.     if(p->value==k) 
  109.           return(p);
  110.     else 
  111.           if(k<p->value) 
  112.                 p=p->l;
  113.          else
  114.                 p=p->r;
  115.     return (NULL);
  116. }
  117.  
  118. int PreOrderTraverse(node T)
  119. {
  120.     if(T!=NULL)
  121.     {
  122.           printf("%lf",T->value);
  123.           printf("\n");
  124.           PreOrderTraverse(T->l);
  125.           PreOrderTraverse(T->r);
  126.     }
  127.     else
  128.           return 1;
  129. }
  130.  
  131. int leaf(node T)
  132. { 
  133.     if(T)
  134.     {
  135.         if((T->l==NULL)&&(T->r==NULL))
  136.             return 1;
  137.         else
  138.             return leaf(T->l)+leaf(T->r);
  139.     }
  140.     else
  141.         return 0;
  142. } 
  143.  
  144. //用了好大工夫才编出的一段程序：
  145. void PostOrder(node T,int *i,stud *s)
  146. {
  147.         if(T!=NULL)
  148.         {
  149.            if((T->l==NULL)&&(T->r==NULL))
  150.                 {
  151.                       s->a[*i]=T->value;
  152.                       (*i)++;
  153.                       return ;          
  154.                 }       
  155.             PostOrder(T->l,i,s);
  156.             PostOrder(T->r,i,s);
  157.         }
  158.         else
  159.                 return ;
  160. }
  161. //程序结束
  162.  
  163. void PreOrder(node T,double h)
  164. {
  165.    if(T!=NULL)
  166.     {
  167.             if (T->value!=h)
  168.             {
  169.                     printf("%lf\n",T->value);
  170.                     PreOrder(T->l,h);
  171.                     PreOrder(T->r,h);
  172.             }
  173.             else
  174.             {
  175.                    free(T);
  176.                    T=NULL;
  177.             }
  178.     }
  179.     else
  180.             return;
  181. }
  182.  
  183. main()
  184. {
  185.       int m,n,k,t,i=0,j=0;
  186.       node root,T;
  187.       double a;
  188.       stud s;
  189.       root=creadBiTree();
  190.       printf("\nPreordertraverse the tree:\n");
  191.       PreOrderTraverse(root);
  192.       m=depth(root);
  193.       printf("\nThe depth of the tree is:%d\n",m);
  194.       n=leaf(root);
  195.       printf("\nThe sum of the leaf root are:%d\n",n);
  196.       while(t!=0)
  197.       {
  198.             printf("\n查询二叉树中是否存在：");
  199.             scanf("%lf",&a);
  200.             T=search(root,a);
  201.             if(T!=NULL)
  202.                     printf("二叉树中存在该结点。\n");
  203.             else
  204.                     printf("二叉树中不存在该结点。\n");
  205.             printf("输入1继续查询,输入0停止查询。请输入：");
  206.             scanf("%d",&t);
  207.     }
  208.         PostOrder(root,&i,&s);
  209.         printf("该二叉树的叶结点为：\n");
  210.         for (j=0;j<i;j++)
  211.               printf("%d\t",s.a[j]);
  212.         printf("\n");
  213.         printf("要删除第k个叶结点:k=");
  214.         scanf("%d",&k);
  215.         while(k>=1&&k<=n)
  216.         {
  217.                 printf("删除第k个结点后，先序遍历该二叉树：\n");
  218.                 PreOrder(root,s.a[k-1]);
  219.                 printf("\n");
  220.                 printf("要删除第k个叶结点:k=");
  221.                 scanf("%d",&k)
  222.             }
          printf("该二叉树不存在这个叶结点
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter



Host by is-Programmer.com | Power by Chito 1.3.3 beta | Designed by Wink Hosting.