Binary Search Trees (and eventually, a non-binary tree)

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 3289 Views - Last Post: 01 January 2013 - 12:41 AM Rate Topic: -----

#16 IceHot  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 186
  • Joined: 28-August 12

Re: Binary Search Trees (and eventually, a non-binary tree)

Posted 31 December 2012 - 06:20 PM

Now, I have implemented a binary tree and a general tree. Each node of the general tree has the same amount of subnodes. Now, I am making a directory tree, but I am having problems with it. My code is supposed to create the full tree, but only ends up making the first level of subnodes and the subtree of the first subnode. Here is my full code (which is intended for Windows machines), just make sure you replace "C:/Users/owner/Desktop/*." with your_directory+"/*." whilst testing the code:
#include <iostream>
#include <windows.h>
#include <string>
#include <cstring>
#include <new>

using namespace std;

//initializations
int numFolders = 0;
int numSubnodes = 0;
HANDLE h;
WIN32_FIND_DATA fd;
struct node
{
    string value;
    node ** subnode;
};   //end node

void createtree(int n, node * a)
{
    //The integer parameter is only going to be used what to store to values. It will also provide for easy access to the parent value:
    //parent_value == a->value
    if (n == 0)
    {
        a->value = "C:/Users/owner/Desktop"; //store the root directory to the value.
        cout << a->value << endl;
        h = FindFirstFile("C:/Users/owner/Desktop/*.", &fd);    //set the handle to FindFirstFile(root_directory, &fd)
        //Find number of folders in root directory. Exclude any that have '.' in the name.
        do
        {
            if (((string)fd.cFileName != ".") && ((string)fd.cFileName != ".."))
            {
                numSubnodes++;
            }   //end if
        }   //end do
        while (FindNextFile(h,&fd));
        if (numSubnodes != 0)
        {
            createtree(1,a);
        }   //end inner if
    }   //end if
    else
    {
        if (numSubnodes != 0)
        {
            a->subnode = new(nothrow) node * [numSubnodes]; //make array of subnode pointers
            numFolders = numSubnodes;   //passing the number of folders to another variable (to prevent logic error in the loop)
            cout << "numFolders == "<<numFolders<<endl;
            cout << "a->value == "<<a->value<<endl;
            h = FindFirstFile((a->value+"/*.").c_str(), &fd);    //set the handle to FindFirstFile(value_of_parent_directory, &fd)
            for (int temp = 0; temp < numFolders; temp++)
            {
                a->subnode[temp] = new (nothrow) node;
                //Set the value to fd.cFileName. Use control structure here to check for the "." and ".." (to throw them out)
                if (temp == 0)
                {
                    while ((((string)fd.cFileName == ".") || ((string)fd.cFileName == "..")) && (FindNextFile(h,&fd)))
                    {
                        //do nothing; the FindNextFile(h,&fd) is changing fd.cFileName to the next folder
                    }   //end while
                    //This is just in case the only subdirectories found were "." and ".."
                    if (((string)fd.cFileName != ".") && ((string)fd.cFileName != ".."))
                    {
                        a->subnode[temp]->value = (string)fd.cFileName;
                    }   //end if
                }   //end if
                else
                {
                    if (FindNextFile(h,&fd)) a->subnode[temp]->value = (string)fd.cFileName;
                }   //end else
                //append the parent value to the front of them
                if ((string)fd.cFileName != "")
                {
                    a->subnode[temp]->value = (string)a->value+'/'+a->subnode[temp]->value;
                    cout << a->subnode[temp]->value << endl;
                }   //end if
            }   //end for
            for (int temp = 0; temp < numFolders; temp++)
            {
                numSubnodes = 0;    //reset the number of subnodes to 0
                h = FindFirstFile((a->subnode[temp]->value + "/*.").c_str(), &fd);  //Initializing the handle value for the next run
                //check the number of folders (that aren't named "." or ".."!)
                do
                {
                    if (((string)fd.cFileName != ".")&&((string)fd.cFileName != ".."))
                    {
                        numSubnodes++;
                    }   //end if
                }   //end do
                while (FindNextFile(h,&fd));
                createtree(n+1,a->subnode[temp]);
            }   //end for
        }   //end if
        else
        {
            a->subnode = 0;    //initialize the pointer to 0; there is nothing to be done here!
        }   //end else
    }   //end else
}   //end createtree

int main()
{
    node dirtree;
    createtree(0,&dirtree);
    return 0;
}



This post has been edited by IceHot: 31 December 2012 - 06:27 PM

Was This Post Helpful? 0
  • +
  • -

#17 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3169
  • View blog
  • Posts: 9,595
  • Joined: 05-May 12

Re: Binary Search Trees (and eventually, a non-binary tree)

Posted 01 January 2013 - 12:41 AM

You have over complicated the recursive building of your tree. Most of the complication is due to you keeping information in globals instead of using local variables or passing data as variables.

Some things to help you out:

First, since you are already using the standard string class, why not also use the standard vector class as well. Right now your node class has provisions to store an array of pointers to child nodes, but you never keep track of how many child nodes you have. The vector class will keep track of the number of child nodes as well as the allocations.

Second, most everything can be done in a single pass through each directory level. It's a matter changing your approach to passing variables.

Consider this class:
struct Node
{
    string name;
    vector<Node> children;
};



And this recursive pseudo-code:

main()
{
    Node root;

    BuildTree("C:\\Users\\owner\\Desktop", &root);
}

BuildTree(const string & path, Node & node)
{
    node.name = path;

    hFind = FindFirstFile(path + "\\*", &finddata);
    do
    {
        if (finddata.cFileName == "." ||
            finddata.cFileName == "..")
        {
            continue;
        }

        Node child;

        child.name = path + "\\" + finddata.cFileName;

        if (finddata.attribute indicates a directory)
        {
            BuildTree(child.name, child);
        }

        node.children.push_back(child);

    } while(FindNextFile(hFind, &finddata));
}


Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2