Thread: Binary Tree

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    4

    Binary Tree

    Hello, I'm having a problem writing the output to 'tree.out' for my binary tree program. What it's supposed to do is to outf it to my tree.out by reading the data from tree.dat. I've already put tree.dat and tree.out in my resource files.

    Here is my code.

    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <iomanip>
    
    using namespace std;
    
    struct treetype
    {
    	treetype *root, *left, *right;
    	int id;
    };
    
    void createtree (treetype *&root)
    {
    	root = new treetype;
    	root->id = -1;
    	root->left = NULL;
    	root->right = NULL;
    }
    
    bool emptytree(treetype *root)
    {
    	return root == NULL;
    }
    
    void inserttree(treetype *root, int id)
    {
    	treetype *parent, *current, *knew;
    	int data = id;
    	if(!emptytree(root))
    	{
    		knew = new treetype;
    		knew->id = data;
    		knew->left = NULL;
    		knew->right = NULL;
    
    		parent = NULL;
    		current = root;
    
    		while(current != NULL)
    		{
    			parent = current;
    			if(data < current->id)
    				current = current->left;
    			else
    				current = current->right;
    		}
    
    		if(data < parent->id)
    			parent->left = knew;
    		else
    			parent->right = knew;
    	}
    	else
    		root->id = data;
    }
    
    void readtree(treetype *root)
    {
    	int id;
    	ifstream inf;
    	ofstream outf;
    	inf.open("tree.dat");
    	outf.open("tree.out");
    
    	outf << "Original Output" << endl << endl;
    
    	while (!inf.eof())
    	{
    		inf >> id;
    	}
    }
    
    void inorder(treetype *root)
    {
    	if(current != NULL)
    	{
    		inorder(current->left);
    		outf << current->id << endl;
    		inorder(current->left);
    	}
    }
    void main()
    {
    	treetype *root;
    	createtree(root);
    	readtree(root);
    	inorder(root);
    }
    It is giving me this errors.

    Code:
    c:\documents and settings\owner\my documents\visual studio 2005\projects\hw4trees\hw4trees\hw4trees.cpp(77) : error C2065: 'current' : undeclared identifier
    c:\documents and settings\owner\my documents\visual studio 2005\projects\hw4trees\hw4trees\hw4trees.cpp(79) : error C2227: left of '->left' must point to class/struct/union/generic type
            type is ''unknown-type''
    c:\documents and settings\owner\my documents\visual studio 2005\projects\hw4trees\hw4trees\hw4trees.cpp(80) : error C2065: 'outf' : undeclared identifier
    c:\documents and settings\owner\my documents\visual studio 2005\projects\hw4trees\hw4trees\hw4trees.cpp(80) : error C2227: left of '->id' must point to class/struct/union/generic type
            type is ''unknown-type''
    c:\documents and settings\owner\my documents\visual studio 2005\projects\hw4trees\hw4trees\hw4trees.cpp(81) : error C2227: left of '->left' must point to class/struct/union/generic type
            type is ''unknown-type''

  2. #2
    Registered User
    Join Date
    Mar 2007
    Posts
    4
    Can someone please help me. I'm really desperate...

    Here's my new code

    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <iomanip>
    
    using namespace std;
    
    struct treetype
    {
    	treetype *root, *left, *right;
    	int id;
    };
    
    void createtree (treetype *&root)
    {
    	root = new treetype;
    	root->id = -1;
    	root->left = NULL;
    	root->right = NULL;
    }
    
    bool emptytree(treetype *root)
    {
    	return root == NULL;
    }
    
    void inserttree(treetype *root, int id)
    {
    	treetype *parent, *current, *knew;
    	int data = id;
    	if(!emptytree(root))
    	{
    		knew = new treetype;
    		knew->id = data;
    		knew->left = NULL;
    		knew->right = NULL;
    
    		parent = NULL;
    		current = root;
    
    		while(current != NULL)
    		{
    			parent = current;
    			if(data < current->id)
    				current = current->left;
    			else
    				current = current->right;
    		}
    
    		if(data < parent->id)
    			parent->left = knew;
    		else
    			parent->right = knew;
    	}
    	else
    		root->id = data;
    }
    
    void readtree(treetype *root)
    {
    	int id;
    	ifstream inf;
    	inf.open("tree.dat");
    
    	while (!inf.eof())
    	{
    		inf >> id;
    	}
    	insertree(root);
    }
    
    void inorder(treetype *root)
    {
    	if(root != NULL)
    	{
    		inorder(root->left);
    		cout << root->id << endl;
    		inorder(root->right);
    	}
    }
    void main()
    {
    	treetype *root;
    	createtree(root);
    	readtree(root);
    	inserttree(root, id);
    	inorder(root);
    }
    It's supposed to do an inorder sort on the tree but I can't figure it out on how to really do it. I've gone through many people and ask them how to do it but they keep telling me that I'm stupid. I know I am but please just try to help me and show me the right way...I'm really begging each and one of you. Please...just please...help me...please.

  3. #3
    Registered User
    Join Date
    Dec 2005
    Location
    Colchester, Essex, United Kingdom.
    Posts
    31
    In your `inorder' function, you are referencing a variable `current' and there appears to be no variable with that name in scope. There is a variable with that name, however, in your `inserttree' function. Perhaps you got confused?

    [edit]: Nevermind. Looks like you made that correction in your update. Does your code compile now, then?
    Last edited by tomcant; 03-30-2007 at 09:15 AM.

  4. #4
    Registered User
    Join Date
    Mar 2007
    Posts
    4
    Yes it compiles now, but it still won't do the inorder function for the tree. I'm not calling it right and I dunno how or where to put it.

    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <iomanip>
    
    using namespace std;
    
    struct treetype
    {
    	treetype *root, *left, *right;
    	int id;
    };
    
    void createtree (treetype *&root)
    {
    	root = new treetype;
    	root->id = -1;
    	root->left = NULL;
    	root->right = NULL;
    }
    
    bool emptytree(int id)
    {
    	return id == -1;
    }
    
    void inserttree(treetype *root, int id)
    {
    	treetype *parent, *current, *knew;
    	int data = id;
    	if(!emptytree(id))
    	{
    		knew = new treetype;
    		knew->id = data;
    		knew->left = NULL;
    		knew->right = NULL;
    
    		parent = NULL;
    		current = root;
    
    		while(current != NULL)
    		{
    			parent = current;
    			if(data < current->id)
    				current = current->left;
    			else
    				current = current->right;
    		}
    
    		if(data < parent->id)
    			parent->left = knew;
    		else
    			parent->right = knew;
    	}
    	else
    		root->id = data;
    }
    
    void readtree(treetype *root)
    {
    	int id;
    	ifstream inf;
    	inf.open("tree.dat");
    
    	while (!inf.eof())
    	{
    		inf >> id;
    	}
    }
    
    void inorder(treetype *root)
    {
    	if(root != NULL)
    	{
    		inorder(root->left);
    		cout << root->id << endl;
    		inorder(root->right);
    	}
    }
    
    int main()
    {
    	treetype *root;
    	int id;
    	createtree(root);
    	readtree(root);
    	inserttree(root, id);
    }

  5. #5
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    This is very C-stype programming... Don't you want to start writing a class?

    Code:
    int id;
    ...
    inserttree(root, id); // id is not initialized here
    readtree initializes local var in a loop and puts it away...
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  6. #6
    Registered User
    Join Date
    Mar 2007
    Posts
    4
    Didn't I initialize it in my inserttree function? What's the proper way of doing it?

  7. #7
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    for example
    id = readvalue();

    and readvalue should return the value read from file, as I see it does not use tree, so no need to pass it as a param
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by vart View Post
    for example
    id = readvalue();

    and readvalue should return the value read from file, as I see it does not use tree, so no need to pass it as a param
    From what I can tell, readtree does need to pass the tree in as a param (although it will need to be by reference), and he just hasn't finished that function yet.
    It looks like it will need to read from the file and call inserttree for each item.

    btw, the inorder function is correct (short of being const-correct though), and was fine how it was being called from main.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM