int max(int a, int b)
{
if(a>b)
return a;
else
return b;
}
int l_tree(TREE *s, int depth)// Функция измерения макс глубины дерева
{
if(s->data==error)
{
printf("Tree is empty.\n");
system("pause");
}
else
{
if(s==NULL)
return depth;
else
return max(l_tree(s->left,depth+1),l_tree(s->right,depth+1));
}
}
измерение глубины бинарного дерева
долго бьюсь над задачей - вычислить максимальную глубину данного бинарного дерева, но идеи алгоритмов возникают вообще нереализуемые, подскажите будьте добры как мне это сделать:\ ?
всёже родил один алгоритм, но не могу найти ошибки в коде, вот функции:
всёже родил один алгоритм, но не могу найти ошибки в коде, вот функции:
Код:
проще всего рекурсивно
рекурсивно обрабатываем левую правую ветку
возвращаем наибольшее из этих чисел +1
нерекурсивный выход - отсутствие поддерева
можно и через стек - но по сути тоже самое
рекурсивно обрабатываем левую правую ветку
возвращаем наибольшее из этих чисел +1
нерекурсивный выход - отсутствие поддерева
можно и через стек - но по сути тоже самое
Цитата: nilbog
проще всего рекурсивно
рекурсивно обрабатываем левую правую ветку
возвращаем наибольшее из этих чисел +1
нерекурсивный выход - отсутствие поддерева
можно и через стек - но по сути тоже самое
рекурсивно обрабатываем левую правую ветку
возвращаем наибольшее из этих чисел +1
нерекурсивный выход - отсутствие поддерева
можно и через стек - но по сути тоже самое
Код:
int max(int a, int b)
{
if(a>b)
return a;
else
return b;
}
int l_tree(TREE *s, int depth)// Функция измерения макс глубины дерева
{
if(s->data==error)
{
printf("Tree is empty.\n");
system("pause");
}
else
{
if(s==NULL)
return depth;
else
return max(l_tree(s->left,depth+1),l_tree(s->right,depth+1));
}
}
{
if(a>b)
return a;
else
return b;
}
int l_tree(TREE *s, int depth)// Функция измерения макс глубины дерева
{
if(s->data==error)
{
printf("Tree is empty.\n");
system("pause");
}
else
{
if(s==NULL)
return depth;
else
return max(l_tree(s->left,depth+1),l_tree(s->right,depth+1));
}
}
вот, написал но она не работает:\
всё) нашёл ошибку
- условие лишнее, из-за него и была ошибка:)
Код:
if(s->data==error)
{
printf("Tree is empty.\n");
system("pause");
}
{
printf("Tree is empty.\n");
system("pause");
}
- условие лишнее, из-за него и была ошибка:)
Есть более простой способ, рекурсивно, хотя на вкус и цвет товарищей нет. но выложу алгоритм
думаю друзья БГУИРовцы поблагодарят меня=))
Код:
int count(Tree *p, int c){
if(c>max) max=c;
if(p->left!=NULL) count(p->left, c+1);
if(p->right!=NULL) count(p->right, c+1);
return max;
}
if(c>max) max=c;
if(p->left!=NULL) count(p->left, c+1);
if(p->right!=NULL) count(p->right, c+1);
return max;
}
думаю друзья БГУИРовцы поблагодарят меня=))
Не соглашусь с последним ответом: count возвращает тип int , и его надо куда-то сохранять. Не говоря уже о непонятно откуда взявшейся max. Идея привлекательная, но хотелось бы её немного отредактировать:
int count (tree*p, int c)
{
int a,b;
if (p->left) a=count(p->left, c+1);
if (p->right) b=count(p->right, c+1);
if (a>c) return a;
else if (b>c) return b;
else return c;
}
int count (tree*p, int c)
{
int a,b;
if (p->left) a=count(p->left, c+1);
if (p->right) b=count(p->right, c+1);
if (a>c) return a;
else if (b>c) return b;
else return c;
}
Значения a и b не указаны.
Точнее должно быть так:
При вызове с драйвера нужно указать перво значение d= 0.
if (a>c) return a; неверно, поскольку глубина правой части может быть больше, чем левой.
Точнее должно быть так:
Код:
int Depth (int d)
{
int a=0,b=0;
if (this->l!=NULL)
a = this->l->Depth(d++);
if (this->r!=NULL)
b= this->r->Depth(d++);
if (a>d && a>b) return a;
if (b>d) return b;
return d;
}
{
int a=0,b=0;
if (this->l!=NULL)
a = this->l->Depth(d++);
if (this->r!=NULL)
b= this->r->Depth(d++);
if (a>d && a>b) return a;
if (b>d) return b;
return d;
}
if (a>c) return a; неверно, поскольку глубина правой части может быть больше, чем левой.