max функция c высота дерева

есть ли функция max в c, чтобы я мог сделать что-то подобное, чтобы вычислить высоту дерева: или, возможно, есть лучший способ вычислить высоту дерева.

int height(struct node *tree)
{ 
    if (tree == NULL) return 0;
    return 1 + max(height (tree->left), height (tree->right)); 
}

если да, то что мне нужно?

в настоящее время я получаю эту ошибку:

dict-tree.o: В функции 'height':
/home/ex10/dict-tree.c:36: неопределенная ссылка на `max'


c max tree
person learner123    schedule 16.02.2011    source источник

Ответы (5)


arrow_upward
2
arrow_downward

Вероятно, потому что max — неопределенная функция,

попробуйте сначала реализовать max, прежде чем продолжить.

int max(int a, int b) {
    if(a > b) return a;
    else return b;
}
person Andreas Wong    schedule 16.02.2011

arrow_upward
7
arrow_downward

Нет, встроенной нет. Обычно вы пишете свою собственную встроенную функцию, например.

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

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

int height(struct node *tree)
{ 
    int height_left, height_right;
    if (tree == NULL) return 0;

    height_left = height (tree->left);
    heigth_right = height (tree->right);

    return 1 + ((height_left > height_right) ? height_left : height_right);
}

Н.Б. остерегайтесь максимальной макро-ловушки. Заманчиво сделать что-то вроде

#define MAX(a,b) (((a) > (b)) ? (a) : (b))

которые вы затем можете использовать для любых входных данных независимо от их типов, но проблема здесь в том, что любое из входных выражений имеет побочные эффекты, например. MAX(++i, ++j). Тогда проблема заключается в том, что побочные эффекты будут оцениваться дважды для того, какой из входных данных является максимальным. Если вы собираетесь кодировать max, вы должны использовать (встроенную) функцию, а не макрос. К сожалению, поскольку вы работаете на C, а не на C++ без перегрузки/шаблонов, это ограничит вас одним набором типов ввода/вывода для каждой именованной функции max.

person Rup    schedule 16.02.2011

arrow_upward
2
arrow_downward

Нет, нет. Существует семейство функций для вычисления максимума значений с плавающей запятой (см. fmax() и др.), которые вы, безусловно, могли бы использовать сами, но я думаю, что проще сделать это локально.

Что-то типа:

const size_t left = height (tree->left);
const size_T right = height (tree->right);
return left > right ? left : right;
person unwind    schedule 16.02.2011

arrow_upward
0
arrow_downward

Если вы хотите использовать C++, а не просто C, то есть. Он находится в стандартной библиотеке шаблонов, поэтому вам нужно будет включить необходимый файл. См. здесь для примера:

http://www.cplusplus.com/reference/algorithm/max/

Воспроизведено для вашего удобства:

// max example
#include <iostream>
#include <algorithm>
using namespace std;

int main () {
  cout << "max(1,2)==" << max(1,2) << endl;
  cout << "max(2,1)==" << max(2,1) << endl;
  cout << "max('a','z')==" << max('a','z') << endl;
  cout << "max(3.14,2.72)==" << max(3.14,2.72) << endl;
  return 0;
}
person EmeryBerger    schedule 16.02.2011

arrow_upward
0
arrow_downward 

int height(struct node *tree)
{ 
if (tree == NULL) 
{
    return 0;
}    
int left = height(tree->left);
int right = height(tree->right);
return (1 + ((left >right)?left:right)); 
}

//если еще лучше, чем функция max в этом случае

person Ron Aham    schedule 05.05.2015