c - 如何查找 B 树的层数

Question

Possible Duplicate:
Segmentation fault in btree implementation

在下面的代码中我们如何找到 B 树的层数

#include<stdio.h>
#include<stdlib.h>
#define M 10
struct node
  {
 int n; /* n < M No. of keys in node will always less than order of Btree */
 int keys[M-1]; /*array of keys*/
 struct node *p[M]; /* (n+1 pointers will be in use) */
   }*root=NULL;

  enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys };
  void insert(int key);
  void display(struct node *root,int);
  enum KeyStatus ins(struct node *r, int x, int* y, struct node** u);
  int searchPos(int x,int *key_arr, int n);

  int main()
  {
  int key;
  int choice;
  int  i,j,mul,count=0;
  int mul_count[65026]={0},value[7097];
  for(i=1;i<=255;i++)
    {
            for(j=1;j<=255;j++)
            {
            mul = j*i;
            mul_count[mul]++;
            }
    }

      for(i=1;i<=65026;i++)
      {
      if( mul_count[i]!= 0 && mul_count[i]!= 2)
            {
            value[count]=i;
                    count++;
            }
      }
         printf("Creation of B tree for node %d\n", M);
        while(1)
    {
       printf("1.Insert\n");
       printf("2.Display\n");
         printf("3.Quit\n");
      printf("Enter your choice : ");
      scanf("%d",&choice);
      switch(choice)
     {
       case 1:
       printf("Inserting is done automatically press 2: \n");
       //scanf("%d",&key);
       for(i=0;i<count;i++)
        {
      key = value[i];
       insert(key);
      }
    break;



        case 2:
            printf("Btree is :\n");
        display(root,0);
       break;

         ase 3:
         exit(1);

               default:
           printf("Wrong choice\n");
         break;

          }/*End of switch*/

         }/*End of while*/
         return 0;
           }/*End of main()*/



    void insert(int key)
    {
     struct node *newnode;
    int upKey;
     enum KeyStatus value;
     value = ins(root, key, &upKey, &newnode);
      if (value == Duplicate)
      printf("Key already available\n");
      if (value == InsertIt)
     {
      struct node *uproot = root;
        root=malloc(sizeof(struct node));
    root->n = 1;
   root->keys[0] = upKey;
   root->p[0] = uproot;
  root->p[1] = newnode;
  }/*End of if */
    }/*End of insert()*/


     enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node **newnode)
     {
      struct node *newPtr, *lastPtr;
      int pos, i, n,splitPos;
      int newKey, lastKey;
      enum KeyStatus value;
     if (ptr == NULL)
      {
     *newnode = NULL;
    *upKey = key;
    return InsertIt;
    }
    n = ptr->n;
    pos = searchPos(key, ptr->keys, n);
    if (pos < n && key == ptr->keys[pos]) 
   return Duplicate;
    value = ins(ptr->p[pos], key, &newKey, &newPtr);
   if (value != InsertIt)
    return value;
    /*If keys in node is less than M-1 where M is order of B tree*/

     if (n < M - 1)
     {
   pos = searchPos(newKey, ptr->keys, n);
    /*Shifting the key and pointer right for inserting the new key*/
   for (i=n; i>pos; i--)
     {
    ptr->keys[i] = ptr->keys[i-1];
    ptr->p[i+1] = ptr->p[i];
    }
   /*Key is inserted at exact location*/
   ptr->keys[pos] = newKey;
   ptr->p[pos+1] = newPtr;
     ++ptr->n; /*incrementing the number of keys in node*/
   return Success;
   }/*End of if */
     /*If keys in nodes are maximum and position of node to be inserted is last*/
    if (pos == M - 1)
     {
     lastKey = newKey;
     lastPtr = newPtr;
     }

    else /*If keys in node are maximum and position of node to be inserted is not    last*/
    {
    lastKey = ptr->keys[M-2];
     lastPtr = ptr->p[M-1];
     for (i=M-2; i>pos; i--)
       {
     ptr->keys[i] = ptr->keys[i-1];
       ptr->p[i+1] = ptr->p[i];
      }

    ptr->keys[pos] = newKey;
      ptr->p[pos+1] = newPtr; 
    }
     splitPos = (M - 1)/2;
    (*upKey) = ptr->keys[splitPos];
    (*newnode)=malloc(sizeof(struct node));/*Right node after split*/
     ptr->n = splitPos; /*No. of keys for left splitted node*/ 
     (*newnode)->n = M-1-splitPos;/*No. of keys for right splitted node*/
     for (i=0; i < (*newnode)->n; i++)
          {
       (*newnode)->p[i] = ptr->p[i + splitPos + 1];
         if(i < (*newnode)->n - 1)
      (*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
        else
       (*newnode)->keys[i] = lastKey;
       }
    (*newnode)->p[(*newnode)->n] = lastPtr;
     return InsertIt;
     }/*End of ins()*/



    void display(struct node *ptr, int blanks)
     {
    int check = 0;
     if (ptr)
      {
     int i;
     for(i=1;i<=blanks;i++)
      printf(" ");
     for (i=0; i < ptr->n; i++)
     {
    //check++;
    printf("%d ",ptr->keys[i]);
      }
     printf("\n");
    for (i=0; i <= ptr->n; i++)
    display(ptr->p[i], blanks+10);
      }/*End of if*/

     //printf("\n no of levels:%d",check);

   }/*End of display()*/




       int searchPos(int key, int *key_arr, int n)
           {
       int pos=0;
      while (pos < n && key > key_arr[pos])
     pos++;
      return pos;
        }/*End of searchPos()*/

Answer 1

这有点像您的 display 函数:

int max(int a, int b)
{
   return a > b ? a : b;
}

int depth(struct node *ptr)
{
   int d=0;
   if (ptr==NULL)
      return d;
   for (i=0; i <= ptr->n; i++)
      d=max(d,depth(ptr->p[i]))
   return d+1;
}