Wysokość drzewa RB

 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TRUE 1
#define FALSE 0

struct node
{
 enum { BLACK, RED } color;
 unsigned int value;
 struct node *left, *right, *parent;
};

void dopisz();
void print(struct node *tmp,unsigned h,unsigned long long M);
void rotateLeft(struct node *x);
void rotateRight(struct node *x);
void insertFixup(struct node *x);
int findNode(unsigned int value);
struct node *insertNode(unsigned int value);
int HeightBSTree(struct node *T);

int iloscDodanych = 0;
int iloscSzukan = 0;

struct node *root = 0;

int main()
{
    int isEnd = FALSE;
	char answer[100];
    int h;
	int zarodek;
    zarodek= time(NULL);
    srand(zarodek);
	while(!isEnd)
	{
		printf("\n\t\tMENU\n");
		printf("[0] - zakonczenie programu\n");
                printf("[1] - dopisanie\n");
                printf("[2] - usuniecie\n");
                printf("[3] - wyswietlenie wysokości drzewa\n");
		scanf("%s", answer);

                switch(answer[0])
                {
                        case '0':
                                printf("Zakonczenie!\n");
                                isEnd=TRUE;
                                break;
                        case '1':
                                while(iloscDodanych < 10000)
                                {
                                    dopisz(rand()%100000);
                                }

                                break;
                        case '2':
                                //bedzie potem
                                break;
                        case '3':

                                h = HeightBSTree(root);
                                printf("%d\n", h);

                                break;
                        default:
                                printf("Bledny wybor...\n");
                }
	}
	return 0;
}

struct node *insertNode(unsigned int value)
{
    struct node *current, *parent, *x;
    current = root;
    parent = NULL;
    while (current != NULL)
    {
        if (value == current->value) return (current);
            parent = current;
        current = (value > current->value) ?
            current->left : current->right;
    }

    if ((x = malloc (sizeof(*x))) == 0)
    {
        printf ("Brak pamieci\n");
        exit(1);
    }

    x->value = value;
    x->parent = parent;
    x->left = NULL;
    x->right = NULL;
    x->color = RED;

    if(parent)
    {
        if(value > parent->value)
            parent->left = x;
        else
            parent->right = x;
    }
    else
    {
        root = x;
    }
    insertFixup(x);
    return x;
}

void insertFixup(struct node *x)
{
    while ((x != root) && (x->parent->color == RED))
    {
        if (x->parent == x->parent->parent->left)
        {
            struct node *y = x->parent->parent->right;
            if ((y)&&(y->color == RED))
            {
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;

            }
            else
            {
                if ((x)&&(x == x->parent->right))
                {
                    x = x->parent;
                    rotateLeft(x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateRight(x->parent->parent);
            }
        }
        else
        {

            struct node *y = x->parent->parent->left;
            if ((y)&&(y->color == RED))
            {
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            }
            else
            {
                if (x == x->parent->left)
                {
                    x = x->parent;
                    rotateRight(x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateLeft(x->parent->parent);
            }
        }
    }
    root->color = BLACK;
}

void rotateLeft(struct node *x)
{

    struct node *y = x->right;
    x->right = y->left;
    if (y->left != NULL) y->left->parent = x;

    if (y != NULL) y->parent = x->parent;
    if (x->parent)
    {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    }
    else
    {
        root = y;
    }
    y->left = x;
    if (x != NULL)
        x->parent = y;
}

void rotateRight(struct node *x)
{
    struct node *y = x->left;

    x->left = y->right;
    if (y->right != NULL) y->right->parent = x;

    if (y != NULL) y->parent = x->parent;
    if (x->parent)
    {
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    }
    else
    {
        root = y;
    }
    y->right = x;
    if (x != NULL)
        x->parent = y;
}

void dopisz(unsigned int tValue)
{
    if(findNode(tValue))
    {
        insertNode(tValue);
        iloscDodanych++;
    }

}


int findNode(unsigned int value)
{
    struct node *current = root;
    while(current != NULL)
    if(value == current->value)
        return FALSE;
    else
        current = (value > current->value) ?
        current->left : current->right;
    return TRUE;
}

int HeightBSTree(struct node *T)
{
	int hleft=0, hright=0;
	if(T->left)
	{
	    hleft = HeightBSTree(T->left);
		hright = HeightBSTree(T->right);
	}
	if(T->right)
	{
	    hleft = HeightBSTree(T->left);
		hright = HeightBSTree(T->right);
	}
	if(hleft > hright)
        return hleft;
    else return hright;
}

Nie wiem gdzie tutaj jest wejście na nulla. Ta sama funkcja działa mi w drzewie BST. ;\ Czy ktoś mógłby mi z tym pomóc?

        if(T->left)
        {
            hleft = HeightBSTree(T->left);
                hright = HeightBSTree(T->right); // tu
        }
        if(T->right)
        {
            hleft = HeightBSTree(T->left);  // oraz tu
                hright = HeightBSTree(T->right);
        }

int HeightRBTree(struct node *T)
{
	int hleft, hright;
	if ( T != NULL )
	{
		hleft = HeightBSTree(T->left);
		hright = HeightBSTree(T->right);
		return(1 + (hleft > hright ? hleft : hright));
	}
	else
		return(0);
}

Działa porządnie. Polecam. ;P

To samo co wyżej ale po ludzku:

unsigned HeightRBTree(struct node *T) { return T?max(HeightBSTree(T->left),HeightBSTree(T->right)):0; }