C++ Binary Tree Basics

This is a discussion on C++ Binary Tree Basics within the C++ Programming forums, part of the General Programming Boards category; Code: //Declare Data Structure struct CP { int id; //ID of the Node int data; //Data of the Node CP ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    2

    C++ Binary Tree Basics

    Code:
    //Declare Data Structure
    struct CP {
        int id;         //ID of the Node
        int data;       //Data of the Node
        CP * left;      //Pointer to the Left Subtree 
        CP * right;     //Pointer to the Right Subtree
    };
    
    typedef CP * CPPtr;
    I have a structure of tree that looks like this. Without changing the structure of tree, I am required to write a function that return's the depth of a node given it's id. (id is a unique number that represents the node). i.e. something like int getDepth(CPPtr tree,int id).

    Can anyone help me? Your help would be much appreciated.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,981
    What is your idea and what have you tried?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Mar 2012
    Posts
    2
    my idea is simply have a function that checks the id of a node by taking it's pointer => nodeID
    Then I traverse the tree until it found nodeID(tree pointer) == id. Then I calculate the depth by using ldepth and rdepth.
    Initially i intend to do it in 1 function using recursion, but failed to do so.
    So i used 2 functions,1 doing the recursion and another just takes the result and process.
    However, it never really worked

    Code:
    
    int nodeDepth(CPPtr tree, int id) 
    {     
       int lDepth=0,rDepth=0;     
       nodeDepth_Helper(tree,id,lDepth,rDepth);    
       cout<<"lDepth "<<lDepth<<endl;   
       cout<<"rDepth "<<rDepth<<endl;   
       return min(lDepth,rDepth); 
    }  
    
    //Define nodeDepth_Helper to do the actual recursion to find lDepth and rDepth 
    void nodeDepth_Helper(CPPtr tree, int id, int& lDepth,int& rDepth)
    {    
    if (tree != NULL)    
    {      
         if (nodeID(tree)==id)             
                return;          
        else       
        {            
            lDepth=lDepth+1;     
            nodeDepth_Helper(tree->left,id,lDepth,rDepth);      
            rDepth=rDepth+1;   
            nodeDepth_Helper(tree->right,id,lDepth,rDepth);          
         }    
    } 
    }

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,981
    The helper idea is good, but I suggest that you pass the depth by value, and then return the depth at which the node was found, or a designated value to indicate not found.

    Then, if the current node is the node to find, you just return the current depth. Otherwise, you (recursively) search for the node in the left subtree: if it is found, you return the depth found, otherwise you search for the node in the right subtree: if it is found, you return the depth found, otherwise you return the value for not found.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting From Binary Tree to Threaded Binary Trees
    By elton_fan in forum C Programming
    Replies: 15
    Last Post: 11-08-2007, 10:41 PM
  2. Replies: 2
    Last Post: 08-01-2007, 01:08 PM
  3. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  4. display tree data in binary tree format
    By xddxogm3 in forum C++ Programming
    Replies: 4
    Last Post: 12-10-2003, 11:47 PM
  5. b-tree (not binary tree) implementation help
    By Unregistered in forum C++ Programming
    Replies: 8
    Last Post: 01-02-2002, 02:30 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21