开发者

max function c tree height

is there a max function in c so i can do something like this to calculate tree height :or perhaps there is a better way to calculate tree height.

开发者_高级运维
int height(struct node *tree)
{ 
    if (tree == NULL) return 0;
    return 1 + max(height (tree->left), height (tree->right)); 
}

if so what includes do i need?

currently i get this error :

dict-tree.o: In function 'height':

/home/ex10/dict-tree.c:36: undefined reference to `max'


No, there isn't one built in. Typically you'd write your own inline function, e.g.

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

(using whichever 'inline' hint syntax your compiler prefers). In your case, though, you might as well just spell this out manually - it's simple enough:

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);
}

N.B. beware of the max macro trap. It's tempting to do something like

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

which you can then use for any inputs regardless of their types, but the problem here is if either of the input expressions have side effects, e.g. MAX(++i, ++j). The issue then is that the side effects will get evaluated twice for whichever of the inputs is the max. If you're going to code up max you must use an (inline) function rather than a macro. Unfortuantely since you're in C not C++ without overloading / templates this will limit you to one set of input / output types per named max function.


Probably because max is an undefined function,

try implementing max first before proceeding.

int max(int a, int b) {
    if(a > b) return a;
    else return b;
}


No there isn't. There is a family of functions to compute the maximum of floating-point values (see fmax() and friends), which you could certainly use yourself, but I think it's easier to just do it locally.

Something like:

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


If you are willing to use C++ rather than just plain C, there is. It's in the Standard Template Library, so you will have to include the requisite file. See here for an example:

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

Reproduced for your convenience:

// 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;
}


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)); 
}

//if else is better than function max in this case

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜