Блог

Вот код дерева двоичного поиска

 #include<stdio.h>
#include<conio.h>
#include"malloc.h"

struct node
{
    int data;
    struct node* left;
    struct node* right;
};
int size(struct node* n)
{
    if(n==NULL)
       return 0;
    else
       return (size(n->left) 1 size(n->right));
}

int maxdepth(struct node* n)
{
    int ldepth,rdepth;
    if(n==NULL)
    {
       return 0;
    }
    else
    {
       ldepth=maxdepth(n->left);
       rdepth=maxdepth(n->right);
       if(ldepth>rdepth)
          return (ldepth 1);
       else
          return (rdepth 1);
    }
}

int lookup(struct node* node,int target)
{
    if(node==NULL)
       return 0;
    else if(target==node->data)
       return 1;
    else if(target<node->data)
       return(lookup(node->left,target));
    else
       return(lookup(node->right,target));
}

struct node* newnode(int data)
{
     struct node* newnod=(struct node*)malloc(sizeof(struct node));
     newnod->data=data;
     newnod->left=NULL;
     newnod->right=NULL;
     return newnod;
}

struct node* insert(struct node* root,int target)
{
    if(root==NULL)
        return(newnode(target));
    else if(target<=root->data)
        root->left=insert(root->left,target);
    else 
        root->right=insert(root->right,target);
    return root;
}

void main()
{
    int result,s,max;
    struct node* newnode=NULL;
    clrscr();
    newnode=insert(newnode,2);
    newnode=insert(newnode,3);
    newnode=insert(newnode,4);
    max=maxdepth(newnode);
    printf("maxdepth %dn",max);
    s=size(newnode);
    result=lookup(newnode,3);
    printf("size %dn",s);
    printf("%d",result);
    getch();
}
  

Когда я запускаю эту программу. Я получаю maxdepth значение 3.

Если я изменю maxdepth функцию как

 int maxdepth(struct node* n)
{
    int ldepth,rdepth;
    if(n==NULL)
    {
        return 0;
    }
    else
    {
        ldepth=maxdepth(n->left);
        rdepth=maxdepth(n->right);
        if(ldepth>rdepth)
            return (ldepth);
        else
            return (rdepth);
    }
}
  

Я получаю maxdepth значение как 0. в чем проблема? Я не мог этого не понять?

Вы не учитываете текущий узел, поэтому 1 необходим.

       {
        ldepth = maxdepth(n->left);
        rdepth = maxdepth(n->right);

        if(ldepth > rdepth)
          return ldepth   1;
        else
          return rdepth   1;
      }
  

Без 1 maxdepth всегда будет возвращаться 0 . Потому что ldepth и rdepth всегда будет 0 .

Пример дерева с 3 узлами:

    A
 /   
B     C
  

Теперь вы вызываете maxdepth(A) , это будет делать: ldepth = maxdepth(B); rdepth = maxdepth(C); , затем maxDepth(B) будет делать: ldepth = maxdepth(null); rdepth = maxdepth(null); /* ldepth and rdepth are now 0 */ , поэтому maxDepth(B) в результате вернется 0 . maxDepth(C) Вернется 0 аналогичное. Затем вы сделаете:

 if(ldepth > rdepth)
  return ldepth;
else
  return rdepth;
  

Но оба ldepth и rdepth являются 0 , поэтому rdepth будет возвращено, что является 0 . В конечном итоге maxdepth(A) в результате будет возвращено 0.

Вот почему 1 это необходимо.

Давайте посмотрим на пример дерева:

     __A__
   /     
  B       C
 /      / 
D   E   F   G
  

В этом дереве мы идеально сбалансированы, поэтому не будем беспокоиться о том, какое поддерево выше в каждом узле (они одинаковой высоты). Итак, мы просто рассчитаем высоту, используя левые ветви.

Какова высота дерева? Это высота A .

Какова высота A ? Это единица плюс высота B .

В свою очередь, высота B равна единице плюс высота D , а высота D D равна единице плюс высота левой ветви, которая равна нулю.

Таким образом, общая высота равна 1 1 1 0 = 3 .

Таким образом, алгоритм в этом (упрощенном) случае является:

 def height (node):
    if node is null:
        return 0
    return 1   height (node.left)
  

И вот почему ваша рекурсивная функция высоты должна добавлять по одному на каждом уровне. Если вместо этого вы добавите 0 (что и делает ваш второй сегмент кода), вы переключитесь с получения 1 1 1 0 = 3 на получение 0 0 0 0 = 0 .

Если вы измените приведенный выше алгоритм, чтобы учесть различные размеры поддеревьев, вы в основном получите свой первый сегмент кода, который работает нормально:

 def height (node):
    if node is null:
        return 0
    leftheight = height (node.left)
    rightheight = height (node.rigth)
    return 1   max (leftheight, rightheight)