Height of the Tree

[LStriker]

I can't make my code just to show the tree size.
Something like: left -1, right 1, root 0. I've tried to use a few codes that i found here but none has worked... :/

#include <conio.h>#include <stdio.h>
#include <stdlib.h>


typedef struct Node
{
    struct Node *left;
    struct Node *right;
    int value;
} Node;


void insertNode(Node **tree,int element)
{
    if(*tree == NULL)
    {
        Node *aux = (Node *)malloc(sizeof(Node));
        aux->value = element;
        aux->right= NULL;
        aux->left = NULL;
        *tree = aux;
        printf("The value %d has been inserted.\n",element);
        return;
    }


    if(element < (*tree)->value)
    {
        insertNode(&(*tree)->left,element);
        return;
    }


    if(element > (*tree)->value)
    {
        insertNode(&(*tree)->right,element);
        return;
    }
    printf("The value %d is already in the tree.\n",element);
}


Node *Removtwo(Node *two)
{
    if(two==NULL)
        return NULL;
    else if(two->left == NULL)
        return Removtwo(two->right);
    else
        return Removtwo(two->left);
}


void removerNode(Node **tree,int element)
{
    if(element < (*tree)->value)
    {
        removerNode(&(*tree)->left,element);
    }
    else if(element > (*tree)->value)
    {
        removerNode(&(*tree)->right,element);
    }
    else if((*tree)->left!=NULL && (*tree)->right!=NULL)
    {
        Node *aux= NULL;
        aux = Removtwo((*tree)->right);
        (*tree)->value = aux->value;
        removerNode(&(*tree)->right,(*tree)->value);
    }
    else
    {
        Node *aux = (*tree);
        if((*tree)->left==NULL)
        {
            (*tree) = (*tree)->right;
        }
        else
        {
            *tree = (*tree)->left;
        }
        printf("The value %d was sucessfull removed.\n",element);
        free(aux);
    }
}


void Print(Node *tree)
{
    if(tree == NULL)
    {
        return;
    }else
    Print(tree->left);
    printf("%d->",tree->value);
    Print(tree->right);
}


int main()
{
    int num,insertion,removing;
    Node *tree = NULL;


    while(num != 4)
    {
        printf("-------------------------------------\n");
        printf("------ 1. Insert         ------------\n");
        printf("------ 2. Remove         ------------\n");
        printf("------ 3. Print Tree     -----------\n");
        printf("------ 4. Exit           ------------\n");
        printf("-------------------------------------\n");
        scanf("%d", &num);
        system("cls");


        switch(num)
        {
        case 1:
        {
            printf("Put the value: ");
            scanf("%d",&insertion);
            insertNode(&tree,insertion);
            getch();
            system("cls");
            break;
        }
        case 2:
        {
            printf("Put the value: ");
            scanf("%d",&removing);
            removerNode(&tree,removing);
            getch();
            system("cls");
            break;
        }
        case 3:
        {
            Print(tree);
            getch();
            system("cls");
            break;
        }
        case 4:
             {
                system("cls");
               break;
             }
        }
    }
}

[vart]

I do not get what you mean by tree size.
If left size if 1 and right size is 1, Why root size is 0?

I thought it would be left_size + right_size +1 if you want total number of nodes, or max(left_size, right_size) + 1, if you want the tree depth.

So what do you want to get when you are talking about tree size?

[Elysia]

Heads up - this is C and not C++. Please post in the C section next time.

[LStriker]

I do not get what you mean by tree size.
If left size if 1 and right size is 1, Why root size is 0?

I thought it would be left_size + right_size +1 if you want total number of nodes, or max(left_size, right_size) + 1, if you want the tree depth.

So what do you want to get when you are talking about tree size?

i expressed myself a little bit wrong, but i want to do just what u said.. i tried to implement this but did not work:

height(Node) = max ( height(node.Left) + height (node.Right)) +1
printf (" Left: %d Right: %d ", tree->left, tree->right);


Sorry about the section... i'll post in the right one next time

[iMalc]

I can't make my code just to show the tree size.

Where is the bit of code that attempts to do that?

Do you mean the number of nodes, or the maximum depth?

[LStriker]

Where is the bit of code that attempts to do that?

Do you mean the number of nodes, or the maximum depth?

Maximum depth;
i tried too many codes but none has work so i came to the conclusion that i don't know how to do this. I was trying something like this
height(Node) = max ( height(node.Left) + height (node.Right)) +1
printf (" Left: %d Right: %d ", tree->left, tree->right);

[anduril462]

Maximum depth;
i tried too many codes but none has work so i came to the conclusion that i don't know how to do this. I was trying something like this
height(Node) = max ( height(node.Left) + height (node.Right)) +1
printf (" Left: %d Right: %d ", tree->left, tree->right);

You're on the right track with the recursive function, but there's a small error. Look carefully at your usage of max. You are finding the max of one thing, the sum of the left and right sub-trees. Summing those two things produces a single value and you're asking for the max of just one thing, which doesn't really make sense. You need to find the max of either the left or right sub-tree

vart showed you the correct way in post #2 (notice the , not a +):

...or max(left_size, right_size) + 1, if you want the tree depth.

So take that, and come up with a function. If you get stuck, post the code you have and we will help you fix it.

[iMalc]

Well judging by all the things that you have in the code posted, you are capable of putting that formula to use already.

Just try adding it into your code and post the function that you put it in, along with any compile errors.