1 Replies - 352 Views - Last Post: 02 April 2013 - 10:05 AM Rate Topic: -----

#1 neondayz  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 10
  • Joined: 02-April 13

Height of a binary search tree

Posted 02 April 2013 - 06:21 AM

Hello im trying to figure out this qusetion for my assignment but i have no clue how to make the function.

Using a binary tree, write and test a function that finds the height of the tree.

Heres the binary tree i have made how would i make a function that finds the height of the tree?

 //
//  main.cpp
//  BinarySearchTree
//

#include <iostream>

using namespace std;

struct node
{
    int data;
    node * left;
    node * right;
};

node * insert(int data, node ** tree); // need to be able to modify the tree node
void destroy(node *tree);
void printTree(node *tree);

node * search(int key, node *tree);

int main(int argc, const char * argv[])
{
    node * root = NULL;
    node * current = NULL;
    int value;

    do
    {
        cout << "Please enter an integer, zero to quit" << endl;
        cin >> value;
        current = insert(value, &root);
        printTree(root);
    } while (value != 0);

    do
    {
        cout << "Search for an integer, zero to quit" << endl;
        cin >> value;
        current = search(value, root);
        if (current == NULL)
        {
            cout << "The number " << value << " is not in the tree" << endl;
        }
        else
        {
            cout << "The number " << value << " is at node " << current << endl;
        }
    } while (value != 0);


    cout << "The tree is " << endl;
    printTree(root);

    // destroy the tree
    destroy(root);

    return 0;
}

node * search(int key, node *tree)
{
    if (tree == NULL || tree->data == key)
        return tree;
    if (key < tree->data)
        return search(key, tree->left);
    else
        return search(key, tree->right);
}

void printNode(node * Node)
{
    cout << " addr = " << Node << " left = " << Node->left << " right = " << Node->right;
    cout << " data = " << Node->data << " " << endl;
}

node * createNode(int data)
{
    node * newNode = NULL;

    newNode = new node;
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;

    cout << "created new node ";
    printNode(newNode);

    return newNode;
}

node * insert(int data, node ** tree)
{
    node * newNode = NULL;

    if ((*tree) == NULL) // there is no tree
    {
        newNode = createNode(data);
        *tree = newNode;
    }
    else if (data < (*tree)->data) // goes to left of existing node
    {
        // check if left node exists
        if ((*tree)->left == NULL)
        {
            newNode = createNode(data);
            (*tree)->left = newNode;
        }
        else
        {
            newNode = insert(data, &((*tree)->left));
        }
    }
    else // goes to the right of the existing node
    {
        // check if right node exists
        if ((*tree)->right == NULL)
        {
            newNode = createNode(data);
            (*tree)->right = newNode;
        }
        else
        {
            newNode = insert(data, &((*tree)->right));
        }
    }

    return newNode;
}

void destroy(node *tree)
{
    if (tree != NULL)
    {
        if (tree->left != NULL)
        {
            destroy(tree->left);
        }
        if (tree->right != NULL)
        {
            destroy(tree->right);
        }
        delete tree;
    }
}

void printTree(node *tree)
{
    if (tree != NULL)
    {
        printTree(tree->left);
        printNode(tree);
        printTree(tree->right);
    }
}
 


Is This A Good Question/Topic? 0
  • +

Replies To: Height of a binary search tree

#2 Martyr2  Icon User is offline

  • Programming Theoretician
  • member icon

Reputation: 4194
  • View blog
  • Posts: 11,868
  • Joined: 18-April 07

Re: Height of a binary search tree

Posted 02 April 2013 - 10:05 AM

Have you ever found the max value of an array? You loop through the array and whenever a value you come across is more than the current value for "max" you set max to that value. When at the end you have the highest value.

Similar concept here. You set a max value to one before entering the tree. Also create a second variable to hold the current "level" deep in the tree. Each time you go down into a child you increment the current level and compare it to max. If it is greater than max, you update max. Each time you go back up into the parent, you decrement the current level (not max, max only is set when the current level exceeds the value of max).

So let's go through an example..

max = 1
current = 1

     A
   B   C
 D    E   F
     G



We go from A down into B, increment current to 2. Is 2 > max? yes, max is set to 2. We go down into D, increment current to 3. Is 3 > max? Yes, max is set to 3. We go back to B, so we decrement current back to 2. Go back to A, decrement current to 1. We go to C, increment current. Great than max? no, go to E and increment current. Is it greater than max? No both are 3. Go down into G, increment current to 4. Is it greater than max? Yes, max is set to 4. Etc etc...

End result is that the height is max after then entire tree is iterated through. Height of tree, 4.

Hope you get the idea. :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1